Reasoning · Grade 4-2 Nim Games

Problem

Which marbles you must take to win

Ten marbles numbered 1 to 10 sit in a row. Players take turns removing marbles from the lowest number still there. Three different rule sets are given. For each, find the marbles you must be the one to take.
Your answer
How to solve
Strategy Work Backwards — The rules say who wins by describing the very end of the game, so the end is where the reasoning has to start. I first ask which marble decides the game, then ask what I must have done one turn earlier to make that marble mine, then one turn earlier again. Doing this repeatedly produces a chain of key marbles, and the chain turns out to be evenly spaced - that is the pattern that makes the strategy easy to remember. A short systematic list of the small end positions confirms which ones are hopeless for the player whose turn it is.
1STEP 1

Notice that only the number left matters

All that matters is how many marbles remain.

marbles taken = 1,…,k → remaining = 10 - k
2STEP 2

Rules (1): the turns are completely forced

In (1) the turns are forced, so yours are 2, 4, 6, 8, 10.

me: 2,4,6,8,10 opponent: 1,3,5,7,9
3STEP 3

Rules (2): start at the end and step back

In (2) step back from 10 three at a time.

10 - 7 = 3
4STEP 4

Rules (2): repeat the step-back to the very start

Carrying on gives 1, 4, 7, 10.

10-1 = 9, 10-4 = 6, 10-7 = 3, 10-10 = 0
5STEP 5

Read the pattern in the key marbles

The key numbers go up in threes.

1 → 4 → 7 → 10
6STEP 6

Rules (3): the last marble is now poison

In (3) marble 10 is poison, so take 3, 6, 9.

9 → 6 → 3
7STEP 7

Play each game out to check

Playing them out shows all three work.

1,4,7,10 and 3,6,9
Answer
2 4 6 8 10 / 1 4 7 10 / 3 6 9
10, 7, 4, 1
Each list should end on the marble that decides that game, and each does: (1) and (2) end on marble 10, the winning marble, while (3) ends on marble 9, leaving the poisoned marble 10 for the opponent. The spacing also matches the moves available: in (1) only 1 marble may be taken per turn so the key marbles are 2 apart, and in (2) and (3) either 1 or 2 may be taken so they are 1 + 2 = 3 apart. Finally the lists say who has to move first, and it checks out: 10 is a multiple of 2 so in (1) I go second, 10 is not a multiple of 3 so in (2) I go first, and 10 leaves 1 more than a multiple of 3 so in (3) I go second.
Takeaway

Work backwards from the marble that decides the game, then jump back by one-plus-the-most-you-may-take each time - and always answer your opponent's move so the two of you remove that same total every round.

  • Notice that only the number left matters
  • Rules (1): the turns are completely forced
  • Rules (2): start at the end and step back
  • Rules (2): repeat the step-back to the very start
  • Read the pattern in the key marbles
  • Rules (3): the last marble is now poison
  • Play each game out to check