Alice and Bob are playing a game in which they take turns modifying a $k$-tuple $(t_1,\ldots,t_k)$ of positive integers. Alice plays first. On each turn, a player subtracts a positive multiple of $t_i$ from $t_j$ for some $i\neq j$, subject to the condition that the resulting $k$-tuple consists of positive integers. A player loses if they have no valid moves.
For a given positive integer $k$ and $k$-tuple $(t_1,\ldots,t_k)$ of positive integers, who has a winning strategy and what is it?
I have a solution for the $k=2$ case, which I will include here. Let $\phi=\frac{\sqrt{5}+1}{2}$ be the golden ratio. Observe that $\phi$ is irrational, and $\frac{1}{\phi}=\phi-1$.
Clearly the order of the entries in a $k$-tuple does not affect who has a winning strategy. We will order all 2-tuples (pairs) of positive integers $(a,b)$ so that $a\geq b$.
Claim: Alice has a winning strategy for the pair $(a,b)$, where $a\geq b$ are positive integers, if and only if $\frac{a}{b}>\phi$.
Proof: It suffices to show the following for positive integers $a\geq b$.
a) If $\frac{a}{b}>\phi$, then there exists a valid move $(a,b)\to (a',b')$ with $a'\leq b'$ and $\frac{a'}{b'}<\phi$.
b) If $\frac{a}{b}<\phi$, then all valid moves $(a,b)\to (a',b')$ with $a'\geq b'$ satisfy $\frac{a'}{b'}>\phi$.
We first prove b). If $a=b$ then there are no valid moves. If $a>b$ and $\frac{a}{b}<\phi$, then $b<a<\phi b<2b$. Hence there is exactly one valid move, namely $(a,b)\to(b,a-b)$. Clearly $a-b<b$, and $\frac{a-b}{b}=\frac{a}{b}-1<\phi-1=\frac{1}{\phi}$, hence $\frac{b}{a-b}>\phi$ as required.
We now prove a). Let $a,b$ be positive integers with $\frac{a}{b}>\phi$. Write $a=qb+r$ for integers $q,r$, where $0\leq r<b$. Consider the following move $$(a,b)\to\begin{cases} (b,r) & \text{if } b<\phi r, \\ (b+r,b) & \text{otherwise.} \end{cases}$$
The first move is obtained by subtracting $qb$ from $a$, while the second is obtained by subtracting $(q-1)b$ from $a$. In both cases, the resulting pair consists of positive integers. To show this is a valid move, we must show that we are subtracting a positive integer multiple of $b$ from $a$. Since $a>b$, the integer $q$ is positive. If $r=0$, then $a\geq 2b$, hence $q-1$ is positive. If $r\neq0$ and $b>\phi r$, then
$$a-r>b\phi-\frac{b}{\phi}=b,$$
hence $a-r\geq 2b$, so $q-1$ is positive. Thus the described move is valid.
Observe now that if $b<\phi r$ then $\frac{b}{r}<\phi$, as required. If $b>\phi r$, then
$$\frac{b+r}{b}=1+\frac{r}{b}<1+\frac{1}{\phi}=\phi,$$ as required. $\square$
from Hot Weekly Questions - Mathematics Stack Exchange
Post a Comment