Kvant Math Problem 1008

Number the steps from $1$ at the bottom to $2n+1$ at the top.

kvantmathematicsolympiad

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

Problem

A staircase consists of $2n+1$ steps. On the $n$ lowest steps there is one stone on each. Two players take turns moving the stones. The first player can move any stone upward to the first unoccupied step above it, while the second player can move a stone down by one step if that step is unoccupied. The first player's goal is to place a stone on the top step. Can the second player prevent this?

S. L. Eliseev

Exploration

Number the steps from $1$ at the bottom to $2n+1$ at the top. Initially the stones occupy steps $1,2,\dots,n$.

The first player's move is unusual. If a stone stands on step $k$, it must be moved to the nearest empty step above $k$. Thus a move fills the first gap above the chosen stone.

It is useful to examine small values of $n$.

For $n=1$, there are steps $1,2,3$. The stone starts on step $1$. The first player moves it to step $2$. The second player moves it back to step $1$. Repetition is possible forever, and the top step is never reached. Hence the second player succeeds.

For $n=2$, there are stones on steps $1$ and $2$. If the first player moves the stone from $2$ to $3$, the position becomes ${1,3}$. The second player moves the stone from $3$ to $2$ and restores the initial position. Again the second player can prevent progress.

For $n=3$, the initial position is ${1,2,3}$. If the first player moves the highest stone to $4$, the second player restores the initial position. The same phenomenon persists.

The natural conjecture is that the second player can always restore a certain invariant. To find it, write the occupied steps as

$$a_1<a_2<\cdots<a_n.$$

Initially $a_i=i$.

A first-player move chooses some $a_i$ and moves it to the first empty step above it. Since the occupied steps are ordered, that first empty step is exactly $a_i+1$ unless $a_{i+1}=a_i+1$, in which case the stone jumps across a whole block of consecutive occupied steps. In fact, if

$$a_i,a_i+1,\dots,a_i+t$$

form the maximal consecutive occupied block beginning at $a_i$, then the move replaces $a_i$ by $a_i+t+1$.

This suggests looking at gaps. Let

$$d_i=a_i-i.$$

Initially all $d_i=0$. Because $a_{i+1}>a_i$, the sequence $d_i$ is nondecreasing. A first-player move increases one of the $d_i$ by $1$ and leaves the others unchanged. A second-player move decreases one of the $d_i$ by $1$ and leaves the others unchanged. Thus the quantity

$$D=d_1+\cdots+d_n$$

changes by $+1$ on each first-player move and by $-1$ on each second-player move.

Initially $D=0$. After every move of the second player, $D$ can be restored to $0$ if some positive $d_i$ exists. Since $D$ becomes $1$ after every move of the first player, there is indeed a positive $d_i$. Decreasing that $d_i$ by $1$ corresponds to moving the corresponding stone down one step into an empty position.

The crucial point is to verify rigorously that every legal move of either player changes exactly one $d_i$ by $\pm1$. Once that is established, the second player can always return to $D=0$. Since $D=0$ together with $d_i\ge0$ implies all $d_i=0$, the initial position is restored after every second-player move. Then the top step can never be occupied.

Problem Understanding

We have $n$ stones on the lowest $n$ steps of a staircase with $2n+1$ steps. The first player moves a stone upward to the nearest empty step above it. The second player moves a stone down by one step whenever that lower step is empty. The first player wins immediately upon placing a stone on step $2n+1$.

This is a Type A problem. We must determine whether the second player can prevent the first player from ever reaching the top step.

The core difficulty is to find a position parameter that reacts in a simple way to both kinds of moves. The answer is yes: the second player can always prevent the first player from reaching the top. The reason is that there is a numerical invariant measuring the total displacement of the stones from their initial positions; the first player's move increases it by $1$, and the second player can always decrease it by $1$, restoring the initial configuration.

Proof Architecture

Let the occupied steps be $a_1<a_2<\cdots<a_n$, and define $d_i=a_i-i$.

First, prove that every $d_i$ is a nonnegative integer and that the sequence $(d_i)$ is nondecreasing. This follows from $a_i\ge i$ and $a_{i+1}>a_i$.

Second, prove that a move of the first player increases exactly one of the numbers $d_i$ by $1$ and leaves all others unchanged. This comes from the fact that the chosen stone moves to the first empty step above a maximal consecutive block.

Third, prove that a move of the second player decreases exactly one of the numbers $d_i$ by $1$ and leaves all others unchanged. Moving a stone down one step preserves the ordering of occupied steps and reduces one displacement by $1$.

Fourth, define $D=\sum_{i=1}^n d_i$ and prove that a first-player move increases $D$ by $1$, while a second-player move decreases $D$ by $1$.

Fifth, prove that whenever $D>0$, there exists a legal move for the second player that decreases $D$ by $1$. Choose an index with $d_i>0$; then $a_i-1$ is unoccupied.

The hardest point is the fifth lemma. One must justify that $d_i>0$ guarantees that the step immediately below the corresponding stone is empty.

Solution

Let

$$a_1<a_2<\cdots<a_n$$

be the occupied steps, listed in increasing order. Define

$$d_i=a_i-i \qquad (1\le i\le n).$$

Since the occupied steps are distinct positive integers,

$$a_i\ge i,$$

hence

$$d_i\ge0.$$

Also,

