How to prove something is impossible in a competition

Proving that something is possible and proving that it is impossible are not two difficulties of the same task. They are different tasks, and only one of them can be finished by being clever with the object in front of you.

To show a thing is possible, you exhibit one. One tiling, one number, one construction, and the question is closed forever. To show a thing is impossible, exhibiting anything is useless, because you have to rule out every attempt at once, and there are usually infinitely many attempts. No amount of good work on the object gets you there. You need something that talks about all the objects simultaneously.

That something has a name and a fixed shape, and once you know the shape, "prove this cannot be done" stops being the scariest sentence on the paper and becomes the most mechanical.

The move that feels like a proof and is not

Two things students write when a competition asks them to prove something is impossible, both of which score zero:

• "I tried for twenty minutes and could not find one."
• "I checked all the cases up to a thousand and none worked."

Both are evidence about which side of the question you are on. Neither is an argument. The second one is worth dwelling on, because it feels so much more rigorous than it is. No fraction with denominator up to two thousand squares to exactly 2, and that fact is a genuine computation with a genuine result, and it proves precisely nothing about the denominator two thousand and one.

What an impossibility proof actually is

Every one of them is the same three lines. You find a quantity — call it the obstruction — with three properties:

1. You can compute it for any candidate, without knowing which candidate.
2. It takes one value on everything the rules permit.
3. It takes a different value on the thing you were asked to rule out.

Then nothing permitted can be the target, and you are done. Notice that step 1 is what makes the argument cover infinitely many attempts for the same price as one: you never look at a candidate, you look at a number attached to every candidate at once.

So the search is not for a solution. It is for a quantity that separates.

The ladder of obstructions

They come in a rough order of cost, and you should try them in this order, because the cheap ones are cheap and they work more often than people expect.

One: count. The crudest obstruction is size. A $5 \times 5$ board cannot be tiled by dominoes because $25$ is odd and every domino covers two squares. That is a complete proof, and it took one sentence.

Two: a residue. When the counts match, ask whether some quantity is fixed modulo a small number. No sum of two integer squares is ever $3$ more than a multiple of $4$, because squares are $0$ or $1$ modulo $4$ and no two of those add to $3$. Any problem asking you to write $4k+3$ as $x^2 + y^2$ dies right there, for every $k$ at once.

Three: a colouring. A colouring is a modulus you had to invent, and it is the step where impossibility problems get interesting. Remove two opposite corners from a chessboard and try to tile the rest with dominoes: counting clears it completely, since $62$ squares is exactly $31$ dominoes' worth, and an argument that stops at counting concludes the wrong thing. Colour the board the way a chessboard is already coloured, and a domino covers one square of each colour wherever you put it — all $112$ placements. The two removed corners are the same colour as each other, so what remains is $32$ of one colour and $30$ of the other, and $31$ dominoes need $31$ of each. Impossible.

Four: a structural divisibility fact. Sometimes the obstruction is a theorem rather than a count. If $P$ has integer coefficients then $m - n$ divides $P(m) - P(n)$ for all integers $m, n$, and that single fact is enough to prove a polynomial taking the value 1 at three distinct integers has no integer root. The obstruction is a divisibility that every integer-coefficient polynomial satisfies whether it wants to or not.

Five: descent. When nothing is fixed, look for something that must strictly decrease. Assume a counterexample exists, build a smaller one from it, and note that the positive integers have no infinite descending chain. The irrationality of $\sqrt2$ is this: the parity step turns any fraction equal to $\sqrt2$ into one with a smaller denominator, and a smallest denominator was assumed. Descent is the expensive rung, so reach for it last.

The test that tells you which rung you are on

Compute your candidate obstruction twice: once on the target, once on anything the rules allow. If the two values differ, you have a proof and you should stop looking. If they agree, the obstruction is too coarse, and you go one rung finer.

That is exactly what happens on the mutilated board. Counting gives $62$ on the target and $62$ on a legal tiling, agreement, so counting is too coarse. Colour parity gives $32$ against $30$ on the target and a dead heat on any tiling. Disagreement, so it is over.

The same fork settles whether every token on a $5 \times 5$ grid can move to an adjacent square at once. Twenty-five tokens onto twenty-five squares is a perfect match by counting. But the colouring splits the grid $13$ against $12$, and an orthogonal step always lands on the other colour, so thirteen tokens need thirteen destinations of a colour that only has twelve squares. The counting rung says nothing; the colouring rung ends it in a line.

Find all is half an impossibility proof

The most common place this skill is tested is not a problem containing the word impossible. It is a problem that says determine all.

"Find all $n$ such that …" is two tasks stapled together: exhibit the ones that work, then prove nothing else does. The first half is arithmetic and most people do it well. The second half is an impossibility proof about every value you did not list, and it is where the marks actually go. A solution that lists the right answers with no argument that the list is complete is a conjecture with good numbers in it.

So when you finish a find all, ask the question this whole page is about: what is the obstruction that kills everything not on my list? If you cannot name one, you have not finished.

What to practise

Take ten problems whose answer is "no" and, without solving any of them, write one line each: what quantity separates the target from everything legal. You will be wrong often, and being wrong quickly on the counting rung before climbing is the actual skill.

Lemma treats this as two named techniques rather than two tricks you happen to meet: invariants for the quantity that never changes, and colourings for the one you have to build. The problem archive has the boards and the polynomials above with full statements and expected times, the daily problem posts a fresh one every day in three tiers with no account needed, and the other guides cover the neighbouring recognition questions.