Kvant Math Problem 376

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m47s
Source on kvant.digital

Problem

A row consists of 30 cells. A white piece stands on the rightmost cell, and a black piece stands on the leftmost cell. Each of the two players, in turn, moves their piece by one cell — either forward or backward. (Skipping a move is not allowed.) The player who cannot make a move loses. Who wins: the first player or their opponent?
Solve the problem by replacing 30 in the statement with $N$.

A. Talalay

Exploration

Let the black piece start at cell $1$ and the white piece at cell $N$. A move consists of moving one's own piece by one cell to the left or to the right. A move is legal only if after the move the two pieces do not occupy the same cell. Since the row is finite, eventually some player may become unable to move.

The natural state variable is the distance

$$d=w-b,$$

where $b$ and $w$ are the positions of the black and white pieces. Since the pieces may not coincide, we always have $d\ge 1$.

When $d>1$, each player can either increase or decrease $d$ by $1$. Indeed, moving the black piece right decreases $d$ by $1$, moving it left increases $d$ by $1$; similarly for the white piece. When $d=1$, the pieces occupy adjacent cells. Then neither player may decrease $d$, because that would place the pieces on the same cell. Hence from $d=1$ the only legal moves increase $d$ to $2$.

The game depends only on $d$. The possible values are

$$1,2,\dots,N-1.$$

At $d=N-1$ the pieces stand at the two ends of the row. From this position neither piece can move outward, so every legal move decreases $d$ to $N-2$.

Try small cases.

For $N=2$, the only state is $d=1$. The first player moves to $d=0$? No, that is illegal. Thus there is no move at all. The first player loses.

For $N=3$, states are $d=1,2$. From $d=2$ one must move to $d=1$. From $d=1$ one must move to $d=2$. The game alternates forever unless we interpret the board boundaries carefully. Looking directly at the positions, $(1,3)$ is the only state. Neither piece can move outward, but either can move inward to obtain adjacent pieces. Then from adjacency the next player has no legal move, because moving away would require moving the piece that is not theirs. Thus the distance description alone misses whose turn it is and which configurations realize a given distance.

A better description is to record the pair of positions. Let

$$G(b,w)$$

denote the position. Legal moves are exactly those that keep

$$1\le b<w\le N.$$

Compute small cases.

For $N=2$, position $(1,2)$ has no legal move.

For $N=3$, from $(1,3)$ either player moves to $(2,3)$ or $(1,2)$. Both of those positions have exactly one legal move, returning to $(1,3)$. Hence $(1,3)$ is losing.

For $N=4$, positions with adjacent pieces at an end, namely $(1,2)$ and $(3,4)$, have one move each. The starting position is $(1,4)$. Tracing the game suggests that $(1,4)$ is winning.

Let

$$x=b-1,\qquad y=N-w.$$

Then $x$ is the number of empty cells to the left of the black piece and $y$ the number of empty cells to the right of the white piece. A move changes exactly one of $x,y$ by $\pm1$, provided it remains nonnegative and the pieces do not cross.

The number of cells between the pieces is

$$k=w-b-1.$$

Since

$$x+y+k=N-2,$$

the state is determined by $(x,y)$ with

$$x,y\ge0,\qquad x+y\le N-2.$$

A move changes one coordinate by $\pm1$. This is exactly the game of a token moving on the triangular lattice

$$x,y\ge0,\quad x+y\le N-2.$$

The starting position is $(0,0)$.

Computing Grundy parity for small $N$ gives:

$$N=2:\ (0,0)\ \text{losing},$$

$$N=3:\ (0,0)\ \text{losing},$$

$$N=4:\ (0,0)\ \text{winning},$$

$$N=5:\ (0,0)\ \text{winning},$$

$$N=6:\ (0,0)\ \text{losing}.$$

This suggests period $4$:

$$N\equiv2,3\pmod4 \Rightarrow \text{losing},$$