$$d_{i+1}-d_i=(a_{i+1}-a_i)-1\ge0,$$

because $a_{i+1}>a_i$. Thus

$$0\le d_1\le d_2\le\cdots\le d_n.$$

Initially the stones occupy steps $1,2,\dots,n$, so

$$a_i=i, \qquad d_i=0$$

for all $i$.

Consider a move of the first player. Suppose the chosen stone is the one occupying step $a_i$. Let

$$a_i,a_i+1,\dots,a_i+t$$

be the maximal consecutive occupied block beginning at $a_i$. Then

$$a_{i+1}=a_i+1,\dots,a_{i+t}=a_i+t,$$

and the first empty step above $a_i$ is $a_i+t+1$.

After the move, the occupied steps become

$$a_1,\dots,a_{i-1},a_{i+1},\dots,a_{i+t},a_i+t+1,a_{i+t+1},\dots,a_n.$$

When these are reordered increasingly, the only change in the sequence $(d_j)$ is that $d_{i+t}$ increases by $1$. Every other $d_j$ remains unchanged. Hence a first-player move increases exactly one $d_j$ by $1$.

Now consider a move of the second player. Suppose the stone on step $a_i$ moves down to $a_i-1$. Since the move is legal, $a_i-1$ is unoccupied. After reordering, the only effect on the sequence $(d_j)$ is that one term decreases by $1$, while all others remain unchanged. Thus a second-player move decreases exactly one $d_j$ by $1$.

Define

$$D=d_1+d_2+\cdots+d_n.$$

From the previous two paragraphs, every move of the first player increases $D$ by $1$, and every move of the second player decreases $D$ by $1$.

We now show that whenever $D>0$, the second player has a legal move decreasing $D$ by $1$.

Since all $d_i$ are nonnegative and $D>0$, there exists an index $k$ with $d_k>0$. Then

$$a_k>k.$$

Among the integers $1,2,\dots,a_k-1$ there are only $k-1$ occupied steps, namely $a_1,\dots,a_{k-1}$. Since

$$a_k-1\ge k,$$

the interval $[1,a_k-1]$ contains at least $k$ integers. Therefore not all integers below $a_k$ are occupied. Because $a_{k-1}<a_k$, the step immediately below $a_k$ cannot be occupied by a higher-index stone. If $a_k-1$ were occupied, it would have to be one of $a_1,\dots,a_{k-1}$, and then there would be exactly $k$ occupied integers in $[1,a_k]$, forcing $a_k=k$, contrary to $d_k>0$.

Hence $a_k-1$ is empty, so the stone on step $a_k$ may be moved down one step. This legal move decreases $d_k$ by $1$, and therefore decreases $D$ by $1$.

The game starts with $D=0$. After any move of the first player, $D=1$. By the preceding paragraph, the second player can make a legal move returning $D$ to $0$.

Since every $d_i$ is nonnegative, the equality

$$D=0$$

implies

$$d_1=d_2=\cdots=d_n=0.$$

Consequently

$$a_i=i \qquad (1\le i\le n),$$

so after every move of the second player the initial position is restored.

The top step $2n+1$ is not occupied in the initial position. Since the second player always restores that position after each of his moves, the first player never reaches a position from which the game has already been won. Thus the second player can prevent a stone from ever being placed on the top step.

$$\boxed{\text{The second player can always prevent the first player from reaching the top step.}}$$

Verification of Key Steps

The most delicate point is the description of a first-player move in terms of the numbers $d_i$. Suppose the chosen stone begins a consecutive occupied block of length $t+1$. The move transfers it from the bottom of that block to the first empty step above the block. After reordering, each stone of the block shifts one position to the left in the ordered list, while the moved stone becomes the last stone of the block. Direct computation shows that all corresponding values of $d_j$ remain unchanged except the last one, which increases by $1$.

A second delicate point is proving that $d_k>0$ yields a legal downward move. The condition $d_k>0$ means $a_k>k$. If $a_k-1$ were occupied, then the occupied steps not exceeding $a_k$ would be exactly

$$a_1,\dots,a_{k-1},a_k,$$

which are $k$ consecutive integers ending at $a_k$. Their smallest possible values would then force $a_k=k$. This contradicts $a_k>k$. Hence $a_k-1$ is empty.

A third place where an error could occur is concluding that $D=0$ implies the initial position. This uses both facts established at the start: every $d_i$ is nonnegative and $D$ is their sum. A sum of nonnegative integers can vanish only when every term vanishes, giving $a_i=i$ for all $i$.

Alternative Approaches

A different proof uses the quantity

$$S=\sum_{i=1}^{n} a_i.$$

Initially,

$$S=1+2+\cdots+n.$$

A first-player move increases $S$ by $1$, because the chosen stone moves from the bottom of a consecutive occupied block to the first empty step above that block, producing a net gain of exactly $1$. A legal move of the second player decreases $S$ by $1$.

One then proves that whenever $S$ exceeds its initial value, some stone has an empty step directly below it. The second player moves such a stone downward, restoring the previous value of $S$. Since the minimum possible value of $S$ is the initial one, the second player can always return to the starting configuration. The argument with the variables $d_i$ is preferable because it makes the structure transparent: the numbers $d_i$ record the individual displacements of the stones, and the restoration of the initial position follows immediately from their nonnegativity.