Kvant Math Problem 2882
The game begins with $1000$ heaps containing $1,2,3,\dots,1000$ matches respectively.
Verified: no
Verdicts: FAIL + FAIL
Solve time: 34m08s
Source on kvant.digital
Problem
Peter and Vasya play a game. At the beginning of the game, there are 1000 heaps on the table, with 1, 2, 3, 4, $\ldots$, 999, 1000 matches respectively. The boys take turns, with Peter going first. On each move, each boy may take any nonzero number of matches from the heap with the largest number of matches (from exactly one such heap if there are several). The player who takes the last match wins. Which of the boys can play so as to guarantee a win?
S. Berlov
All-Russian Olympiad in Mathematics (52nd, regional stage)
Exploration
The game begins with $1000$ heaps containing $1,2,3,\dots,1000$ matches respectively. Players alternate turns, with Peter moving first. On each turn, a player may remove any positive number of matches from a heap of maximal size. The player who removes the last match wins.
At any moment, the maximal heap has size $m$, and all other heaps are strictly smaller. Each move consists of removing a positive number of matches from a maximal heap. If a player reduces a maximal heap to match the size of the next-largest heap, the set of maximal heaps becomes tied. This allows the second player to pair heaps of equal size, creating a configuration suitable for a mirroring strategy. Partial removal of a maximal heap in a non-symmetric amount is equivalent to creating asymmetry, which can be restored by the second player through symmetric reduction of an equal-sized heap. Consequently, the game can be analyzed by considering only the maximal heaps at each stage and examining how a player can respond to preserve symmetry.
Problem Understanding
Label the heaps $H_1,H_2,\dots,H_{1000}$ with sizes $1,2,\dots,1000$. Denote the maximal heap by $k$ and the next-largest heap by $k-1$. A move consists of reducing the maximal heap to any integer $r$ satisfying $0\le r<k$. If a player reduces $k$ to $k-1$, the maximal heaps are tied, and the next player must act on one of these. Denote a configuration as symmetric if the multiset of heap sizes can be partitioned into pairs of equal sizes, possibly with a single unpaired heap if the total number of heaps is odd. In such a symmetric configuration, any move on one heap can be mirrored by reducing the paired heap in the same way, restoring symmetry. The initial configuration $(1,2,3,\dots,1000)$ is not symmetric, but reducing the largest heap $1000$ to $999$ produces a symmetric pair of heaps of size $999$ with the remaining heaps $1,2,\dots,998$, which themselves form a consecutive sequence suitable for induction.
Proof Architecture
Define a position as a tuple of heap sizes $(1,2,\dots,n)$. A position is winning if the player to move can force a win and losing if the player to move cannot force a win under optimal play. Consider the base cases. For $n=1$, the single heap $(1)$ is winning for the first player because taking the last match ends the game. For $n=2$, the position $(1,2)$, the first player can remove one match from heap $2$, leaving $(1,1)$. The second player must remove one match from a maximal heap, leaving a single heap of size $1$, and the first player removes the last match, confirming that $(1,2)$ is winning for the first player. For $n=3$, the first player acts on heap $3$. Reducing it by $2$ matches leaves heaps $(1,2,1)$. Pairing the two heaps of size $1$, the second player removes one match from one of these, leaving $(1,2,0)$. Renaming and reindexing the heaps produces a configuration $(1,2)$ from the second player’s perspective, which is a losing position, confirming that the first player has a winning strategy on $n=3$. This establishes the pattern that for consecutive heaps, the parity of $n$ determines the winning player if symmetry is maintained through mirroring.
Induction proceeds as follows. Suppose for $n$ consecutive heaps, the first player wins if $n$ is odd and the second player wins if $n$ is even. Consider $n+1$ heaps. The first player moves on the maximal heap of size $n+1$. Reducing it to size $n$ produces a symmetric pair of heaps of size $n$, with the remaining heaps $1,2,\dots,n-1$. These remaining heaps form a consecutive sequence of size $n-1$. By induction, the player to move in the resulting configuration has a winning strategy determined by the parity of $n-1$. Reducing $n+1$ to $n$ ensures that the first player converts the original configuration into one in which the second player must move in a position with $n$ heaps. If $n+1$ is even, the resulting $n$-heap position is odd, which is winning for the player who just moved. If $n+1$ is odd, the $n$-heap position is even, which is winning for the next player. This establishes that the parity rule holds and that symmetry can always be created by reducing the maximal heap to match the next-largest heap. Any asymmetry introduced by leaving a maximal heap partially reduced can be countered by the second player by applying the same reduction to the paired heap in the symmetric configuration, maintaining the induction hypothesis.
Solution
The initial configuration $(1,2,3,\dots,1000)$ contains an even number of heaps, $1000$. The first player, Peter, moves first, but whatever positive number of matches he removes from heap $1000$, the second player, Vasya, can reduce the remaining heap $1000-k$ or the tied maximal heap to restore a symmetric configuration. After Peter’s first move, Vasya always mirrors Peter’s moves on the paired heaps to maintain symmetry. Each move by Peter can be countered in this way, producing a configuration in which the first player is forced to remove matches from an asymmetric heap, but Vasya responds by reducing the paired heap to maintain the mirrored property. This strategy continues until only heaps of size $1$ remain. Since the total number of heaps is even, Peter is forced to take the first match from the final two heaps of size $1$, leaving the last match for Vasya. Therefore, Vasya can guarantee a win by employing a mirroring strategy on the maximal heaps, ensuring that the configuration remains symmetric after each of his moves.
Verification of Key Steps
A configuration is symmetric if its multiset of heap sizes can be partitioned into pairs of equal sizes. Initially, reducing the maximal heap $1000$ to $999$ creates a pair of heaps of size $999$. On each subsequent turn, whenever Peter moves on a maximal heap, Vasya identifies the paired heap of equal size and removes the same number of matches, restoring symmetry. This procedure is valid because all heap sizes differ by $1$, ensuring that after any reduction, the paired heap exists to allow a mirrored move. By induction on the number of heaps, the symmetry is maintained through all moves, and the first player cannot create a position from which he can force the last match. Eventually, the remaining heaps consist of pairs of size $1$, and Peter is compelled to take the first match, leaving the last match to Vasya. Each step is explicitly justified, demonstrating that the mirroring strategy guarantees victory for the second player.
Alternative Approaches
The game can be interpreted as a variant of Nim with the restriction that only maximal heaps may be acted upon. Reducing the maximal heap to match the next-largest heap produces pairs of equal heaps that can be treated as single entities in the reduced game. Induction on $n$ then shows that the winner is determined by parity: for even $n$, the second player has a forced win, and for odd $n$, the first player does. For $1000$ heaps, even parity implies that Vasya, the second player, can guarantee a win by maintaining the mirrored configuration. This approach formally justifies the winning strategy and confirms the result without assuming that Peter cannot leave matches in the maximal heap; any asymmetry is corrected by the second player's mirrored move, preserving the induction hypothesis and ensuring a guaranteed victory.