Puzzles
Greedy & Strategy Games
These are two-player games with perfect information, no luck involved, where one side can always force a win with the right strategy. The skill is finding the losing positions, the setups that guarantee a loss no matter how well the player facing them plays, and always steering your opponent into one.
1. The Nim Game
Two players alternate turns removing 1, 2, or 3 stones from a pile that starts with 21 stones. Whoever removes the last stone wins.
Rules
- Each turn removes 1, 2, or 3 stones
- Players alternate turns
- Whoever takes the last stone wins
Your task — Determine which player can force a win, and describe the winning strategy.
Difficulty — Medium
Hint 1 — Think about multiples of 4.
Hint 2 — Leaving 4 stones is a losing spot.
Hint 3 — Always leave a multiple of 4.
Main idea — Leaving your opponent a pile size that's a multiple of 4 guarantees you can always restore the pile to the next lower multiple of 4 after their move, eventually forcing them to take the last stone from a losing position.
Solution
- Since 21 is not a multiple of 4, the first player can win by always leaving a multiple of 4 for the opponent.
- On the first turn, the first player removes 1 stone, leaving 20, a multiple of 4.
- Whatever the opponent removes, 1, 2, or 3, the first player removes enough to bring that round's total to exactly 4, keeping the pile at a multiple of 4 after every one of their own turns.
- This continues until the pile reaches exactly 4, then 0, with the first player taking the final stone.
Reasoning
If a player faces a pile that's a multiple of 4, any move they make leaves a pile that is not a multiple of 4, giving their opponent the chance to remove just enough stones to restore a multiple of 4.
Since an empty pile is itself a multiple of 4, and taking the last stone wins, always handing your opponent a multiple of 4 guarantees you eventually hand them exactly 0 stones on their turn, meaning you took the last one.
2. The Two-Pile Coin Game
Two piles of coins sit on the table, one with 5 coins and one with 7 coins. Players alternate turns, and on each turn a player removes any number of coins, at least one, from exactly one of the two piles. Whoever removes the last coin from the table wins.
Rules
- Only one pile can be touched per turn
- Any positive number of coins can be taken
- The player taking the last coin wins
Your task — Determine which player can force a win, and describe the winning first move.
Difficulty — Hard
Hint 1 — Compare the pile sizes in binary.
Hint 2 — XOR the two pile sizes together.
Hint 3 — A losing position has XOR zero.
Main idea — Converting both pile sizes to binary and XOR-ing them together reveals whether the position is already balanced, a loss for whoever moves next, or unbalanced, a win for whoever moves next by rebalancing it.
Solution
- Write 5 and 7 in binary: 5 is 101, and 7 is 111.
- XOR these together: 101 XOR 111 equals 010, which is 2, not zero, meaning the position favors the player about to move.
- The first player wins by removing 2 coins from the pile of 7, leaving piles of 5 and 5, since 5 XOR 5 equals 0, a balanced, losing position for the opponent.
Reasoning
A position where the XOR of all pile sizes is zero is always a loss for the player about to move, since every move they make necessarily unbalances it, while a nonzero XOR position is always a win, since there's always a move that restores balance to zero.
Starting at a nonzero XOR of 2 means the first player has a winning move, and reducing the 7-pile to match the 5-pile is exactly the move that restores the balanced, zero-XOR position, handing their opponent a guaranteed loss with correct play.
3. Optimal Strategy for a Coin Row
A row of coins with values 3, 9, 1, 2 lies on the table. Two players alternate turns, and on each turn a player takes the coin from either the left end or the right end of the remaining row. Both players play to maximize their own total, and the first player moves first.
Rules
- Only the leftmost or rightmost coin can be taken
- Both players always play optimally
- Each taken coin's value goes to that player
Your task — Find the maximum total the first player can guarantee, regardless of how the second player plays.
Difficulty — Hard
Hint 1 — Think about the last two coins first.
Hint 2 — Consider what the opponent leaves you.
Hint 3 — Break the row into smaller sub-rows.
Main idea — Working backward from small sub-rows of the coin line and tracking the best guaranteed outcome for whoever moves first in each sub-row builds up to the answer for the full row, the same idea behind dynamic programming.
Solution
- The first player takes the 2 from the right end, leaving the row 3, 9, 1.
- The second player then takes the 3 from the left end, leaving 9, 1.
- The first player takes the 9, and the second player is left with the final 1.
- The first player's total is 2 plus 9, which is 11, out of 15 coins on the table, no matter how the second player responds along the way.
Reasoning
Because each player plays optimally, the value either player can guarantee from any stretch of the row depends only on the best guaranteed outcomes of the shorter stretches left after a move, which is why solving small sub-rows first and reusing those answers, rather than planning the entire game at once, both simplifies the reasoning and guarantees the truly optimal result.
Checking the second player's alternative first response confirms it leads to the same guaranteed total for the first player, showing 11 is forced regardless of how the second player plays, not just the outcome of one particular line of play.
4. The Poisoned Chocolate Game
A 2 by 2 grid of chocolate squares sits on the table, and the top-left square is secretly poisoned. Players alternate turns, and on each turn a player chooses one remaining square and eats it along with every square below it and to its right in the original grid. Whoever is forced to eat the poisoned square loses.
Rules
- The grid is 2 rows by 2 columns
- Eating a square also eats all squares below and right of it
- Eating the top-left square loses the game
Your task — Determine which player can force a win, and find their winning first move.
Difficulty — Medium
Hint 1 — Avoid leaving a clean rectangle.
Hint 2 — Try eating just the bottom-right square.
Hint 3 — Check every response the opponent has.
Main idea — Eating only the single bottom-right square immediately breaks the board into an uneven shape that traps whoever moves next into eventually being forced onto the poisoned square, no matter how they respond.
Solution
- The first player eats only the bottom-right square, leaving the poisoned top-left square along with the top-right and bottom-left squares.
- Whichever of the two remaining safe squares the second player eats next, only the poisoned square and one other safe square remain.
- The first player eats that one remaining safe square, leaving only the poisoned square for the second player, who is forced to eat it and lose.
Reasoning
Checking every possible response confirms that after the first player's opening move, the second player has no way to avoid eventually being the one left with only the poisoned square, since both of their possible choices lead to the same forced final position.
This kind of argument, showing every branch leads to the same outcome, is how these combinatorial games are proven, rather than relying on a general formula the way some other take-away games allow.
5. Optimal Game Strategy: The Reversed Goal
Two players alternately remove 1 or 2 stones from a pile that starts with 17 stones. Unlike the usual version of this game, whoever is forced to take the very last stone loses.
Rules
- Each turn removes 1 or 2 stones
- Players alternate turns
- Whoever takes the last stone loses
Your task — Determine which player can force a win under this reversed goal, and describe their strategy.
Difficulty — Medium
Hint 1 — The usual goal here is flipped.
Hint 2 — Try to leave exactly 1 stone.
Hint 3 — Keep the pile one more than a multiple of 3.
Main idea — Because taking the last stone is now a loss, the winning strategy is to always leave your opponent a pile size that is one more than a multiple of 3, eventually trapping them with exactly 1 stone forced onto their turn.
Solution
- A pile of 1 stone is a loss for whoever faces it, since they must take it, so it's a losing position to be handed.
- Working this pattern forward shows that piles of size 1, 4, 7, 10, 13, and 16, each one more than a multiple of 3, are losing positions for whoever must move from them.
- Since 17 is not one of those sizes, the first player wins by removing 1 stone, leaving 16, a losing position for the opponent, and then always restoring the pile to the next lower number in that losing sequence after each of the opponent's moves.
Reasoning
From a losing position like 4 stones, taking 1 leaves 3, a winning position for the opponent since they can then leave you with 1, and taking 2 leaves 2, also winning for the opponent for the same reason, so either move from 4 hands the opponent a winning position.
Repeating this pattern shows only piles of size 1, 4, 7, 10, 13, and 16 force a loss on whoever must move from them, and since 17 isn't one of those sizes, the first player can always steer the game back into that losing sequence for their opponent, eventually leaving them exactly 1 stone to be forced into taking last.