Brainteasers & Logic
Strategy Games & Winning Positions
Overview
Strategy games reduce to one mechanical process: classify every position as P (previous player wins = current player loses) or N (next player = current player wins). Work backwards from terminal states. Nim is the prototype — its XOR solution is elegant. Once you understand P/N positions, you can solve most combinatorial games at interviews quickly.
How to Recognize
- →'Two players take turns. Who wins with optimal play?'
- →Nim-style: remove stones from piles
- →Subtraction games: remove at most k from a pile
- →Any game where you need to find the 'right' positions
Step-by-Step Approach
- 1.Label every position P (losing for current player) or N (winning)
- 2.P-position: ALL moves lead to N-positions. N-position: EXISTS a move to a P-position.
- 3.Work backwards from terminal (empty/no-moves) position: it's a P-position
- 4.Nim: XOR all pile sizes. XOR=0 → P-position (lose). XOR≠0 → N-position (win).
Key Formulas
Worked Examples
Problem
A pile has 17 stones. Players alternate removing 1, 2, or 3. The player who takes the last stone wins. Who wins?
Solution
Max removal = 3. Cycle length = 3+1 = 4. P-positions are multiples of 4: {0, 4, 8, 12, 16, 20...}.
Verify: position 0 = P (no moves, previous player took last stone and won → you lose). Position 4: remove 1→3 (N), remove 2→2 (N), remove 3→1 (N). All moves go to non-multiples of 4 (all N). So 4 is P. ✓
17 mod 4 = 1. Since 17 is NOT a multiple of 4: N-position. Current player wins.
Winning move: take 1 stone, leaving 16 = 4×4 — a P-position.
Strategy thereafter: whatever opponent takes (1,2,3), respond with (3,2,1) to always add to 4 total. Next P-positions: 16, 12, 8, 4, 0.
Answer
First player wins. Take 1 stone (leaving 16). Then mirror: whatever opponent takes, take 4 minus that. P-positions every 4 stones.
Common Mistakes
- !
Nim: confusing P-position (XOR=0, current player LOSES) with winning. If XOR=0 and it's your turn, you are in trouble.
- !
For subtraction games: multiples of (k+1) are P-positions, not multiples of k.
- !
Misère Nim: the XOR strategy applies in normal Nim. Misère Nim (player who takes LAST stone LOSES) uses XOR strategy except when all piles ≤ 1.
Practice Problems
Click "Show Answer" to revealNim piles: [2, 4, 6]. Is this P or N position? If N, find the winning move.
Remove 1–5 stones from a pile of 31. Last to move wins. Who wins and what's the first move?
The 100-point game: players add 1–10 to a running total starting at 0. First to reach exactly 100 wins. First or second player wins, and what is the strategy?