Games & Processes

What you need to know

• Round-robin. If $n$ teams each play every other team once, there are $\binom{n}{2}$ games. With no ties, each game has one winner, so the wins also add up to $\binom{n}{2}$. Example: $8$ teams play $\binom82 = 28$ games and win $28$ in all.
• Single elimination. $n$ players need exactly $n-1$ matches: each match knocks out one player, and everyone but the champion is knocked out. Example: $64$ players need $63$ matches.
• Invariants. An invariant is something no step changes, like even/odd, or a total's remainder when divided by some $m$. A final state with a different value can never be reached. Example: $1, 2, \dots, 10$ are on a board. A move erases two numbers and writes their difference, which lowers the sum by twice the smaller one. So the sum, $55$ at the start, stays odd, and the last number left is never $0$.
• Winning and losing positions. A position is losing if the player to move loses with best play on both sides. That happens when every move leads to a winning position. A position is winning when some move leads to a losing one. In "take $1$ to $k$ stones; whoever takes the last stone wins," the losing positions are the multiples of $k+1$. Example: taking $1$ to $3$ stones, $20$ is losing. Whatever you take, your opponent tops the round up to $4$ stones, and in the end takes the last one.

How AMC 10 tests it

• Problems 5–12: games in a tournament, handshakes at a party, days until a schedule repeats.
• Problems 12–20: a number is changed again and again by a rule; find its value after many steps.
• Problems 15–22: two-player games of taking objects away, asking which starting sizes are first-player wins.
• Problems 18–25: a repeated process with a counting answer.

Standard approaches

1. Work out the first several steps by hand; a cycle or pattern usually shows up fast.
2. Look for an invariant the process keeps (even/odd, a sum's remainder).
3. For two-player games, work backward from the end, marking positions W (winning) or L (losing).
4. For tournaments, use total wins $= \binom{n}{2}$ to set up an equation.
5. For "how many starting values," find the pattern, then count with remainders.

Worked example

Alice and Bob alternately remove $1$, $3$, or $4$ coins from a pile of $n$ coins, Alice first; whoever takes the last coin wins. For how many integers $n$ with $1 \le n \le 100$ does Bob have a winning strategy?

(A) $14$ (B) $20$ (C) $28$ (D) $29$ (E) $34$

Solution.

Step 1: the rule. Mark each pile size L (losing) or W (winning) for the player about to move. A pile of $0$ is L (the other player just took the last coin). A pile is W exactly when taking $1$, $3$, or $4$ coins can leave an L pile.

Step 2: the table. For example, $2$ is L (its only move leaves $1$, a W), and $7$ is L (its moves leave $6$, $4$, $3$, all W).

Step 3: the period. Each entry depends only on the entries $1$, $3$, and $4$ places back. Entries $7$ to $10$ (L, W, L, W) match entries $0$ to $3$, so from there on the table repeats every $7$. The L piles are the numbers with remainder $0$ or $2$ when divided by $7$ (written $n \equiv 0$ or $2 \pmod 7$).

Step 4: who wins. Alice moves first, so Bob wins exactly when the starting pile is L.

Step 5: count. Multiples of $7$: $7, 14, \dots, 98$, which is $14$ numbers. Remainder $2$: $2, 9, \dots, 100$, which is $\frac{100-2}{7}+1 = 15$ numbers. Total: $14+15 = 29$.

The answer is $\boxed{\textbf{(D)}\ 29}$.

Pitfalls

• Counting round-robin games as $n(n-1)$ instead of $\binom{n}{2}$. That counts each game twice: $8$ teams play $28$ games, not $56$.
• Stopping a simulation before the cycle has repeated in full, then following a false pattern.
• Marking a position W because one move leads to a W position. A winning move must lead to an L position.
• Off-by-one mistakes between "after $k$ steps" and "at step $k$." If the start is step $1$, then after $5$ steps you are at step $6$.

Traps that recur

• Treating the game as ordinary Nim (using wall sizes 6, 2, 1 directly) even though removing a middle brick splits a wall into two. (2021 AMC 10B #24)
• Treating the 18 games as freely arrangeable (choosing which 3 go in each round) without enforcing that every player plays exactly once per round. (2013 AMC 10A #24)
• Reporting the number of transitive triples, 945 (choice C), or the total number of triples, 1330 (choice E), instead of their difference. (2016 AMC 10B #22)
• Trying to simulate all the exchanges by hand, or assuming the process ends with 0 tokens of each color. (2013 AMC 10B #17)