$$N\equiv0,1\pmod4 \Rightarrow \text{winning}.$$

The crucial point is to prove the pattern on the triangular board.

Problem Understanding

We have a row of $N$ cells. The black piece occupies the leftmost cell and the white piece the rightmost cell. Players alternate moves. On each turn a player must move the corresponding piece by one cell left or right. The move must keep the pieces in distinct cells. A player who has no legal move loses.

This is a Type A problem, a complete classification problem. We must determine for which values of $N$ the initial position is winning for the first player and for which values it is losing.

The core difficulty is that the legal moves depend simultaneously on the positions of both pieces and on the board boundaries. A useful representation must expose enough symmetry to classify all starting positions.

The answer will be that the initial position is losing precisely when

$$N\equiv2,3\pmod4,$$

and winning precisely when

$$N\equiv0,1\pmod4.$$

Proof Architecture

Define coordinates $x=b-1$ and $y=N-w$, so the game is played on the set of lattice points $(x,y)$ satisfying $x,y\ge0$ and $x+y\le N-2$.

Show that a legal move changes exactly one coordinate by $\pm1$, provided the resulting point remains in the triangular region.

Introduce the quantity

$$s=x+y.$$

The triangle consists of layers $s=0,1,\dots,N-2$.

Prove by induction on $s$ that every position with $s\equiv0,1\pmod4$ is losing and every position with $s\equiv2,3\pmod4$ is winning.

The induction works because every move changes $s$ by exactly $1$, and interior positions have neighbors in both adjacent layers while boundary positions still have at least one neighbor in each feasible adjacent layer.

Apply the classification to the initial position $(0,0)$, for which $s=0$ inside the triangle of size $N-2$, and translate the result into a condition on $N$.

The most delicate point is verifying that the inductive pattern remains valid on the boundary layer $s=N-2$, where moves increasing $s$ are impossible.

Solution

Let the black piece occupy cell $b$ and the white piece occupy cell $w$. Since the pieces must remain distinct,

$$1\le b<w\le N.$$

Define

$$x=b-1,\qquad y=N-w.$$

Then $x$ and $y$ are nonnegative integers. Furthermore,

$$w-b=(N-y)-(x+1)=N-1-(x+y),$$

and the condition $b<w$ becomes

$$x+y\le N-2.$$

Hence every position of the game corresponds to a lattice point

$$(x,y),\qquad x\ge0,\ y\ge0,\ x+y\le N-2.$$

A move of the black piece changes $b$ by $\pm1$, hence changes $x$ by $\pm1$ and leaves $y$ unchanged. A move of the white piece changes $w$ by $\pm1$, hence changes $y$ by $\mp1$ and leaves $x$ unchanged. Therefore every legal move changes exactly one coordinate by $1$ or $-1$, and the resulting point must remain inside the triangle

$$T_N={(x,y):x\ge0,\ y\ge0,\ x+y\le N-2}.$$

Set

$$s=x+y.$$

Every move changes $s$ by exactly $1$.

We shall determine all losing positions.

For each integer $m$ with $0\le m\le N-2$, let

$$L_m={(x,y)\in T_N:x+y=m}.$$

We claim that a position is losing if and only if

$$N-2-s\equiv0\ \text{or}\ 1\pmod4.$$

The proof is by induction downward from the top layer.

The top layer is $s=N-2$. Every point of this layer has no move to a layer with larger $s$, because it already lies on the boundary $x+y=N-2$. Every legal move decreases $s$ to $N-3$. Thus all positions of layer $N-2$ have moves only to layer $N-3$.

The next layer is $s=N-3$. Every point of this layer has at least one move to layer $N-2$ and possibly other moves to layer $N-4$.

We now prove the classification.

Let

$$r=N-2-s.$$

Thus $r$ measures the distance in layers from the top boundary.

We show that

$$r\equiv0,1\pmod4 \Longrightarrow \text{losing},$$

