Puzzles and Brainteasers, lesson 1
A puzzle you've never seen
Ways in when a puzzle looks like nothing you know.
Interview puzzles are picked so that you haven't met them before. What helps is a few ways in that work on almost any puzzle, and the habit of thinking out loud. You need school maths and nothing else.
Part 1. Try small cases
Work small cases to find a pattern, then find the reason it holds.
Guess first
100 lamps in a row, numbered 1 to 100, are all off. 100 people walk past in turn: person 1 flips every switch, person 2 every 2nd switch, person 3 every 3rd, and so on up to person 100. How many lamps end up on?
A hundred lamps is too many to follow in your head. So shrink the puzzle until you can do it on paper.
Example 1.1
Ten lamps first
Run the same walk with 10 lamps and 10 people. Which lamps end up on, and why?
- Run the small caseon: 1, 4, 9
Flip them by hand: only lamps 1, 4 and 9 end on.
- Spot the pattern1 × 1, 2 × 2, 3 × 3
The lamps left on are square numbers. So far that's a guess, not an answer.
- Find the reasonlamp 12: 1 × 12, 2 × 6, 3 × 4
Person p flips lamp n when p divides n. Divisors come in pairs, so most lamps get an even number of flips and end off.
- See why squares differlamp 36: … 4 × 9, 6 × 6
In 6 × 6 the pair is one number, so 36 has 9 divisors and ends on. Only a square has a divisor paired with itself.
AnswerScaled back up, 10 lamps stay on: the squares 1 × 1 up to 10 × 10.
Small cases
Solve the puzzle for the smallest sizes you can do by hand, look for a pattern, then find a reason the pattern has to hold. Small cases suggest an answer. Only a reason confirms it.
Skip the reason and small cases can fool you. Join every pair of points on a circle with a straight line, no three lines meeting at a point. 1 to 5 points cut the circle into 1, 2, 4, 8 and 16 regions. 6 points give 31.
Your turn
Run the same walk with 1,000 lamps and 1,000 people. How many lamps end up on?
Part 2. Draw it
Draw the puzzle, sort its pieces into types, and count each type.
Guess first
A wooden cube is painted on all six faces, then cut into 27 equal small cubes, 3 along each edge. How many small cubes have exactly two painted faces?
Holding 27 cubes in your head is hard. A sketch helps, because each kind of small cube sits in its own kind of place: a corner, an edge, the middle of a face, or the inside.
Example 2.1
The painted cube, by place
Sort all 27 small cubes by how many painted faces they have.
- Corners8 cubes, 3 faces each
A cube has 8 corners, and a corner piece touches three outside faces.
- Edges12 × 1 = 12 cubes, 2 faces each
Each edge holds 3 pieces: two corners, and 1 in the middle that touches two faces.
- Face centres6 × 1 = 6 cubes, 1 face each
The middle of each face touches only that face.
- Inside1 cube, no paint
The very centre touches nothing outside.
- Check the total8 + 12 + 6 + 1 = 27
So nothing was missed or counted twice.
Answer12 small cubes have exactly two painted faces.
Casework
Split everything into types that don't overlap and that cover every case, then count each type. If the counts add up to the total, you haven't missed a case or counted one twice.
The usual slip is to count only what the sketch shows. The three hidden faces count too, so count from the cube's 8 corners, 12 edges and 6 faces, not from the picture.
Your turn
Now cut a painted cube into 64 small cubes, 4 along each edge. How many have exactly one painted face?
Part 3. Push to an extreme
Test a puzzle at an extreme value, such as zero, where the answer is easy to see.
Guess first
A rope fits tightly round a ball as big as the Earth, about 40,000 km round. You want it to float 1 metre above the surface all the way round. Roughly how much rope must you add?
Suppose the extra rope doesn't depend on the ball's size. Then you can pick the size that makes the puzzle easiest: the smallest one.
Example 3.1
A rope round a ball of any size
How much rope does it take to lift a tight rope 1 metre off a ball of any size?
- Shrink the ball to a pointradius 0
A ball of radius 0 is a point, and a tight rope round it has length 0.
- Lift the rope 1 metre2π × 1 ≈ 6.28 m
The rope is now a circle of radius 1 metre. A circle is 2π times its radius round, where π, read "pi", is about 3.14.
- Check every size2π(r + 1) − 2πr = 2π
Call the ball's radius r. The rope grows from 2πr to 2π(r + 1). The r cancels, so every ball needs the same 6.28 metres.
AnswerAbout 6.28 metres, for a ball of any size.
Extreme case
Set a quantity to an extreme, often 0, where the puzzle gets easy. If the answer can't depend on that quantity, the easy case gives the answer. If it can, the easy case is still a check.
The trick needs an answer that stays put as the quantity moves. The rope's total length depends on the ball, so radius 0 says nothing about it. Say why the answer can't change before you push.
Your turn
A square field has a fence round it. A second square fence runs 1 metre outside the first all the way round. How much longer is the outer fence?
Part 4. Say it out loud
State your assumptions, try a case and check your answer, out loud as you go.
Guess first
Two cables are 130 metres long together. One is 100 metres longer than the other. How long is the shorter one?
If 30 came first, a spoken check catches it: "30 plus 130 is 160." In an interview, how you get there counts along with what you get, and thinking out loud lets the interviewer follow and steer you.
Example 4.1
A knockout of 50 players, out loud
50 players enter a knockout. Each match has one winner, and the loser leaves. How many matches until one player is left?
- Restate and assumeno draws; an odd one out waits
Say it: "With an odd number in a round, I'll assume one player sits it out." A wrong assumption gets corrected now, before it costs you.
- Try a small case4 players: 2 + 1 = 3 matches
Two semi-finals and a final. 5 players take 4. The matches look like one fewer than the players.
- Find the reason50 − 1 = 49
Every match knocks out exactly one player, and 49 players must go.
- Check another way25 + 12 + 6 + 3 + 2 + 1 = 49
Count round by round: 50, 25, 13, 7, 4, 2 and 1 players left. The two ways agree.
Answer49 matches.
Sanity check
A quick test that an answer could be right: put it back into the puzzle, compare it with a small case, or count another way. Do it out loud, before you give the number.
If the interviewer says an assumption is wrong, that's help, not a fail. Change it out loud and carry on. If you're stuck, say which way in you'll try next.
Your turn
A slab of 24 tiles, 6 by 4, is joined together. Each snap breaks one piece into two along a line between tiles. How many snaps does it take to get 24 single tiles?
Where you'll meet it
Many quant trading and research interviews include a puzzle you won't have seen. The interviewer watches how you start: restate it, try the smallest case, sketch it, test an extreme. A clear path that needs one hint often says more than a bare right number.
Engineers use small cases the same way: a fast formula is checked against a slow, plainly correct version on every small input. For the lamps, the fast formula is the whole-number square root, isqrt(n) in Python. When the two disagree, the smallest failing input points to the bug.
from itertools import combinations
from math import isqrt
def lamps_on(n): # n people walk past n lamps
lamp = [False] * (n + 1)
for person in range(1, n + 1):
for k in range(person, n + 1, person):
lamp[k] = not lamp[k]
return [k for k in range(1, n + 1) if lamp[k]]
print(lamps_on(100)) # [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
print(all(len(lamps_on(n)) == isqrt(n) for n in range(1, 301))) # True
n = 3 # the painted cube
faces = [(x in (0, n - 1)) + (y in (0, n - 1)) + (z in (0, n - 1))
for x in range(n) for y in range(n) for z in range(n)]
print([faces.count(k) for k in (3, 2, 1, 0)]) # [8, 12, 6, 1]
def regions(n): # n points on a circle, all joined
lines = list(combinations(range(n), 2))
# two lines cross inside the circle when their ends alternate round it
crossings = sum(len({a, b, c, d}) == 4 and (a < c < b) != (a < d < b)
for (a, b), (c, d) in combinations(lines, 2))
return 1 + len(lines) + crossings
print([regions(n) for n in range(1, 7)]) # [1, 2, 4, 8, 16, 31]Check yourself
Four questions from across the lesson. Try each one before you look back.
1
Ten players each play every other player once. A quick answer says 10 × 9 = 90 games. Check it on 3 players first. How many games are there really?
2
Two equal jars hold water and juice. Move a spoonful of water into the juice and stir, then move a spoonful of the mix back. Is there more juice in the water jar, or more water in the juice jar?
3
Points on a circle, every pair joined, no three lines through one point: 1, 2, 3, 4 and 5 points give 1, 2, 4, 8 and 16 regions. How many with 6 points?
4
A painted cube is cut into 1,000 small cubes, 10 along each edge. How many have at least one painted face?
What to remember
1Try small cases
Work small cases, then find the reason: 10 of 100 lamps stay on, the squares, because only squares have an odd number of divisors.
1Try small cases
Small cases only suggest: points on a circle give 1, 2, 4, 8 and 16 regions, and then 31.
2Draw it
Draw it, sort the pieces by type, and check the types add up: 8 + 12 + 6 + 1 = 27 small cubes.
3Push to an extreme
Push a quantity to an extreme when the answer can't depend on it: a rope 1 metre above any ball needs 2π ≈ 6.28 metres more.
4Say it out loud
Say assumptions, cases and checks out loud: 50 players need 49 knockout matches, and counting by rounds confirms it.
Puzzles and Brainteasers overviewSpotted a mistake? Tell us.