I come across a video about an endgame problem in Xiangqi (the Chinese chess). In this problem, there is a winning strategy for the side (red side) that moves first. Lying at the heart of this problem is another problem that can be visualized as a simple marble game. The game starts with two jars of marbles such that at least one jar is non-empty. Two players take turns to pick one of the two jars and draw $n ≥ 1$ marbles from the chosen jar. The one who takes the last marble wins.

It can be proved that the player that makes the first draw will win if and only if the two jars have unequal number of marbles. The following proof is adapted from an answer to a similar marble problem by user PSPACEhard on Mathematics Stackexchange.

Let $x_i$ and $y_i$ be the numbers of marbles of the two jars in the $i$-th turn before the player makes a draw.

Observation 1
If $x_i=y_i$, in whatever way the player in the $i$-th turn makes his draw, $x_{i+1}\neq y_{i+1}$.

Observation 2
If $x_i\neq y_i$, the player in the $i$-th turn can choose the jar with more marbles and draw enough marbles so that $x_{i+1}=y_{i+1}$.

If $x_i=y_i$, we say that the $i$-th turn is an L-turn. Note that a player cannot draw the last marble in an L-turn because $x_i=y_i\neq 0$ and the player cannot deplete both jars in a single turn.

If $x_i\neq y_i$, we say that the $i$-th turn is a W-turn.

According to the two observations, we have the following conclusions.

  • If a player is in an L-turn, the next turn must be a W-turn for his opponent.

  • If a player is in an W-turn, the player can always choose the jar with more marbles and draw enough marbles such that the next turn will be a L-turn for his opponent.

If the two jars have the same number of marbles initially, the first turn is an L-turn for the first player. And the next turn will always be a W-turn for the opponent. The opponent can always make a draw such that the first player will continue to be in an L-turn. This cycle repeats until the opponent draws the last marble in a W-turn.

If the two jars have different number of marbles initially, the first player will be able to draw the last marble by a similar argument.

References

  1. The Xiangqi endgame example by Shiro speaks chess

  2. A similar marble problem on Mathematics Stackexchange