A chessboard missing two corners, 31 dominoes.
The mutilated chessboard puzzle: remove two opposite corners from an 8 by 8 board, leaving 62 squares, and try to tile it with 31 dominoes. The counts work. The tiling does not exist, and the one-line proof is the cleanest invariant argument in mathematics.
Take a standard chessboard, 8 squares by 8, and cut off two diagonally opposite corner squares. Sixty-two squares remain. You have 31 dominoes, each exactly the size of two adjacent squares.
Can you cover the 62 squares with the 31 dominoes, no overlaps and no overhang? Prove your answer.
The arithmetic is inviting: 31 dominoes, 62 squares, a perfect match. People who try it spend a long time nearly succeeding, always with two squares left over that are not adjacent. That experience is the puzzle's real content, because "I could not find one" is not a proof, and an interviewer will say so. The question is whether you can show that no arrangement exists without checking any of them. Look at the board itself for something every domino must respect.
Stuck? Open hints one at a time
Each hint gives away one more layer. Stop the moment something clicks.
Hint 1 a nudge
A chessboard has colours. Two diagonally opposite corners are always the same colour. What colours do the remaining 62 squares have?
Hint 2 the key move
Adjacent squares always differ in colour, so a domino covers exactly one dark and one light square, no matter where it lies. Count what 31 dominoes must cover, and compare.
The solution
Reveal the full solution
No tiling exists.
Colour the board in the usual way. Diagonally opposite corners share a colour, so removing them leaves 32 squares of one colour and 30 of the other. Every domino, wherever it is placed, covers two adjacent squares, and adjacent squares always have different colours; so each domino covers exactly one square of each colour. Thirty-one dominoes therefore cover exactly 31 dark and 31 light squares. The board offers 32 and 30. No arrangement can change that, so no arrangement works.
The proof never examines a single placement. It identifies a quantity that every legal move preserves, the difference between dark and light squares covered, notes that the starting position has it wrong, and concludes. That is an invariant argument in its purest form, and it is why this puzzle appears in the first chapter of several textbooks on proof.
What this puzzle is really testing
Whether your instinct on "can this be done" is to search or to look for a conserved quantity. Searching would work here, in the sense that a computer could exhaust every arrangement, but it would teach nothing and would not scale to a 100 by 100 board. The invariant scales to any board and any pair of removed same-colour squares. The same instinct settles the water jugs reachability question with a divisibility invariant and underlies every correctness argument about a loop: find what the loop preserves, check it at the start, read off what must be true at the end. The converging pointers proof is that method applied to real code.
Follow-ups to expect
Remove two squares of different colours from anywhere on the board: now a tiling always exists, a result due to Gomory with a pretty proof using a Hamiltonian cycle through the board. Triominoes instead of dominoes: a different colouring with three colours. And the general lesson the interviewer wants to hear stated: parity and colouring arguments prove impossibility; constructions prove possibility; know which one you are being asked for.