insideout Get Pro

06 · Games with winning positions

Pro

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?

1, leaving 20. From then on you can always leave a multiple of 4, as the example shows.

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?

  1. 0 leftlose

    Your opponent just took the last counter.

  2. 1, 2 or 3 leftwin

    Take them all.

  3. 4 leftlose

    Any move leaves 1, 2 or 3, and your opponent takes the rest.

  4. 5, 6 or 7 leftwin

    Take 1, 2 or 3 to leave your opponent on 4.

  5. 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.

0lose1234lose5678lose9101112lose13141516lose17181920lose21take 1counters left, for the player about to move
Figure 1Losses for the player about to move are the multiples of 4. From 21 you take 1; whatever your opponent then takes, 1, 2 or 3, you take the rest of 4 and land on the next loss down.

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?

Now 1 left is the loss, and losses step by 5: 1, 6, 11, 16, 21. From 25, take 4 to leave 21. Calling 25 a loss borrows the labels of the game where the last counter wins.

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.

Still to come
  1. Copy the opponent
  2. Steal a strategy

Puzzles and Brainteasers overviewSpotted a mistake? Tell us.