Puzzles
Invariants & Parity
These puzzles are solved by finding something that never changes, no matter how the process unfolds, and comparing that fixed quantity between the starting point and the goal. When the invariant doesn't match, no sequence of moves can ever bridge the gap, which proves impossibility without checking a single possibility.
1. Chessboard Domino Tiling
You have a standard 8 by 8 chessboard and a supply of dominoes, each covering exactly two adjacent squares.
Rules
- Each domino covers 2 adjacent squares
- Every square is covered exactly once
- Dominoes can't overlap or hang off the board
Your task — Determine whether the full 64-square board can be completely tiled, and explain why using the board's coloring.
Difficulty — Easy
Hint 1 — Color the board like a checkerboard.
Hint 2 — Each domino covers one of each color.
Hint 3 — Compare the count of each color.
Main idea — Since every domino, wherever it's placed, always covers exactly one black square and one white square, the board can only be fully tiled if it has equal numbers of both colors, which the standard chessboard does.
Solution
- Color the 64 squares in the usual alternating pattern, giving 32 black and 32 white squares.
- Every domino placement covers one black and one white square, no matter where it's placed or how it's oriented.
- Since the board has exactly 32 of each color, exactly 32 dominoes can cover the entire board with no leftover squares.
Reasoning
The color counts are an invariant that never changes no matter how the dominoes are arranged, since each domino always uses one of each.
Because the full board has equal counts of each color, a complete tiling is possible, and this same coloring idea becomes the key to proving impossibility in boards where the counts aren't equal.
2. The Mutilated Chessboard
Take a standard 8 by 8 chessboard and remove two opposite corner squares, leaving 62 squares. You have 31 dominoes, each covering exactly two adjacent squares.
Rules
- Two opposite corners are removed
- 62 squares remain to be covered
- Each domino covers 2 adjacent squares
Your task — Determine whether the 31 dominoes can completely tile the remaining 62 squares, and prove your answer.
Difficulty — Medium
Hint 1 — Check the color of each removed corner.
Hint 2 — Opposite corners share the same color.
Hint 3 — Count each color among what's left.
Main idea — The two opposite corners of a standard chessboard are always the same color, so removing them leaves an unequal number of black and white squares, which no arrangement of dominoes can ever cover completely.
Solution
- On a standard chessboard, opposite corners are always the same color, say both black.
- Removing both leaves 30 black squares and 32 white squares, a difference of 2.
- Since every domino must cover one black and one white square, no set of dominoes can ever cover 30 black and 32 white squares evenly, so a complete tiling is impossible.
Reasoning
The invariant from the full board, that every domino covers one square of each color, can't change no matter how cleverly the dominoes are placed, so a complete tiling always requires equal numbers of both colors.
Since removing two same-colored corners breaks that balance permanently, no possible arrangement of dominoes can ever tile the mutilated board, proving impossibility without checking every placement.
3. Odd or Even Coin Flipping
6 coins are arranged in a row, all showing heads. On each move, you must flip exactly 3 coins of your choosing, changing each from heads to tails or tails to heads.
Rules
- Exactly 3 coins are flipped per move
- Coins can be chosen freely each move
- Any number of moves is allowed
Your task — Determine whether all 6 coins can be turned to tails, prove it using parity, and give a working sequence if so.
Difficulty — Medium
Hint 1 — Count the number of tails.
Hint 2 — Each move changes it by an odd amount.
Hint 3 — Reaching an even target needs even moves.
Main idea — Since flipping exactly 3 coins always changes the number of tails by an odd amount, the parity of the tails count flips every move, so reaching an even target requires an even number of moves.
Solution
- Flip coins 1, 5, 6 then flip coins 2, 5, 6. Together this turns coins 1 and 2 to tails, while coins 5 and 6 are each flipped twice and stay heads.
- Repeat the same trick for coins 3 and 4, using 5 and 6 as helpers again: flip 3, 5, 6, then flip 4, 5, 6, turning 3 and 4 to tails while 5 and 6 return to heads.
- Finally flip 5, 1, 2, then flip 6, 1, 2: this turns 5 and 6 to tails, while 1 and 2, already tails, are each flipped twice and stay tails, completing all 6 coins as tails in 6 total moves.
Reasoning
Each pair of moves sharing two helper coins flips exactly the two coins that are not shared, leaving the two helper coins flipped twice and therefore unchanged, which is the trick that lets you target any two coins precisely using only 3-coin moves.
Chaining three such paired moves, reusing coins 5 and 6 as helpers, flips every one of the 6 coins exactly once overall, proving not just that the parity allows a solution, but that an explicit one actually exists.
4. Light Bulb Switching
100 light bulbs, numbered 1 through 100, all start off. A worker makes 100 passes. On pass number k, the worker toggles the switch of every bulb whose number is a multiple of k.
Rules
- Bulbs start off, numbered 1 through 100
- On pass k, toggle every multiple of k
- 100 passes are made in total
Your task — Determine which bulbs end up on after all 100 passes.
Difficulty — Medium
Hint 1 — Count how many times each bulb toggles.
Hint 2 — That count equals its divisor count.
Hint 3 — Most numbers have an even divisor count.
Main idea — A bulb ends up on only if it's toggled an odd number of times, and the number of times bulb n is toggled equals its number of divisors, which is odd only for perfect squares.
Solution
- Bulb number n is toggled once for every divisor of n, since pass k toggles bulb n exactly when k divides n.
- Divisors of most numbers pair up, since if d divides n then so does n divided by d, giving an even count unless d equals n divided by d, which happens only when n is a perfect square.
- So only the bulbs at perfect square positions, 1, 4, 9, 16, and so on up to 100, end up toggled an odd number of times and remain on.
Reasoning
Every divisor d of n pairs naturally with n divided by d, and these two are different unless n is a perfect square, in which case one divisor pairs with itself, leaving an odd total count.
Since a bulb ends up on only when flipped an odd number of times, and the flip count exactly equals the divisor count, only perfect square bulb numbers, 10 of them between 1 and 100, remain lit.
5. The Colored Tiles Problem
You want to tile a 10 by 10 floor completely using 1 by 4 tiles, each covering exactly 4 cells in a single row or column, with no overlaps or gaps.
Rules
- Tiles are 1 by 4, horizontal or vertical
- Every cell is covered exactly once
- Tiles can't overlap or hang off the floor
Your task — Determine whether this tiling is possible, even though the area, 100 cells, divides evenly by 4.
Difficulty — Hard
Hint 1 — Area dividing evenly isn't enough.
Hint 2 — Color columns in 4 repeating stripes.
Hint 3 — Compare how each color is covered.
Main idea — Coloring the floor's columns in four repeating stripes reveals that horizontal and vertical tiles interact with the colors so differently that the resulting color counts can never actually be matched, even though the total area works out evenly.
Solution
- Color each column by its position modulo 4, giving color counts of 30, 30, 20, and 20 cells across the four colors, since the 10 columns split unevenly into that repeating pattern.
- Every horizontal tile spans all 4 colors exactly once, while every vertical tile covers exactly 4 cells of a single color.
- Setting up the resulting equations shows matching the color counts would require a non-whole number of vertical tiles in some columns, which is impossible, proving no valid tiling exists.
Reasoning
A horizontal tile always contributes equally to all four running color totals, so any imbalance between those totals must come entirely from vertical tiles, each adding to only one color at a time.
Since the imbalance created by the stripe coloring, a gap of 10 cells between the largest and smallest color groups, can't be resolved using only whole numbers of vertical tiles in multiples of 4, the tiling is proven impossible, using a deeper coloring argument than the simple checkerboard trick.
6. People Switching Seats
5 people are seated in a row in the order A, B, C, D, E. You want to rearrange them into the order E, D, C, B, A using only swaps of two people sitting in adjacent seats.
Rules
- Only adjacent people can be swapped
- Each swap counts as one move
- You want the fully reversed order
Your task — Determine the minimum number of adjacent swaps needed, and explain why.
Difficulty — Medium
Hint 1 — Count pairs that are out of order.
Hint 2 — Each swap fixes exactly one pair.
Hint 3 — Compare to the fully reversed order.
Main idea — Every adjacent swap changes the relative order of exactly one pair of people, so the minimum number of swaps always equals the total number of pairs in the wrong relative order compared to the target.
Solution
- In the target order E, D, C, B, A, every single pair of people is in the opposite relative order compared to the start.
- With 5 people, the total number of pairs is 5 choose 2, which is 10.
- Since every one of these 10 pairs needs its relative order flipped, and each adjacent swap flips exactly one pair, the minimum number of swaps needed is exactly 10.
Reasoning
An adjacent swap only ever changes the relative order of the two people directly involved, leaving every other pair's relative order untouched, so the count of out-of-order pairs drops by exactly one with each correctly chosen swap.
Since full reversal puts every pair in the opposite relative order from where it started, the number of necessary swaps is fixed at exactly the total pair count, and this pair-count invariant is also why certain arrangements are only reachable with a matching parity of swaps.
7. Parity of Moves: The Frog Puzzle
3 frogs sit on the left side of a row of 7 lily pads, and 3 more frogs sit on the right side, with 1 empty pad in the middle. Frogs can slide into an adjacent empty pad, or jump over exactly one frog into an empty pad beyond it, but frogs can never move backward toward their starting side.
Rules
- Frogs only move forward, never backward
- A move is a slide or a jump over one frog
- The goal is to fully swap the two groups
Your task — Determine the total number of moves needed to completely swap the two groups of frogs, and explain the count.
Difficulty — Hard
Hint 1 — Count slides and jumps separately.
Hint 2 — Each frog needs a fixed number of jumps.
Hint 3 — Add the slides and jumps together.
Main idea — Every frog must jump over every one of the opposing frogs exactly once, and every frog needs exactly one slide into an empty space at some point, so the total move count is fixed by these two separate, countable requirements.
Solution
- Every frog eventually slides exactly once into an adjacent empty space during the whole process, and since there are 6 frogs total, that accounts for exactly 6 slide-moves.
- Every frog also jumps over every frog from the opposite group exactly once; with 3 frogs on each side, that's 3 times 3, or 9, required jump-moves.
- Adding these together, 6 slides plus 9 jumps, gives a minimum of 15 total moves to completely swap the two groups.
Reasoning
Since frogs can never move backward, each frog's journey to the other side consists of exactly the slides and jumps needed to pass every opposing frog once, with no wasted or repeated moves possible in an optimal solution.
Counting the two move types separately, one guaranteed slide per frog and one guaranteed jump per opposing pair, gives an exact total that also proves this is the minimum possible, since skipping any move would leave some pair of opposing frogs still blocking each other.
8. Can You Reach the Final Configuration?
A row of 5 light switches starts with all switches off. On each move, you flip exactly 2 adjacent switches at the same time.
Rules
- Exactly 2 adjacent switches flip per move
- Any number of moves is allowed
- The goal is exactly 1 switch on, the rest off
Your task — Determine whether the target, exactly the middle switch on and all others off, can ever be reached, and prove your answer.
Difficulty — Medium
Hint 1 — Count how many switches are on.
Hint 2 — Each move changes that count evenly.
Hint 3 — Compare starting and target parity.
Main idea — Flipping exactly 2 switches at a time always changes the total number of switches that are on by an even amount, so the parity of that total can never change from where it started.
Solution
- At the start, 0 switches are on, an even number.
- Flipping 2 adjacent switches changes the on-count by plus 2, 0, or minus 2, always an even change, so the parity of the on-count stays even forever.
- The target configuration has exactly 1 switch on, an odd number, which can never be reached, since the on-count parity is permanently locked at even.
Reasoning
Every move changes the number of switches that are on by an even amount, whether both flipped switches turn on, both turn off, or one of each, so the overall parity of the on-count is an invariant fixed for the entire process.
Since the starting parity is even and the target parity is odd, no sequence of moves, however long or clever, can ever bridge that permanent mismatch, proving impossibility without checking any specific sequence of moves.