insideout Get Pro

01 · A puzzle you've never seen

Free

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?

10: lamps 1, 4, 9, 16, 25, 36, 49, 64, 81 and 100, the square numbers. The example finds them.

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?

  1. Run the small caseon: 1, 4, 9

    Flip them by hand: only lamps 1, 4 and 9 end on.

  2. Spot the pattern1 × 1, 2 × 2, 3 × 3

    The lamps left on are square numbers. So far that's a guess, not an answer.

  3. 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.

  4. 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.

5 points: 16 regions6 points: 31, not 32
5 points: 16 regions6 points: 31, not 32
Figure 1Doubling looks certain after five points and fails at six. Each line adds one region, plus one for each line it crosses. Six points make 15 lines and 15 crossings, so 1 + 15 + 15 = 31.

Your turn

Run the same walk with 1,000 lamps and 1,000 people. How many lamps end up on?

The lamps left on are the squares up to 1,000: 31 × 31 = 961 is in range and 32 × 32 = 1,024 is not. The answer 100 scales up the ten from before, but squares thin out.

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?

12: one in the middle of each of the cube's 12 edges. The 8 corner pieces have three painted faces, not two.

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.

  1. Corners8 cubes, 3 faces each

    A cube has 8 corners, and a corner piece touches three outside faces.

  2. Edges12 × 1 = 12 cubes, 2 faces each

    Each edge holds 3 pieces: two corners, and 1 in the middle that touches two faces.

  3. Face centres6 × 1 = 6 cubes, 1 face each

    The middle of each face touches only that face.

  4. Inside1 cube, no paint

    The very centre touches nothing outside.

  5. Check the total8 + 12 + 6 + 1 = 27

    So nothing was missed or counted twice.

Answer12 small cubes have exactly two painted faces.

corner: 3 faces8 of themedge middle: 212 of themface centre: 16 of themplus 1 hidden in the middle: 8 + 12 + 6 + 1 = 27
orange: edge middles, 2 faces (12)corners: 3 faces (8)face centres: 1 face (6)hidden middle: none (1)
Figure 2Each kind of small cube sits in its own kind of place. The orange ones, one in the middle of each edge, have two painted faces. Three of the edges are out of sight at the back.

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?

Each face has a 2 by 2 block in its middle, away from the edges: 6 × 4 = 24. Check: 8 corners + 24 edge pieces + 24 + 8 inside = 64. The answer 96 counts every square on every face, so edge and corner pieces count twice or more.

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?

About 6.28 metres, whatever the size of the ball, as the example shows.

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?

  1. Shrink the ball to a pointradius 0

    A ball of radius 0 is a point, and a tight rope round it has length 0.

  2. 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.

  3. 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?

Shrink the field to a point: the outer fence is a 2 by 2 square, 8 metres round. For any side s, each side becomes s + 2, and 4(s + 2) − 4s = 8. The answer 4 adds 1 metre per side, but each side grows at both ends.

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?

15 metres. The fast answer, 30, fails a check: 30 and 130 make 160, not 130. With 15, the other is 115, and 15 + 115 = 130.

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?

  1. 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.

  2. 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.

  3. Find the reason50 − 1 = 49

    Every match knocks out exactly one player, and 49 players must go.

  4. 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?

Each snap turns one piece into two, so the count of pieces goes up by exactly one. From 1 piece to 24 takes 23 snaps, in any order. The answer 8 counts the 5 + 3 lines between tiles, but a line across several pieces takes several snaps.

Where you'll meet it

In interviews

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.

On the job

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.

Check the puzzles by brute force
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?

3 players play 3 games, but 3 × 2 gives 6, counting each game once for each of its players. So halve it: 10 × 9 / 2 = 45. The answer 55 also counts a game of each player against themselves.

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?

Make the spoon a whole jar: the mix is half and half, a jar of it comes back, and each jar holds half of the other. For any spoon, each jar ends as full as it began, so the water that left was replaced by the same amount of juice.

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?

31: 15 lines and 15 crossings, so 1 + 15 + 15 = 31. The answer 32 trusts the doubling pattern without a reason. 30 is what six evenly spaced points give, because three lines then meet in the middle.

4

A painted cube is cut into 1,000 small cubes, 10 along each edge. How many have at least one painted face?

Count the unpainted ones: an inner cube 8 along each edge, 8 × 8 × 8 = 512. So 1,000 − 512 = 488. The answer 600 is 6 faces × 100 squares, which counts edge and corner pieces two or three times.

What to remember

  1. 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.

  2. 1Try small cases

    Small cases only suggest: points on a circle give 1, 2, 4, 8 and 16 regions, and then 31.

  3. 2Draw it

    Draw it, sort the pieces by type, and check the types add up: 8 + 12 + 6 + 1 = 27 small cubes.

  4. 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.

  5. 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.