2004 AMC 10A Problem 8

P1-10~4 minPrint

Games & Processes Use an invariant, parity, or coloring argument Compute small cases, spot the pattern, generalize

A game is played with tokens according to the following rule. In each round, the player with the most tokens gives one token to each of the other players and also places one token in the discard pile. The game ends when some player runs out of tokens. Players $A$ , $B$ , and $C$ start with $15$ , $14$ , and $13$ tokens, respectively. How many rounds will there be in the game?

Show solution without answering

Key insight

Every three rounds, each player ends up with exactly one fewer token. So after 36 rounds they hold 3, 2, 1, and round 37 leaves A with nothing.

Solution

1. Play a few rounds by hand, writing the holdings of $(A, B, C)$ . In each round the leader loses $3$ and the other two gain $1$ each.
$(15,14,13) \to (12,15,14) \to (13,12,15) \to (14,13,12).$
2. Compare the start with the result after $3$ rounds: $(15,14,13)$ became $(14,13,12)$ . The pattern is the same, but everyone has exactly one token fewer.
3. Why this happens: in those three rounds each player is the leader once, paying $3$ tokens, and receives $1$ token in each of the other two rounds. The net change is $-3 + 1 + 1 = -1$ for everybody.
4. So every block of $3$ rounds takes one token from each player. After $12$ blocks, which is $36$ rounds, the holdings are
$(15-12,\ 14-12,\ 13-12) = (3,\ 2,\ 1).$
Nobody has hit zero yet, since the smallest amount in each block is still at least $1$ .
5. Round $37$ : $A$ has the most, $3$ tokens, and gives them all away (one to $B$ , one to $C$ , one to the discard pile). Now $A$ has $0$ and the game ends.

The answer is $\boxed{\textbf{(B)}\ 37}$ .

Why this works

Repeated processes on the AMC usually fall into a short cycle. Play until the situation looks the same as before except for a simple shift, find how much changes per cycle, and jump ahead. The last few rounds must still be played one at a time, because the game checks for zero after every round.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Simulate the first few rounds, listing $(A, B, C)$ :
$(15,14,13) \to (12,15,14) \to (13,12,15) \to (14,13,12).$
After three rounds the holdings are again "consecutive, decreasing in the order $A, B, C$ ," but each player has exactly one token fewer. This makes sense: in a three-round block every player leads once, paying $3$ tokens, and receives $1$ token in each of the other two rounds, for a net loss of $1$ .

So after $3k$ rounds the holdings are $(15-k, 14-k, 13-k)$ . Taking $k = 12$ , after $36$ rounds the players hold $(3, 2, 1)$ ; nobody has hit zero yet, since within each block the smallest count is at least $2$ less than the leader's starting count.

In round $37$ , player $A$ has the most tokens ( $3$ ) and must give away all three, one to each opponent and one to the discard pile. $A$ now has $0$ tokens and the game ends.

The answer is $\boxed{\textbf{(B)}\ 37}$ .

Review in the AoPS books

Intermediate Counting & Probability, Chapter 13: Events With States (§13.4)
Prealgebra, Chapter 15: Problem-Solving Strategies (§15.1)
Introduction to Number Theory, Chapter 12: Introduction to Modular Arithmetic (§12.6)