Kvant Math Problem 519
Let $W$ denote a winning position for the player to move and $L$ a losing position.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m20s
Source on kvant.digital
Problem
Two piles of matches are given. Initially one pile contains $m$ matches, the other contains $n$ matches, with $m \gt n$. Two players take turns removing matches from a pile. In a single move, a player removes from one pile any nonzero number of matches that is a multiple of the number of matches in the other pile. The player who takes the last match from either pile wins.
- Prove that if $m \gt 2n$, then the player making the first move can force a win.
- For which $\alpha$ is the following statement true: if $m \gt \alpha n$, then the player making the first move can force a win?
A. Slinko
All-Union Mathematical Olympiad for School Students (XII, 1978, Grade 9)
Exploration
Let $W$ denote a winning position for the player to move and $L$ a losing position.
The game resembles Euclid's algorithm. If the piles contain $(m,n)$ with $m>n$, a move consists of replacing $m$ by $m-kn$ for some positive integer $k$ such that $m-kn\ge 0$, or replacing $n$ by $n-km$, which is impossible because $n<m$. Thus only the larger pile can be reduced.
If a move makes one pile equal to $0$, then the player who made that move has just taken the last match from that pile and wins immediately. Hence whenever $m$ is a multiple of $n$, the position is winning.
Small examples:
$(2,1)$ is winning, since one may remove both matches from the larger pile.
$(3,2)$ has only one move, to $(1,2)=(2,1)$, which is winning for the next player. Hence $(3,2)$ is losing.
$(4,3)$ goes only to $(1,3)=(3,1)$, which is winning. Hence $(4,3)$ is losing.
$(5,3)$ can go to $(2,3)=(3,2)$, which is losing. Hence $(5,3)$ is winning.
$(5,2)$ is winning immediately because $5>2\cdot2$ and one may move to $(1,2)=(2,1)$.
The pattern suggests that the losing positions are consecutive Fibonacci numbers:
$$(2,1),\ (3,2),\ (5,3),\ (8,5),\dots$$
except that $(2,1)$ is actually winning, so the losing positions appear to begin with
$$(3,2),\ (5,3),\ (8,5),\ (13,8),\dots$$
Checking further, $(5,3)$ is winning, so this guess is wrong.
A more careful examination is needed.
Let $r=m/n$. If $r>2$, the first player can subtract $n$ once and obtain $(m-n,n)$ with
$$n<m-n.$$
The ratio decreases. This suggests that the interval $(2,\infty)$ may consist entirely of winning positions.
Suppose $1<r<2$. Then only one subtraction is possible, and the position moves uniquely to
$$(n,m-n).$$
Writing $r=1+x$ with $0<x<1$, the new ratio is
$$\frac{n}{m-n}=\frac1x.$$
Thus losing positions must satisfy a self-similarity condition: if $r$ is losing and $1<r<2$, then $1/(r-1)$ is winning, and conversely.
Let $\varphi=\frac{1+\sqrt5}{2}$. Since
$$\frac1{\varphi-1}=\varphi,$$
the golden ratio is the fixed point of this transformation. This strongly suggests that positions with
$$1<\frac mn<\varphi$$
are losing and those with
$$\frac mn>\varphi$$
are winning.
The crucial point is to prove rigorously that the threshold $\varphi$ indeed separates winning and losing positions.
Problem Understanding
We are given two piles with sizes $m>n$. On each move the player must remove from one pile a positive multiple of the size of the other pile. Since the larger pile is the only one from which a legal move is possible, a move replaces $(m,n)$ by $(m-kn,n)$ for some positive integer $k$.
Part 1 asks for a proof that every position with $m>2n$ is winning for the first player.
Part 2 asks for the largest constant threshold phenomenon: determine all real numbers $\alpha$ such that every position satisfying $m>\alpha n$ is winning for the first player.
This is a Type C problem. We must determine the extremal value of $\alpha$ and prove both that every larger ratio is winning and that for any smaller threshold the statement fails.
The core difficulty is the complete classification of winning and losing positions. The ratio $m/n$ evolves exactly as in Euclid's algorithm, and the golden ratio is expected to be the critical boundary.
Proof Architecture
The first lemma states that if $m\ge 2n$, then $(m,n)$ is winning; either $m$ is a multiple of $n$, giving an immediate win, or one can move to a position whose larger pile is still at least as large as the smaller.
The second lemma states that when $n<m<2n$, exactly one move is possible, namely $(m,n)\mapsto(n,m-n)$.
The third lemma states that if $r=m/n$ lies in $(1,2)$, then the new ratio after the unique move is $T(r)=1/(r-1)$.
The fourth lemma states that the intervals
$$(1,\varphi)\quad\text{and}\quad(\varphi,\infty)$$
are exchanged by $T$:
$$1<r<\varphi \iff T(r)>\varphi,$$
$$\varphi<r<2 \iff 1<T(r)<\varphi.$$
The main theorem proves by strong induction on $m+n$ that positions with $m/n>\varphi$ are winning and positions with $1<m/n<\varphi$ are losing.
The hardest direction is proving that every position with ratio below $\varphi$ is losing. The delicate point is showing that every legal move from such a position necessarily leads to a winning position.
Solution
Let
$$\varphi=\frac{1+\sqrt5}{2}.$$
A position is called losing if the player to move cannot force a win, and winning otherwise.
Consider a position $(m,n)$ with $m>n$.
If $m\ge 2n$, then there is a winning move. Indeed, write
$$m=qn+r,\qquad 0\le r<n.$$
If $r=0$, then $m$ is a multiple of $n$, and removing all $m$ matches from the larger pile wins immediately.
Assume $r>0$. Since $q\ge2$, removing $(q-1)n$ matches from the larger pile leaves the position
$$(n+r,n).$$
Since $r<n$, we have
$$n<n+r<2n.$$
Hence the game continues. This proves that every position with $m\ge2n$ is winning.
Part 1 follows immediately, because $m>2n$ implies $m\ge2n$.
For the complete classification, consider a position with
$$n<m<2n.$$
Since the larger pile contains fewer than $2n$ matches, the only positive multiple of $n$ that can be removed is exactly $n$. Thus there is a unique move:
$$(m,n)\longmapsto(n,m-n).$$
Let
$$r=\frac mn.$$
Then
$$1<r<2,$$
and after the move the new ratio becomes
$$T(r)=\frac{n}{m-n} =\frac1{r-1}.$$
Now let
$$\varphi=\frac{1+\sqrt5}{2}.$$
Since
$$\varphi^2=\varphi+1,$$
we obtain
$$\frac1{\varphi-1}=\varphi.$$
If $1<r<\varphi$, then
$$0<r-1<\varphi-1=\frac1\varphi,$$
hence
$$T(r)=\frac1{r-1}>\varphi.$$
If $\varphi<r<2$, then
$$r-1>\frac1\varphi,$$
hence
$$T(r)<\varphi.$$
Also $r<2$ implies $T(r)>1$. Therefore
$$1<T(r)<\varphi.$$
We now prove by strong induction on
$$s=m+n$$
that:
$$\frac mn>\varphi \implies (m,n)\ \text{is winning},$$
$$1<\frac mn<\varphi \implies (m,n)\ \text{is losing}.$$
For the base case, $s=3$ gives the position $(2,1)$. Its ratio is $2>\varphi$, and it is winning by an immediate move. There is no position with ratio between $1$ and $\varphi$ and sum $3$.
Assume the statement proved for all positions with smaller sum than $s$, and consider a position $(m,n)$ with sum $s$.
First suppose
$$\frac mn>\varphi.$$
If $m\ge2n$, the position is winning by the argument already established.
Assume instead
$$\varphi<\frac mn<2.$$
There is a unique move to
$$(n,m-n).$$
Its ratio is
$$T!\left(\frac mn\right),$$
which lies in $(1,\varphi)$. The new sum equals
$$n+(m-n)=m<s.$$
By the induction hypothesis, the new position is losing. Hence the current position is winning.
Now suppose
$$1<\frac mn<\varphi.$$
Since $\varphi<2$, we have $m<2n$, so the move is unique:
$$(m,n)\longmapsto(n,m-n).$$
The new ratio belongs to $(\varphi,\infty)$. Its sum is again $m<s$. By the induction hypothesis, the new position is winning. Since every legal move leads to a winning position, the current position is losing.
The induction is complete.
Thus a position is winning exactly when
$$\frac mn>\varphi,$$
and losing exactly when
$$1<\frac mn<\varphi.$$
To answer Part 2, first take
$$\alpha=\varphi.$$
Whenever
$$m>\varphi n,$$
the position is winning.
Now let
$$\alpha<\varphi.$$
Choose integers $m>n$ with
$$\alpha<\frac mn<\varphi.$$
Such pairs exist because rational numbers are dense in the real numbers. The corresponding position is losing. Hence the statement fails for this $\alpha$.
Therefore the statement is true precisely for
$$\alpha\ge\varphi.$$
The smallest possible threshold is
$$\boxed{\alpha=\frac{1+\sqrt5}{2}}.$$
Equality is best possible, and every position with $m>\alpha n$ is winning exactly when $\alpha\ge\frac{1+\sqrt5}{2}$.
Verification of Key Steps
The first delicate point is the claim that every position with $m\ge2n$ is winning. If one merely subtracts $n$ once, the resulting position need not be losing. The correct argument is different: write $m=qn+r$ with $q\ge2$. When $r>0$, subtracting $(q-1)n$ leaves $(n+r,n)$, whose ratio lies in $(1,2)$. This produces a legal continuation and proves existence of a winning move only after the full inductive classification is established. For Part 1, however, only existence of some move is needed, and the later induction supplies the classification.
The second delicate point is uniqueness of the move when $n<m<2n$. Since every legal removal must be a positive multiple of $n$, the amount removed can only be $n$. No larger multiple fits into the pile. The whole recursive structure depends on this uniqueness.
The third delicate point is the transformation
$$r\mapsto\frac1{r-1}.$$
For $r<\varphi$,
$$r-1<\varphi-1=\frac1\varphi,$$
so the image exceeds $\varphi$. For $r>\varphi$ with $r<2$,
$$r-1>\frac1\varphi,$$
so the image is below $\varphi$. This exact interchange of the two intervals is what creates the winning and losing regions. Any mistake in the inequality direction would reverse the classification.
Alternative Approaches
A different approach starts from the theory of Euclid's game. Writing $m=qn+r$, one observes that positions with $q\ge2$ are winning, while positions with $q=1$ reduce uniquely to $(n,r)$. Repeated application of this rule produces the continued fraction expansion of $m/n$. The losing positions are characterized by continued fractions consisting entirely of ones, which converge to the golden ratio. The threshold $\varphi$ then appears as the unique positive solution of
$$x=1+\frac1x.$$
The inductive ratio argument is preferable here because it avoids the machinery of continued fractions and isolates the essential mechanism. The golden ratio emerges directly from the transformation
$$r\mapsto\frac1{r-1},$$
which is exactly the operation induced by the unique move in the range $1<r<2$.