The Last Stick
The puzzle
Twenty-one sticks lie on a table. You and an opponent take turns removing one, two or three sticks. Whoever takes the last stick wins.
You move first. Can you force a win, and what is the rule?
Stuck?
One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.
Hint 1
Work out which numbers of remaining sticks LOSE for whoever has to move.
Hint 2
If four sticks remain and it is your turn, whatever you take leaves one to three for your opponent.
Show the answer Hide the answer
Yes. Take one stick, leaving twenty, then always take four minus whatever your opponent just took.
How to get there
Leaving a multiple of four is a losing position for the player about to move: from 4 you must leave 1, 2 or 3, all of which the opponent takes to win.
Because the position after any pair of moves can always be reduced by exactly four - you take 4 minus their take - a multiple of four stays a multiple of four all the way down.
Twenty-one is one more than twenty, so take one and hand over 20. Then mirror: they take k, you take 4-k. They face 16, 12, 8, 4 and finally 0.
The technique worth keeping
Label positions as winning or losing from the end backwards. A position is losing if every move from it reaches a winning one, and that single definition solves this whole family of games.