How Do You Prove Something Is Impossible? Find What Never Changes
By the BrainSnail editorial team. How these articles are written and checked, and how to tell us when one is wrong.
Showing that a quantity stays odd or stays even throughout every permitted move proves at a stroke that certain positions can never be reached, however long you try.
The shape of the argument
Find some quantity associated with the situation, show that every allowed move leaves it unchanged in a particular respect, and then observe that the starting position and the target differ in that respect. It follows that no sequence of moves connects them, no matter how many are tried. The quantity most often used is whether something is odd or even, which is why the technique carries that name, and the appeal is that a statement about infinitely many possible sequences is settled by checking a handful of moves.
Classic problems it settles
The same reasoning disposes of several famous puzzles:
- •Covering a chessboard missing two opposite corners with dominoes
- •Which is impossible, since each domino covers one square of each colour
- •And the two removed corners share a colour
- •Sliding puzzles, where half of all arrangements are unreachable
- •Certain configurations of a coin flipping game
- •Knight tours and closed tours on boards of the wrong size
Why it is so satisfying
The technique has a quality that mathematicians describe openly in aesthetic terms, and the reason is the mismatch between the effort and the result. Searching for a solution to the mutilated chessboard could occupy somebody for a very long time and would never finish, because there is nothing to find. The colouring argument takes two sentences and settles it permanently. That asymmetry, between an unbounded search and a short decisive proof, is the appeal of the whole family of arguments, and it is usually a student's first encounter with proving that something cannot be done rather than doing it.
Working through one example
The chessboard case is worth following completely, because seeing it once makes the pattern transferable. A standard board has sixty four squares alternating in colour, thirty two of each. A domino placed anywhere covers two adjacent squares, and adjacent squares always differ in colour, so every domino covers exactly one of each. Any arrangement of dominoes therefore covers equal numbers of the two colours. Removing two diagonally opposite corners removes two squares of the same colour, leaving thirty of one and thirty two of the other, and no arrangement of thirty one dominoes can cover that. The proof is complete and nothing needs to be tried.
The wider family
Oddness and evenness is the simplest case of a much more general strategy that runs through modern mathematics. Any quantity preserved by every allowed operation can play the same role, including a remainder on division by some other number, a colouring with more than two colours, a total that stays constant, or a more abstract property of a structure. Topology is built almost entirely on quantities that do not change when a shape is deformed, which is how one proves that a sphere and a doughnut are genuinely different. The technique here is the accessible entry point to that whole way of thinking.
The takeaway
Identifying a quantity that every allowed move leaves alone, and showing the start and target differ in it, proves no sequence of moves connects them. Colouring a chessboard settles the mutilated board puzzle in two sentences where searching would never finish. The same strategy generalises to any preserved quantity, which is the foundation of topology.