How to Attack a Brainteaser

The frightening part of a brainteaser is not the maths. It is the first fifteen seconds, when you have no idea which of a hundred possible tricks applies and the room is quiet. Strong candidates are not the ones who happen to have seen the puzzle before — they are the ones with a routine they can start running before they know the answer. This is that routine.

1. Pin the rules. Restate the problem in your own words and ask the two or three questions that decide everything: is the coin fair, are the logicians perfect, can I reuse a measurement, do ties count? Interviewers deliberately leave gaps. Filling them out loud is free marks and stops you solving the wrong puzzle.

2. Shrink it. Replace the big parameter with the smallest value that is not trivial. Two islanders instead of a hundred. A 2-by-2 board instead of 8-by-8. Three coins instead of twelve. You are not looking for the answer yet — you are looking for the mechanism.

3. Find the handle. Almost every clean puzzle turns on one quantity: something that never changes (a colour count, a parity, a total), something that only moves one way, a pigeonhole, a symmetry, or a counting bound. Ask directly: what does a legal move do to this number?

4. Guess the shape of the answer. Before computing, say what kind of answer it will be — a yes/no impossibility, a formula in $n$, a threshold, a strategy. Naming the shape narrows the search enormously.

5. Attack it. Test your answer on a case you did not use to build it, and try to construct a counterexample. If it survives, you have a proof sketch. If it dies, you have learned where the mechanism really lives.

Worked example: the mutilated chessboard

Take an 8-by-8 chessboard and cut off two diagonally opposite corners. Can the remaining 62 squares be tiled by 31 dominoes, each covering two adjacent squares?

Pin the rules: dominoes lie flat, cover exactly two edge-adjacent squares, no overlaps, none hanging off. Shrink it: try 2-by-2 with two opposite corners removed. Two squares remain, sitting diagonally — not adjacent, so no domino fits. Impossible, and instantly. Find the handle: what does a domino always do? On a coloured board, a domino covers exactly one black and one white square, every time, no exceptions. That is the invariant. Opposite corners share a colour, so removing them leaves 32 of one colour and 30 of the other. Guess the shape: this is an impossibility answer, one line long. Attack it: 31 dominoes must cover 31 black and 31 white; we have 32 and 30. Contradiction, so no tiling exists — and the argument survives any board size and any two removed squares of the same colour.

Worked example: the 100 light bulbs

One hundred bulbs, all off, in a row. Pass 1 toggles every bulb, pass 2 toggles every second bulb, pass 3 every third, up to pass 100. Which bulbs are on at the end?

Pin the rules: "toggle" means flip whatever state it is in; passes run 1 through 100. Shrink it: do ten bulbs by hand. After all ten passes, bulbs 1, 4 and 9 are lit and the rest are dark. Find the handle: bulb $n$ is toggled once for each pass that divides it — that is, once per divisor of $n$. Starting from off, it ends on exactly when $n$ has an odd number of divisors. Guess the shape: the answer is a set described by a property, and 1, 4, 9 loudly suggests perfect squares. Why? Divisors pair up as $d$ with $n/d$, which cancels them out two at a time — unless $d = n/d$, which happens only when $n$ is a square. Attack it: check $n = 12$ (divisors 1, 2, 3, 4, 6, 12 — six of them, even, off) and $n = 16$ (1, 2, 4, 8, 16 — five, odd, on). So the lit bulbs are the ten perfect squares up to 100.

Run this loop on invariant puzzles, parity arguments, colouring and tiling questions and pigeonhole problems and you will find they are the same five moves wearing different costumes.