Theory of Games 79

7.4 The Gold Coin game

Consider next the Gold Coin game, a two-player moving-coin game played with a gold

coin and some pennies. Each player strives to get the gold coin.

The game begins with the coins on a track, and the gold coin is farthest to the right. On

each turn, a player may either (1) move any coin to the left by one or more spaces but

without jumping over another coin, or (2) take the leftmost coin into his or her possession.

Whoever takes the gold coin is the winner. In the diagram above, one of the players has

just moved the gold coin three spaces, which we will see is a winning move. What is the

winning strategy? I would recommend playing the game with a partner several times in

order to gain familiarity with it.

It turns out that the Gold Coin game can be successfully analyzed by means of a reduction

to the game of Nim, which will lead to a winning strategy in the Gold Coin game. In order

to carry out this reduction, we associate with each position in the Gold Coin game a certain

Nim position as follows.

A given Gold Coin position

↓

The associated Nim values, with all four winning moves indicated

↓

3

1 22 + 1

The associated Nim position

Beginning at the right with the gold coin, we take the coins in successive pairs, and for

each such pair of coins, we think of the interval between them as a Nim pile (orange); we

ignore the intervals between these pairs (blue); and if the leftmost coin has no partner, then