Kvant Math Problem 324

Consider a single pile with a small number of stones.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m20s
Source on kvant.digital

Problem

There are several piles of stones. Two players play a game in which a move consists of splitting each pile containing more than one stone into two smaller piles. The players move alternately until every pile contains exactly one stone. The winner is the player who makes the last move. How should the first player play if initially each pile contained between 80 and 120 stones?

S. V. Fomin

Exploration

Consider a single pile with a small number of stones. If a pile contains one stone, no moves are possible. For two stones, the first player can split it into two piles of one stone each, immediately winning. For three stones, the first player splits into $1+2$; the second player then splits the pile of two into $1+1$, making the last move and winning. For four stones, splitting into $2+2$ leads the second player to split one of the twos, making the last move, so the first player loses if both play optimally. Extending these observations, one sees that the parity of moves matters: the winner is determined by whether the total number of splits (moves) is odd or even. Each pile of $n$ stones requires exactly $n-1$ splits to reduce to single stones. Thus, with multiple piles, the total number of moves is $\sum_i (n_i - 1)$. Small numerical examples confirm this: piles of sizes $2,3,4$ yield totals $1+2+3=6$ moves; if even, the second player wins. The crucial point is to identify the total parity of moves and how it relates to the first player’s strategy. Since all piles initially contain between $80$ and $120$ stones, each pile is much larger than one, but the same parity argument applies.

Problem Understanding

We are asked to determine how the first player should play in a combinatorial game of splitting piles until all piles contain exactly one stone. The problem type is Type A: “Find all X,” where $X$ is the optimal first move or strategy. The core difficulty is recognizing the winning criterion: the game reduces to counting the total number of moves, which is invariant under the choice of splits except for parity. Each pile of size $n$ generates $n-1$ moves. Therefore, the first player should aim to make the total number of remaining moves odd on their turn. Since every pile is between $80$ and $120$ stones, the total number of moves modulo 2 can be computed, and the first player wins if and only if this sum is odd. Intuitively, the player must choose any split on the first move because the exact sizes of piles do not affect parity, only the total number of moves matters.

Proof Architecture

Lemma 1: Reducing a pile of $n$ stones to $n$ singleton piles requires exactly $n-1$ moves. Sketch: each move increases the number of piles by exactly one, starting from one pile and ending with $n$ piles.

Lemma 2: The total number of moves in a game is invariant regardless of the order in which piles are split. Sketch: each pile contributes $n_i-1$ moves independently; summing over all piles gives the total.

Lemma 3: The player who makes the last move is determined by the parity of the total number of moves: if the total is odd, the first player wins; if even, the second player wins. Sketch: moves alternate, so parity decides the last mover.

The hardest step is rigorously justifying that the exact choice of splits never changes the total number of moves; this is the lemma most likely to be misapplied.

Solution

Lemma 1. Let a pile contain $n$ stones. Initially there is one pile. Each move splits a pile of size $m>1$ into two smaller piles. Every move increases the total number of piles by exactly one. To reach $n$ singleton piles from one pile requires increasing the number of piles from $1$ to $n$, a difference of $n-1$. Therefore, exactly $n-1$ moves are necessary.

Lemma 2. Consider several piles with sizes $n_1, n_2, \dots, n_k$. Each pile $i$ requires $n_i-1$ moves to reduce to singletons, independent of the splitting order. Summing over all piles, the total number of moves is

$$\sum_{i=1}^k (n_i - 1).$$

This quantity is invariant under any sequence of splits because no move can change the total number of moves required for the remaining stones.

Lemma 3. Let $M = \sum_{i=1}^k (n_i - 1)$ be the total number of moves. Players alternate moves starting with the first player. If $M$ is odd, then after $M-1$ moves, it will be the first player’s turn, so they make the last move and win. If $M$ is even, the second player makes the last move.

Applying Lemmas 1–3 to the problem, each initial pile has size between $80$ and $120$, so for $k$ piles the total number of moves is

$$M = \sum_{i=1}^k (n_i - 1) = \sum_{i=1}^k n_i - k.$$

The first player wins if and only if $M$ is odd. The exact split in the first move is irrelevant; the first player may split any pile arbitrarily. The winning condition depends solely on the parity of $M$. Therefore, the first player should begin the game if $M$ is odd and avoid playing first if $M$ is even, as optimal play by both players reduces to counting parity.

Verification of Key Steps

Lemma 1 is verified by induction on $n$. Base case $n=1$ requires $0$ moves, consistent with $n-1=0$. Assume a pile of size $n$ requires $n-1$ moves. For $n+1$, split into $k$ and $n+1-k$ with $1\le k\le n$. By the inductive hypothesis, $k-1$ moves reduce the first pile and $n-k$ moves reduce the second pile, plus the initial split, giving $1 + (k-1) + (n-k) = n$ moves, consistent with $n+1-1$.

Lemma 2 is confirmed by testing sequences. For piles of sizes $3$ and $4$, total moves are $2+3=5$. Splitting $4$ first or $3$ first yields the same total after all splits. Merging or rearranging splits does not reduce or increase the total.

Lemma 3 is verified by small examples: a single pile of $2$ stones requires one move, first player wins; a single pile of $3$ stones requires two moves, second player wins. Extending to multiple piles preserves parity, confirming the rule.

Alternative Approaches

One could model the game as a variant of the nimber game by assigning each pile a nimber equal to its size minus one, then computing the nim-sum. This approach is equivalent because in this game all nimbers are treated linearly, and the winner is determined solely by the parity of the sum. The main approach is preferable for its simplicity, relying only on the invariant total number of moves and avoiding unnecessary abstraction.