On this page
After twenty minutes of trying to tile a board or flip some cups, you suspect it cannot be done. Many olympiad problems want exactly that proof, and trying cases cannot give it. A parity argument often can, in three lines.
What is a parity argument in maths?
The parity of a whole number is whether it is odd or even. A parity argument picks a count in the problem, shows that every allowed move keeps its parity fixed, and notes that the goal has the other parity. If every reachable position gives an even count and the goal needs an odd one, you never get there.
Parity is the simplest kind of invariant, a quantity that does not change as you play; see the invariant method in olympiad mathematics for the general idea.
How does the domino chessboard problem prove impossibility?
The philosopher Max Black posed this puzzle in his 1946 book Critical Thinking, according to the Wikipedia article on the mutilated chessboard problem. Remove two diagonally opposite corners from an 8 by 8 chessboard. Can 31 dominoes, each covering two adjacent squares, cover the remaining 62 squares?
Counting squares does not settle it, because 31 times 2 is 62. Colour does. Opposite corners are the same colour, so the cut board has 30 squares of one colour and 32 of the other. Neighbouring squares always differ in colour, so every domino covers one dark and one light square, and 31 dominoes cover exactly 31 of each. The board needs 30 and 32. No tiling exists.
A proof by Ralph Gomory, published in 1973, covers the reverse case: remove any two squares of opposite colours and the rest can always be tiled (same source).
Why is the number of people with an odd handshake count always even?
At any party, add up how many hands each person shook. Every handshake involves two people, so it adds exactly 2 to that total. The sum is therefore twice the number of handshakes, which is even. This is the handshaking lemma, which Leonhard Euler first proved in his 1736 paper on the Königsberg bridges problem.
The even counts add to an even number, so the odd counts must too, and a sum of odd numbers is even only when there are an even number of them. So the number of people who shook an odd number of hands is always even: every graph has an even number of odd-degree vertices. Euler's original puzzle is in our post on the Seven Bridges of Königsberg and the start of graph theory.
How do you spot a parity problem in an olympiad?
Use this four-step check whenever a question asks "is it possible?":
Find the move: one tile placed, two cups flipped, one handshake made.
Find something to count: squares of each colour, cups facing up, a sum of numbers.
Ask what one move does to that count's parity. If it always adds an even number, parity is fixed.
Compare start and goal. If their parities differ, it is impossible. Write the proof in three sentences: the invariant, why moves preserve it, why the goal breaks it.
If nothing useful to count turns up, parity may be the wrong tool; the extremal principle may fit better.
Four worked parity problems to try
Cover each solution and try for five minutes first.
Seven cups stand upside down. Each move flips exactly two cups. Can all seven end up upright? Solution: count the upright cups. A move changes that count by +2, 0 or -2, so it stays even. It starts at 0 and the goal is 7, which is odd. Impossible.
Can nine people each shake hands with exactly three others? Solution: the handshake counts add to 9 times 3, which is 27 and odd, but that sum must be twice the number of handshakes. Impossible.
Can a knight return to its starting square in an odd number of moves? Solution: every knight move changes colour, so getting back needs an even number of moves. Impossible.
The numbers 1 to 10 are written on a board. Each step, erase two numbers and write the larger minus the smaller. Can the last number left be 0? Solution: replacing a and b by their difference lowers the total by twice the smaller one, an even amount. The total starts at 55, which is odd, so the last number is odd. It cannot be 0.
For real papers, HBCSE posts past RMO, INMO and IOQM papers with solutions or answer keys.
If you get stuck on a step, the Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer, so you can see where the invariant comes from. For a refresher on graphs and degrees, each idea has its own lesson in the Fermi Concept Library.
