# Puzzles and Brainteasers

The methods behind the logic puzzles in quant interviews.

URL: https://insideout.sh/courses/puzzles
Updated: 2026-11-12T09:52:14Z

## Lessons

1. [A puzzle you've never seen](https://insideout.sh/courses/puzzles/01): Ways in when a puzzle looks like nothing you know. Free.
2. [Invariants and parity](https://insideout.sh/courses/puzzles/02): Prove a goal is impossible by finding what never changes. Free.
3. [The pigeonhole principle](https://insideout.sh/courses/puzzles/03): More items than boxes means some box holds two. Free.
4. [Weighings and information](https://insideout.sh/courses/puzzles/04): Count what each test can tell apart to find the fewest tests. Pro.
5. [Working backwards](https://insideout.sh/courses/puzzles/05): Solve the last move first, then the one before it. Pro.
6. [Games with winning positions](https://insideout.sh/courses/puzzles/06): Find the positions you want to leave your opponent. Pro.
7. [Search and worst cases](https://insideout.sh/courses/puzzles/07): The fewest tries that work even when luck is against you. Pro.
8. [Number puzzles](https://insideout.sh/courses/puzzles/08): Work out number puzzles in your head with remainders. Pro.
9. [Mixed puzzles, worked](https://insideout.sh/courses/puzzles/09): Puzzles of every kind, and how to tell which method fits. Pro.

## Lesson 1: A puzzle you've never seen

URL: https://insideout.sh/courses/puzzles/01
Updated: 2026-11-12T09:52:14Z
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.

By the end, you can:
1. Work small cases to find a pattern, then find the reason it holds.
2. Draw the puzzle, sort its pieces into types, and count each type.
3. Test a puzzle at an extreme value, such as zero, where the answer is easy to see.
4. State your assumptions, try a case and check your answer, out loud as you go.

### Part 1. Try small cases

**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. 1
B. 0
C. 10
D. 50
Answer: C. 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**
Problem: Run the same walk with 10 lamps and 10 people. Which lamps end up on, and why?
1. Run the small case: on: 1, 4, 9 (Flip them by hand: only lamps 1, 4 and 9 end on.)
2. Spot the pattern: 1 × 1, 2 × 2, 3 × 3 (The lamps left on are square numbers. So far that's a guess, not an answer.)
3. Find the reason: lamp 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 differ: lamp 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.)
Answer: Scaled 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.

Figure 1: Doubling 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?
A. 31
B. 100
C. 500
D. 32
Answer: A. 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

**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?
A. 6
B. 8
C. 24
D. 12
Answer: D. 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**
Problem: Sort all 27 small cubes by how many painted faces they have.
1. Corners: 8 cubes, 3 faces each (A cube has 8 corners, and a corner piece touches three outside faces.)
2. Edges: 12 × 1 = 12 cubes, 2 faces each (Each edge holds 3 pieces: two corners, and 1 in the middle that touches two faces.)
3. Face centres: 6 × 1 = 6 cubes, 1 face each (The middle of each face touches only that face.)
4. Inside: 1 cube, no paint (The very centre touches nothing outside.)
5. Check the total: 8 + 12 + 6 + 1 = 27 (So nothing was missed or counted twice.)
Answer: 12 small cubes have exactly two painted faces.

Figure 2: Each 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?
A. 96
B. 24
C. 16
D. 6
Answer: B. 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

**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?
A. About 6,000 kilometres
B. About 6 kilometres
C. About 1 metre
D. About 6 metres
Answer: D. 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**
Problem: 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 point: radius 0 (A ball of radius 0 is a point, and a tight rope round it has length 0.)
2. Lift the rope 1 metre: 2π × 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 size: 2π(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.)
Answer: About 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?
A. 8 metres
B. About 6.28 metres
C. 4 metres
D. It depends on the field's size
Answer: A. 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

**Guess first:** Two cables are 130 metres long together. One is 100 metres longer than the other. How long is the shorter one?
A. 65 metres
B. 100 metres
C. 30 metres
D. 15 metres
Answer: D. 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**
Problem: 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 assume: no 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 case: 4 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 reason: 50 − 1 = 49 (Every match knocks out exactly one player, and 49 players must go.)
4. Check another way: 25 + 12 + 6 + 3 + 2 + 1 = 49 (Count round by round: 50, 25, 13, 7, 4, 2 and 1 players left. The two ways agree.)
Answer: 49 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?
A. 23
B. 8
C. 24
D. 10
Answer: A. 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.

```python
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

**Question 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?
A. 55
B. 45
C. 100
D. 90
Answer: B. 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.

**Question 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?
A. The same amount
B. More water in the juice jar
C. It depends on the spoon's size
D. More juice in the water jar
Answer: A. 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.

**Question 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?
A. 64
B. 30
C. 31
D. 32
Answer: C. 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.

**Question 4.** A painted cube is cut into 1,000 small cubes, 10 along each edge. How many have at least one painted face?
A. 512
B. 488
C. 600
D. 384
Answer: B. 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. 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. Small cases only suggest: points on a circle give 1, 2, 4, 8 and 16 regions, and then 31.
3. Draw it, sort the pieces by type, and check the types add up: 8 + 12 + 6 + 1 = 27 small cubes.
4. 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. Say assumptions, cases and checks out loud: 50 players need 49 knockout matches, and counting by rounds confirms it.

Next: Next, puzzles that ask whether something can be done at all, settled by a quantity that no move can change.

## Lesson 2: Invariants and parity

URL: https://insideout.sh/courses/puzzles/02
Updated: 2026-11-12T09:52:14Z
Prove a goal is impossible by finding what never changes.

Some puzzles ask whether a goal can be reached at all. Trying moves until you give up proves nothing, since the next try might work. This lesson shows how to prove a goal is out of reach, and a plan that puts the same idea to work. You only need to know odd from even.

By the end, you can:
1. Prove a goal is impossible by finding a quantity that no move can change.
2. Rule out a tiling by colouring the board so each piece covers a fixed mix of colours.
3. Share the parity of a hidden count so each person can work out the one piece they can't see.

### Part 1. What never changes

**Guess first:** The numbers 1 to 10 are on a board. A move wipes out any two numbers and writes their difference, bigger minus smaller. After 9 moves one number is left. What can it be?
A. Any odd number from 1 to 9
B. Any number from 0 to 10
C. Any even number
D. Always 1
Answer: A. It's always odd, and each of 1, 3, 5, 7 and 9 can happen. The example shows why it can never be even, without playing a single game.

You could play a hundred games, get an odd number every time, and still not know that the next game can't end on 0. To rule a result out, look for something that every move leaves alone.

**Example 1.1: The difference game**
Problem: Show that the last number on the board can never be even.
1. Look at what a move does: a, b → a − b (Call the two numbers a and b, with a the bigger. Two numbers go and one comes back, so the count, the largest number and the total can all change.)
2. Watch the total: (a − b) − (a + b) = −2b (The total drops by twice the smaller number, which is always an even amount.)
3. Keep only odd or even: 1 + 2 + … + 10 = 55, odd (Taking away an even amount never turns an odd total even. So the total is odd after every move.)
4. Read the end: last number = total, odd (When one number is left, it is the total.)
Answer: The last number is always odd.

The total itself changes with every move, so it's no use on its own. What survives is whether it's odd or even. Finding the part that survives is the skill this lesson teaches.

**Invariant and parity**: An **invariant** is a quantity that no move can change. **Parity** is whether a whole number is odd or even. If the start and the goal differ in an invariant, no run of moves can get from one to the other.

The trap is building on a quantity that does change. The total, the largest number and the count of numbers all move. Test any candidate on one move before you trust it.

**Your turn:** A jar holds 9 white and 6 black counters, with spare black ones outside. Take out two. If they match, put one black back. If they differ, put one white back. Repeat until one counter is left. What colour is it?
A. White, always
B. Black, always
C. It depends on the order you draw
D. Either, with equal chance
Answer: A. Watch the whites. A move takes out two whites or none, since a mixed pair puts its white back. So the number of whites changes by 0 or 2 and stays odd. It starts at 9, can never reach 0, and the last counter is white.

### Part 2. Colour the board

**Guess first:** Take an 8 by 8 grid of squares and remove two opposite corners, leaving 62. A domino covers two squares side by side. Can 31 dominoes cover the 62 squares exactly, with no overlap?
A. There's no way to know without trying every layout
B. Only if some dominoes lie diagonally
C. Yes
D. No
Answer: D. No. Colour the grid like a chessboard: the two corners removed share a colour, which leaves 30 of one colour and 32 of the other, and every domino covers one of each. No search of layouts is needed.

Counting squares doesn't settle it, because 62 is even and 31 dominoes is the right number. You need a finer count.

**Example 2.1: The grid with two corners gone**
Problem: Show that no layout of 31 dominoes covers the 62 squares.
1. Colour it: dark, light, dark, light, … (Colour the squares like a chessboard, so every square's neighbours are the other colour.)
2. See what a domino covers: 1 dark + 1 light (Its two squares sit side by side, so they differ in colour, wherever it goes.)
3. Count the colours left: 30 dark, 32 light (Opposite corners are the same colour, here dark. Removing both takes two from the 32 dark squares.)
4. Compare: 31 dominoes need 31 + 31 (Any 31 dominoes cover exactly 31 dark squares, and only 30 are left.)
Answer: No layout works.

Figure 1: Opposite corners share a colour, so 30 dark and 32 light squares are left. Every domino, wherever it lies, covers one of each.

The argument never looks at a single layout. It shows that every layout fails at once, which is why it's a proof and a search isn't.

**Colouring argument**: Colour the board so every piece covers the same mix of colours wherever it sits. If the board's colour counts can't match what the pieces cover, no tiling exists.

A colouring can only prove "no". Remove one dark and one light square instead, and the counts match, 31 and 31. That rules nothing out, but it doesn't prove a tiling exists either. You still have to find one.

**Your turn:** A 5 by 5 grid loses one square: the one beside a corner square. Can 12 dominoes cover the 24 squares left?
A. There's no way to know without trying layouts
B. Yes, since 24 is even
C. Yes, in exactly one way
D. No
Answer: D. Colour it like a chessboard with dark corners: 13 dark, 12 light. The square beside a corner is light, so 13 dark and 11 light are left, and 12 dominoes need 12 of each. An even number of squares is needed, but it isn't enough.

### Part 3. Parity as a plan

**Guess first:** Ten people stand in a line facing the front. Each wears a red or blue hat and sees every hat ahead, but not their own or any behind. From the back, each says one word, "red" or "blue", heard by all. They agree a plan beforehand. How many can be sure of naming their own hat?
A. 5
B. None, each is a coin flip
C. 10
D. 9
Answer: D. 9: everyone except the person at the back. One word from the back is enough: whether the red hats ahead of it are odd or even in number.

Nobody sees the back person's hat, so their word can't be sure of it. But it can carry one fact that everyone in front needs. The question is which fact.

**Example 3.1: Five hats in a line**
Problem: Five people use the plan. From the back the hats are unknown, red, blue, red, red. The back person says "red" if they see an odd number of red hats, "blue" if even. Follow each person.
1. The back person: sees 3 reds, odd → "red" (The word describes the hats ahead, so it matches their own hat only half the time.)
2. Person 2: sees 2 reds, even → "red" (The reds from person 2 forward are odd, and they see an even number, so the missing red is their own.)
3. Person 3: 1 named + 2 seen = 3, odd → "blue" (Reds named since the back person spoke, plus reds seen, is already odd, so their own hat is blue.)
4. Persons 4 and 5: 1 + 1 = 2 → "red"; 2 + 0 = 2 → "red" (The same sum each time, reds named plus reds seen: even means their own hat is red, odd means blue.)
Answer: Everyone but the back person names their hat for certain.

Figure 2: The five-hat line. Each person adds the reds named behind them to the reds they see. Since the back person's word said odd, an even sum means their own hat is red.

**Parity bit**: One extra bit that says whether a count is odd or even. If you know a group's parity and can see every member but one, the missing one is fixed.

The tempting plan works in pairs: the back person names the next hat, and its owner repeats it. Only half are then sure. The parity word beats it because it speaks to everyone at once.

**Your turn:** Five people use the same plan. The back person says "red", so they see an odd number of reds. Person 2 sees 2 reds ahead. Person 3 sees 1 red ahead. What do persons 2 and 3 say?
A. Red, then red
B. Blue, then red
C. Red, then blue
D. Blue, then blue
Answer: A. Person 2 sees an even number of reds but was told odd, so their own is red. Person 3 heard 1 red named and sees 1, an even 2, so their own is red too. Blue for person 3 forgets the red named behind them.

### Where you'll meet it

> **In interviews**: When a puzzle asks whether something can be done, it often wants an invariant. Say the quantity you're testing, and check it on one move out loud. Parity comes up with flips, swaps and pairings, colourings with grids and tiles. Prove "no" with the invariant, and prove "yes" by showing one way.

> **On the job**: Disk arrays use the hat trick. RAID 5 stores a parity block beside each group of data blocks: every bit of it records whether the matching bits of the others hold an odd or even number of 1s. When one disk fails, each lost bit is the one value that makes the parity come out right, so the array rebuilds it.

```python
from itertools import product

def endings(nums):                     # every last number the game can reach
    seen, ends, todo = set(), set(), [tuple(nums)]
    while todo:
        s = todo.pop()
        if s in seen:
            continue
        seen.add(s)
        if len(s) == 1:
            ends.add(s[0])
        for i in range(len(s)):
            for j in range(i + 1, len(s)):
                rest = s[:i] + s[i + 1:j] + s[j + 1:]
                todo.append(tuple(sorted(rest + (s[j] - s[i],))))
    return sorted(ends)

print(endings(range(1, 11)))           # [1, 3, 5, 7, 9]

def sure(hats):                        # hats[0] is the back; 1 means red
    said = [sum(hats[1:]) % 2]         # the back person's parity word
    for i in range(1, len(hats)):
        said.append((said[0] - sum(said[1:]) - sum(hats[i + 1:])) % 2)
    return sum(s == h for s, h in zip(said, hats))

print(min(sure(h) for h in product((0, 1), repeat=10)))  # 9
```

The first search plays every possible game, over 7,000 board states, and never ends on an even number. The second tries all 1,024 lines of hats, and at least 9 people are right in every one.

### Check yourself

**Question 1.** Seven coins lie heads up. A move turns over any two of them. Can you get all seven tails up?
A. No: the number of heads stays odd
B. Yes, in 4 moves
C. Yes, if you turn neighbours
D. No: the number of heads never changes
Answer: A. Each move changes the number of heads by −2, 0 or +2, so it stays odd: 7, 5, 3, 1, never 0. The number of heads itself does change, so it can't be the invariant. Its parity is.

**Question 2.** A 4 by 4 grid loses the two end squares of its top row, leaving 14. Can 7 dominoes cover them?
A. No: the colours don't match
B. Yes
C. No: two squares are missing
D. Only with a domino on a diagonal
Answer: B. The two end squares are different colours, so 7 dark and 7 light are left, and the colouring rules nothing out. Then find a layout: one domino fills the middle of the top row, and the full 3 by 4 block below takes six more.

**Question 3.** In the line of 10 using the parity plan, with hats given at random, what's the chance all 10 are right?
A. 9/10
B. 1/2
C. 1
D. 1/1,024
Answer: B. The 9 in front are always right. Only the back person speaks without knowing, and their word matches their own hat half the time. The answer 1/1,024 is ten blind guesses in a row.

**Question 4.** Now hats come in red, blue and green, and each person says one colour. How many of the 10 can be sure of naming their own hat?
A. 3
B. 0
C. 9
D. 6
Answer: C. Number the colours 0, 1 and 2. The back person names the colour whose number is the remainder when the total of the hats ahead is divided by 3. Everyone in front knows every other hat in that total, so only one colour of theirs gives the right remainder. Still 9.

### What to remember

1. An invariant is a quantity no move can change: on the board of 1 to 10 the total starts at 55, odd, and each move takes off an even amount, so the last number is odd.
2. Test a candidate on one move first. The total and the count of numbers both change; only the total's parity survives.
3. Colour the board so every piece covers a fixed mix: a domino covers one dark and one light, and the 8 by 8 grid without opposite corners has 30 and 32.
4. A colouring proves only "no". When the colour counts match, you still have to find a tiling.
5. One parity word from the back of a line of 10 lets the other 9 name their hats for certain.

Next: Next, a counting idea that proves something must happen: put more items than boxes, and some box holds two.

## Lesson 3: The pigeonhole principle

URL: https://insideout.sh/courses/puzzles/03
Updated: 2026-11-12T09:52:14Z
More items than boxes means some box holds two.

Some puzzles ask you to prove that something must happen, however things fall. One idea settles many of them: put more items into boxes than there are boxes, and some box gets two. The skill is choosing the boxes. You need division with remainders and nothing else.

By the end, you can:
1. Find how many items guarantee a match by building the worst case.
2. Choose boxes, such as remainders, so that any two items in one box give what you want.
3. Find the fullest box you can promise when many items share a few boxes.

### Part 1. More items than boxes

**Guess first:** A drawer holds loose socks in 4 colours, plenty of each. In the dark, how many must you take out to be sure of two of the same colour?
A. 8
B. 5
C. 4
D. 2
Answer: B. 5. With 4 you could be unlucky and hold one of each colour. The fifth has to match one of them.

"Be sure" means the answer has to work on your unluckiest day. So don't ask what usually happens. Build the worst draw you can, and see where it breaks.

**Example 1.1: Socks in the dark**
Problem: Find the fewest socks that guarantee a pair, with 4 colours.
1. Name the boxes: 4 colours = 4 boxes (Each sock you draw drops into the box for its colour.)
2. Build the worst case: 1 + 1 + 1 + 1 = 4 socks, no pair (The unluckiest draw puts one sock in each box. So 4 socks guarantee nothing.)
3. Add one more: 5 socks, 4 boxes (Every box already holds a sock, so the fifth lands on top of one. That's a pair.)
Answer: 5 socks.

Both halves matter. The worst case shows 4 isn't enough, and the count shows 5 always is. Together they make 5 the exact answer.

**The pigeonhole principle**: If more items than boxes go into the boxes, some box holds at least two. It promises a crowded box, but not which one.
Rule: k + 1 items in k boxes → some box holds 2

Guaranteed means the worst case, not the likely one. Two socks match a quarter of the time when the colours are equally common, which says nothing about being sure. Change the goal, and the worst case changes with it.

**Your turn:** Now the drawer holds exactly 10 black and 10 white socks. In the dark, how many must you take to be sure of two black socks?
A. 3
B. 4
C. 11
D. 12
Answer: D. The worst case takes all 10 white socks first, then 2 black: 12. Three socks guarantee a pair of some colour, not a black pair. The answer 11 forgets that you need two black ones.

### Part 2. Choose the boxes

**Guess first:** Pick any 6 whole numbers. Must two of them differ by a multiple of 5?
A. Only if some are bigger than 5
B. Yes, always
C. Usually, but not always
D. Only if two are close together
Answer: B. Yes, always. Divide each by 5: there are only 5 possible remainders and 6 numbers, so two share a remainder, and their difference is a multiple of 5.

Here the items are given, but nothing says what the boxes are. You choose them, and the right boxes make "two in one box" mean exactly what the puzzle asks for.

**Example 2.1: Six numbers, five remainders**
Problem: Show that among any 6 whole numbers, two differ by a multiple of 5. Try it on 17, 42, 8, 99, 31 and 60.
1. Choose the boxes: remainders 0, 1, 2, 3, 4 (Divide by 5 and keep the remainder. Every whole number lands in one of these 5 boxes.)
2. Drop the numbers in: 17 → 2, 42 → 2, 8 → 3, 99 → 4, 31 → 1, 60 → 0 (Six numbers, five boxes, so some box gets two. Here it's box 2.)
3. Read the pair: 42 − 17 = 25 = 5 × 5 (Two numbers with the same remainder differ by whole fives, since the remainders cancel when you subtract.)
Answer: Always: two share a remainder, and they differ by a multiple of 5.

Figure 1: Six numbers in five remainder boxes. Two must share a box, and any two in one box differ by a multiple of 5.

**Modulo**: **a mod n**, read "a modulo n", is the remainder when you divide a by n: 42 mod 5 = 2. Two numbers with the same remainder mod n differ by a multiple of n.

Boxes chosen badly prove nothing. Sort the six numbers by size instead, 1 to 20, 21 to 40 and so on, and two may share a box, but their difference can be anything. Before you count, ask what two items in one box would give you.

**Your turn:** Pick any 6 different numbers from 1 to 10. Must two of them add up to 11?
A. Yes, always
B. Only if you pick 7 or more
C. No: 1, 2, 3, 4, 5 and 6 avoid it
D. Only if you pick both 5 and 6
Answer: A. Make the boxes the pairs that add to 11: 1 and 10, 2 and 9, 3 and 8, 4 and 7, 5 and 6. Five boxes, six numbers, so some box gets both its numbers. In 1, 2, 3, 4, 5 and 6, the 5 and 6 add to 11.

### Part 3. The general form

**Guess first:** Drop 5 points anywhere in a square 1 metre on each side, edges included. Must some two of them be no more than 0.71 metres apart?
A. Only if the points fall at random
B. No: they can all be 1 metre apart
C. Yes, always
D. No: put four in the corners and one in the middle
Answer: C. Yes. Cut the square into four smaller squares: two points share one, and two points in a small square are at most 0.71 metres apart. Four corners and the middle are the closest call, every pair at least 0.707 metres apart, still inside the limit.

There are no boxes in sight here, so make some. Cut the square into pieces small enough that any two points in one piece are close.

**Example 3.1: Five points, four small squares**
Problem: Show that some two of any 5 points in the square are no more than 0.71 metres apart.
1. Make 4 boxes: 4 squares, ½ metre on a side (Cut the square in half both ways. A point on a cut line can go in either box.)
2. Count: 5 points, 4 boxes (Some small square holds at least two of the points.)
3. Measure the box: √(½² + ½²) = √2 / 2 ≈ 0.707 m (The farthest apart two points in a small square can be is corner to corner. √2 / 2 is read "the square root of 2, over 2".)
4. Check it's tight: corners + centre: all ≥ 0.707 m (Four corners and the middle keep every pair at least 0.707 metres apart, so no smaller distance can be promised.)
Answer: Yes: some two are at most √2 / 2 ≈ 0.707 metres apart.

Figure 2: Four small squares, five points. Two must share a square, and two points in a small square are never farther apart than its diagonal, about 0.71 metres.

Put in more items and the promise grows. 50 people and 12 birth months guarantee a month shared by at least 5 people, because 12 months of 4 people hold only 48.

**The general pigeonhole principle**: If n items go into k boxes, some box holds at least n / k items, rounded up. ⌈x⌉, read "the ceiling of x", is x rounded up to a whole number: ⌈50 / 12⌉ = 5.
Rule: fullest box ≥ ⌈n / k⌉

The promise is about the fullest box only: some month could still have nobody. And round up, never down. 50 / 12 is about 4.2, and 4 people per month leaves 2 over.

**Your turn:** Drop 9 points in the same 1 metre square, cut into the same four small squares. At least how many points must one small square hold?
A. 3
B. 4
C. 1
D. 2
Answer: A. 9 points in 4 boxes: 9 / 4 = 2.25, rounded up is 3. Four squares of 2 hold only 8, so the ninth makes a 3. The answer 2 rounds down: it's true, but it isn't the most you can promise.

### Where you'll meet it

> **In interviews**: Pigeonhole questions tend to announce themselves with "must", "guarantee" and "at least". The interviewer wants the worst case and a reason. Say the boxes out loud before you count, then show the worst case with one item fewer, so your number is exact.

> **On the job**: No lossless compressor can shrink every file. There are 256 files of exactly 8 bits, but only 255 bit strings shorter than that, counting the empty one. If every 8-bit file got a shorter code, two would share one and couldn't both be restored. The same count says a hash with fewer values than inputs must have collisions.

```python
from itertools import combinations, product

# Socks in 4 colours: 4 socks can all differ, 5 never can
print(any(len(set(s)) == 4 for s in product(range(4), repeat=4)))  # True
print(all(len(set(s)) < 5 for s in product(range(4), repeat=5)))   # True

# 6 numbers: every way to fill the remainders 0 to 4 repeats one
print(all(len(set(r)) < 6 for r in product(range(5), repeat=6)))   # True

# 6 picks from 1 to 10 always hold a pair adding to 11
print(all(any(a + b == 11 for a, b in combinations(s, 2))
          for s in combinations(range(1, 11), 6)))                  # True

# Files of 8 bits against every shorter bit string
print(2 ** 8, sum(2 ** k for k in range(8)))                        # 256 255
```

Brute force can check a promise only when the cases can be listed, as remainders and picks can. For points in a square there are endless cases, and the boxes are the proof.

### Check yourself

**Question 1.** A bag holds counters in 3 colours, plenty of each. How many must you draw, without looking, to be sure of 3 of the same colour?
A. 9
B. 6
C. 4
D. 7
Answer: D. The worst case draws 2 of each colour, 6 counters with no three alike. The seventh makes a three. In the general form, 7 counters in 3 boxes give ⌈7 / 3⌉ = 3. The answer 6 is the worst case itself, one short.

**Question 2.** Pick any 3 whole numbers. Must two of them have an even sum?
A. Only usually
B. Only if one of them is even
C. No: try 1, 2 and 3
D. Yes, always
Answer: D. Use odd and even as the boxes: 3 numbers, 2 boxes, so two share a parity. Two odds or two evens add to an even number. In 1, 2 and 3, the 1 and the 3 add to 4.

**Question 3.** Counting 29 February, a birthday can fall on 366 days. How many people must be in a room to be sure two share a birthday?
A. 366
B. 183
C. 367
D. 23
Answer: C. Sure means the worst case: 366 people could all have different birthdays, so you need 367. With 23 people a shared birthday is only more likely than not, a chance and not a promise.

**Question 4.** At a meeting of 50 people, some pairs shake hands. Must two people have shaken the same number of hands?
A. Only if the number of handshakes is even
B. No: the counts 0 to 49 give 50 different boxes
C. Only if everyone shakes at least one hand
D. Yes, always
Answer: D. The counts run from 0 to 49, which looks like 50 boxes for 50 people. But 0 and 49 can't both happen: someone who shook every hand rules out someone who shook none. So at most 49 boxes are in use, and two people share one.

### What to remember

1. Guaranteed means the worst case: with 4 sock colours the worst draw holds one of each, so 5 socks make a sure pair.
2. Show both halves: a worst case with one item fewer and no match, and the count that forces one.
3. Choose boxes so that two in one box answer the puzzle: with remainders mod 5 as boxes, any 6 whole numbers hold two that differ by a multiple of 5.
4. n items in k boxes put at least ⌈n / k⌉ in some box, and 5 points in four small squares put two within √2 / 2 ≈ 0.71 metres.

Next: Next, finding one odd coin with a balance, by counting what each weighing can tell apart.
