Puzzles and Brainteasers, lesson 6
Games with winning positions
Find the positions you want to leave your opponent.
In a two-player game with no luck and no draws, every position is a win or a loss for the player about to move, if both play their best. Find which, and you know how to play. You need counting, and the working backwards of the last lesson.
Part 1. Label from the end
Label every position as a win or a loss, starting from the end of the game.
Guess first
21 counters lie on a table. Two players take turns removing 1, 2 or 3 of them. Whoever takes the last counter wins. You move first. How many should you take?
Thinking ahead from 21 branches too fast. Near the end the game is tiny, though, so label positions by how many counters are left, starting from 0.
Example 1.1
Counters, labelled from zero
Take 1, 2 or 3 counters a turn; whoever takes the last one wins. For each number left, does the player about to move win or lose?
- 0 leftlose
Your opponent just took the last counter.
- 1, 2 or 3 leftwin
Take them all.
- 4 leftlose
Any move leaves 1, 2 or 3, and your opponent takes the rest.
- 5, 6 or 7 leftwin
Take 1, 2 or 3 to leave your opponent on 4.
- Read the patternlose at 0, 4, 8, 12, 16, 20
From a multiple of 4, every move leaves a number that isn't one; from any other number, one move reaches a multiple.
AnswerFrom 21, take 1 to leave 20. After each reply, take 4 minus what your opponent took.
You never look more than one move ahead. The labels below a position already hold everything that can happen after it, so one comparison per move is enough.
Winning and losing positions
A position is losing for the player to move if every move leads to a winning position, and winning if at least one move leads to a losing one. Label them from the end of the game back, and play by always moving to a losing position.
take 1 to 3, last counter wins: lose on multiples of 4
Check the ending before you label. If whoever takes the last counter loses, then 1 left is the loss, since you must take it, and the losses become 1, 5, 9, 13, 17 and 21. The same 21 counters that won for the first player now lose.
Your turn
25 counters, and a turn takes 1, 2, 3 or 4. This time whoever takes the last counter loses. You move first. How many should you take?
Part 2. Copy the opponent
Win by making the position symmetric and copying every move your opponent makes.
Keep going with Pro
You've done the first part. Pro opens the rest of this lesson, and every other one.
- Copy the opponent
- Steal a strategy
Puzzles and Brainteasers overviewSpotted a mistake? Tell us.