Kvant Math Problem 1210
The position of the game is completely determined by the current number of matches in the pile and the set of numbers already written on the sheet.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m57s
Source on kvant.digital
Problem
There is a pile of $M$ matches and a sheet of paper on which the number $M$ is written. Two players play the following game. They take turns. A move consists of taking from the pile or returning to the pile from 1 to $k$ matches and writing on the sheet the new number of matches in the pile. (At the start, all matches are in the pile — the players have none.) A player loses if they cannot make a move or are forced to write a number that has already appeared on the sheet. Who wins with perfect play if
- $k=2$;
- $k=5$?
K. P. Kokhas
Exploration
The position of the game is completely determined by the current number of matches in the pile and the set of numbers already written on the sheet. Since every written number is forbidden forever, the game can never visit the same number twice. Thus the play traces a simple path in the graph whose vertices are the integers from $0$ to $M$, where two numbers are adjacent if their difference is between $1$ and $k$.
A move from $x$ consists of moving to an unvisited vertex $y$ with $1\le |x-y|\le k$. A player loses when no such vertex exists.
For $k=2$, it is useful to examine small values.
For $M=0$, no move exists, so the first player loses.
For $M=1$, the only move is $1\to0$, after which no move exists; the first player wins.
For $M=2$, the first player moves to $0$ or $1$. In either case the second player makes the remaining move and wins. Thus $M=2$ is losing.
For $M=3$, moving to $1$ gives the path $3\to1$, and the second player must go to $0$ or $2$; in both cases the first player has the last move. Hence $M=3$ is winning.
The pattern suggests that even $M$ are losing and odd $M$ are winning. Testing $M=4$ confirms this: every first move goes to $2$ or $3$, and the opponent can answer so that the parity pattern is preserved.
The graph for $k=2$ is the path with additional edges joining vertices at distance $2$. The symmetry $x\mapsto M-x$ suggests a pairing strategy when $M$ is even.
For $k=5$, small cases are needed.
Let $P(M)$ denote a losing starting position.
$M=0$ is losing.
$M=1,2,3,4,5$ are winning because one can move directly to $0$.
For $M=6$, every move goes to one of $0,1,2,3,4,5$, all of which are winning positions in the game restricted to the visited set produced by the move. Direct checking shows that each first move allows the second player to finish the game. Thus $6$ is losing.
Trying further values gives
$$P(M):\quad 0,6,12,\ldots$$
This suggests that multiples of $6$ are losing.
The crucial point is to find a strategy. When $M=6n$, the involution
$$x\longmapsto 6n-x$$
pairs the vertices symmetrically. Any legal move changes the number by at most $5$, hence if one player moves from $a$ to $b$, then
$$|(6n-a)-(6n-b)|=|a-b|\le5,$$
so the reflected move is also legal. Since the starting vertex is $6n$, after the first player moves to $x$, the second player can move to $6n-x$. This resembles the standard mirror strategy. One must verify that the reflected vertex has not been visited already.
The hardest point is proving that this mirror strategy never breaks down. Since vertices always occur in symmetric pairs, one must show that before the second player responds, the partner $6n-x$ of the first player's new vertex cannot already have appeared.
For nonmultiples of $6$, moving immediately to the nearest lower multiple of $6$ seems to give a winning move.
Problem Understanding
We have vertices $0,1,\dots,M$. Initially only $M$ has been written. A move consists of moving from the current number to another number differing by at most $k$, and the destination number must not have appeared earlier on the sheet. The player who cannot move loses.
This is a Type A problem. We must determine exactly which initial values $M$ are winning and which are losing for each specified value of $k$.
The core difficulty is that the legality of a move depends not only on the current number but also on the entire history of visited numbers. The game is therefore not an ordinary subtraction game. The key idea is to regard the numbers as vertices of a graph and the play as a self-avoiding walk.
For $k=2$, the answer is that the first player wins precisely when $M$ is odd.
For $k=5$, the answer is that the first player wins precisely when $M$ is not divisible by $6$.
Proof Architecture
The first lemma states that for $k=2$ and even $M$, the second player has a mirror strategy with respect to the midpoint $M/2$; the reflection of every legal move is legal and unvisited.
The second lemma states that for $k=2$ and odd $M$, the first player can move to $M-1$, an even number, thereby giving the opponent a losing position.
The third lemma states that for $k=5$ and $M=6n$, the second player has a mirror strategy with respect to the involution $x\mapsto6n-x$.
The fourth lemma states that for $k=5$ and $M\not\equiv0\pmod6$, the first player can move to the largest multiple of $6$ below $M$.
The most delicate point is proving that in the mirror strategies the reflected vertex has never been visited before.
Solution
We interpret the game as follows. The vertices are the integers
$$0,1,\dots,M.$$
Two vertices are joined when their difference is between $1$ and $k$. A move consists of moving along an edge to a vertex that has not yet been visited. Thus the play is a self-avoiding walk beginning at $M$.
We first treat the case $k=2$.
Suppose that $M=2n$ is even. Consider the reflection
$$\sigma(x)=2n-x.$$
After the first player's move from $2n$ to some vertex $x$, the second player moves to $\sigma(x)$.
This response is legal because
$$|\sigma(x)-x| =|2n-2x| =2|n-x|.$$
Since the first move from $2n$ reaches only $2n-1$ or $2n-2$, we have $|n-x|=1$ or $0$, hence $|\sigma(x)-x|\le2$.
Now suppose later the first player moves from $a$ to $b$. The second player responds from $\sigma(a)$ to $\sigma(b)$. Since
$$|\sigma(a)-\sigma(b)|=|a-b|\le2,$$
the response is legal whenever $\sigma(b)$ has not been visited.
We prove that $\sigma(b)$ is indeed unvisited. Initially only $2n$ is visited, and $2n$ is fixed by $\sigma$. After the first move to $x$, the second player visits $\sigma(x)$. Thereafter vertices are always visited in symmetric pairs ${v,\sigma(v)}$. Immediately before any move of the first player, every visited vertex other than the current one belongs to such a completed pair. If $\sigma(b)$ had already been visited, then its partner
$$\sigma(\sigma(b))=b$$
would also have been visited earlier. This is impossible because $b$ is the destination of the current move and therefore is being visited for the first time.
Hence the mirror response is always available. The vertices, except for the fixed vertex $2n$, are partitioned into pairs ${v,\sigma(v)}$. After every move of the first player, the second player makes the corresponding reflected move. Consequently the second player always moves after the first player and can never be the first to run out of moves. Therefore every even $M$ is a losing position.
Now let $M=2n+1$ be odd. The first player moves to $2n$. The game then starts from an even number. By the result already proved, every even starting number is losing for the player to move. Hence the opponent receives a losing position. Thus every odd $M$ is winning.
Therefore for $k=2$ the losing positions are exactly the even integers.
Now consider $k=5$.
Let $M=6n$. Define
$$\tau(x)=6n-x.$$
After the first player's move from $6n$ to a vertex $x$, the second player moves to $\tau(x)$.
Since the first move reaches only vertices $6n-r$ with $1\le r\le5$,
$$|x-\tau(x)| =|6n-2x| =2r\le5$$
only for $r=1,2$; however the response need not be made directly from $x$. The correct mirror strategy is the following.
Whenever the first player moves from $a$ to $b$, the second player moves from $\tau(a)$ to $\tau(b)$.
Because
$$|\tau(a)-\tau(b)|=|a-b|\le5,$$
this move is legal whenever $\tau(b)$ is unvisited.
The same pairing argument as before shows that $\tau(b)$ cannot have been visited earlier. Initially only the fixed vertex $6n$ is visited. Afterwards vertices are created in symmetric pairs ${v,\tau(v)}$. If $\tau(b)$ had already appeared, then applying $\tau$ again shows that $b$ had already appeared, contradicting the fact that the move to $b$ is legal.
Thus the second player can mirror every move of the first player. Since all vertices except $6n$ are partitioned into pairs under $\tau$, the second player always has a response. Hence every multiple of $6$ is a losing position.
Now let
$$M=6n+r,\qquad 1\le r\le5.$$
The first player moves from $M$ to $6n$. This is legal because the distance is $r\le5$.
The resulting position is exactly a starting position with pile size $6n$, and it is now the opponent's turn. We have proved that every multiple of $6$ is losing for the player to move. Hence the opponent receives a losing position.
Therefore every $M$ not divisible by $6$ is winning.
The complete classification is
$$\boxed{\text{For }k=2,\ \text{the first player wins iff }M\text{ is odd}.}$$
and
$$\boxed{\text{For }k=5,\ \text{the first player wins iff }6\nmid M.}$$
Verification of Key Steps
For $k=2$, the critical point is the claim that the reflected destination $\sigma(b)$ is unvisited. Suppose instead that $\sigma(b)$ had appeared earlier. Every appearance except the initial vertex occurs together with its reflected partner, because the second player's strategy creates vertices in pairs. Hence $b=\sigma(\sigma(b))$ would also have appeared earlier. The move to $b$ would then be illegal. This contradiction proves the claim.
For $k=5$, the same issue arises. The involution $\tau(x)=6n-x$ preserves edge lengths because
$$|\tau(a)-\tau(b)|=|a-b|.$$
A careless argument might verify only legality of the reflected edge and forget to prove freshness of the destination. The pairing argument supplies exactly that missing point.
Another possible error is to assume that moving from $6n+r$ to $6n$ produces a game independent of previous history. This is correct because at that moment only two numbers have been written, namely $6n+r$ and $6n$. The classification of multiples of $6$ as losing positions was proved for precisely such starting configurations.
Alternative Approaches
One may formulate the game entirely as a graph problem. The vertices are $0,\dots,M$, and the play is a self-avoiding walk beginning at $M$. For $k=2$ and $k=5$, the graph admits a central symmetry whenever $M$ is respectively even or divisible by $6$. The losing positions are exactly those for which the starting vertex is the unique fixed point of that symmetry. The mirror strategy then becomes a standard pairing argument on graph automorphisms.
The direct solution above is preferable because it works with the numbers written on the sheet rather than introducing additional graph-theoretic language. The symmetry responsible for the answer is exposed explicitly, and the winning move in the nonlosing cases is immediately visible.