and

$$r\equiv2,3\pmod4 \Longrightarrow \text{winning}.$$

For $r=0$, that is $s=N-2$, every move goes to $r=1$. Hence these positions are losing once all positions with $r=1$ are winning.

For $r=1$, every position has a move to $r=0$. Thus if $r=0$ is losing, then $r=1$ is winning.

For $r=2$, every move goes either to $r=1$ or to $r=3$. Since there is always a move to $r=1$, which is winning, the position is losing only if all moves lead to winning positions. We shall see inductively that $r=3$ is also winning; hence $r=2$ is losing.

For $r=3$, there is always a move to $r=2$, so $r=3$ is winning.

The pattern repeats every four layers. Formally, assume all layers with smaller $r$ satisfy the stated rule. Consider a position with $r\ge4$.

$$r\equiv0 \pmod4,$$

then every move leads to layers with values $r-1$ or $r+1$. These are congruent to $3$ and $1$ modulo $4$, hence winning by the inductive rule. Therefore the position is losing.

$$r\equiv1 \pmod4,$$

there exists a move to layer $r-1\equiv0\pmod4$, which is losing. Therefore the position is winning.

$$r\equiv2 \pmod4,$$

every move leads to layers congruent to $1$ or $3$ modulo $4$, both winning. Therefore the position is losing.

$$r\equiv3 \pmod4,$$

there exists a move to layer $r-1\equiv2\pmod4$, which is losing. Therefore the position is winning.

Thus the losing positions are exactly those with

$$r\equiv0\ \text{or}\ 2\pmod4.$$

Since

$$r=N-2-s,$$

the starting position $(0,0)$ has

$$s=0,\qquad r=N-2.$$

Hence the initial position is losing exactly when

$$N-2\equiv0\ \text{or}\ 2\pmod4,$$

that is,

$$N\equiv2\ \text{or}\ 0\pmod4.$$

It is winning exactly when

$$N\equiv1\ \text{or}\ 3\pmod4.$$

For the original problem,

$$30\equiv2\pmod4,$$

so the initial position is losing. The second player wins with correct play.

Therefore

$$\boxed{\text{The first player loses iff }N\equiv0,2\pmod4;\ \text{the first player wins iff }N\equiv1,3\pmod4.}$$

Verification of Key Steps

The first delicate point is the coordinate model. From

$$x=b-1,\qquad y=N-w,$$

we obtain

$$w-b=N-1-(x+y).$$

The condition $b<w$ is equivalent to $x+y\le N-2$. No other restriction appears. Thus the state space is exactly the triangular lattice region.

The second delicate point is the existence of a move from a layer $r\equiv1$ or $3\pmod4$ to the preceding layer $r-1$. Since $r>0$, we have $s<N-2$. Hence the position is not on the top boundary. At least one of the moves increasing $s$ is legal, so a move to layer $r-1$ always exists.

The third delicate point is the classification of positions with $r\equiv0$ or $2\pmod4$. Every move changes $r$ by $\pm1$. Thus such a position can move only to layers congruent to $1$ or $3$ modulo $4$. The inductive hypothesis classifies both as winning. Hence no move reaches a losing position.

Alternative Approaches

A different approach is to color the layers of the triangular board periodically with four colors according to the value of

$$r=N-2-(x+y).$$

One then proves directly that every move changes the color to an adjacent one in the cycle

$$0\leftrightarrow1\leftrightarrow2\leftrightarrow3,$$

and the pattern of winning and losing layers follows from backward induction beginning with the top boundary.

Another approach uses the Sprague-Grundy function. Because every move changes $r$ by $\pm1$, the Grundy value depends only on $r$. Computing the first few values gives

$$0,1,0,1,0,1,\dots$$

on alternating parity classes of $r$, from which the same modular classification follows. The layer argument is preferable because it avoids introducing impartial-game machinery and makes the geometry of the state space explicit.