4
$\begingroup$

Two players play a game in which at the beginning a number $n\geq 2$ is written. Each turn, a player can either subtract $1$ from the number, or divide the number by $3$ if the number is divisible by $3$. The player who can turn the number into $1$ wins. For which values of $n$ does the first player have a winning strategy?

Among the numbers from $2$ to $20$, the ones for which the first player can win are $2,3,5,7,9,11,12,14,16,18,20$. At first the winning numbers are odd, but that changes because for the number $12$, the first player can win by dividing by $3$. After that the winning numbers are even.

$\endgroup$
  • $\begingroup$ Some more odd numbers are winning, aren't they? Like, 39? $\endgroup$ – Gerry Myerson Feb 8 '17 at 5:58
  • $\begingroup$ Absolutely. I just meant within the first 20 numbers. $\endgroup$ – pi66 Feb 8 '17 at 6:07
1
$\begingroup$

The answer is $$\small n=2,\frac{3^{2m}-3}{2},\frac{3^{2m}+1}{2},\frac{3^{2m}+5}{2},\cdots,\frac{3^{2m+1}-5}{2},\frac{3^{2m+1}-3}{2},\frac{3^{2m+1}+1}{2},\frac{3^{2m+1}+5}{2},\cdots ,\frac{3^{2m+2}-5}{2}$$ where $m\ge 1\in\mathbb Z$.

Let us prove this by induction on $m$.

The base case where $m=1$ is easy to check.

Suppose that the first player has a winning strategy for $$\small n=\frac{3^{2m}-3}{2},\frac{3^{2m}+1}{2},\frac{3^{2m}+5}{2},\cdots,\frac{3^{2m+1}-5}{2},\frac{3^{2m+1}-3}{2},\frac{3^{2m+1}+1}{2},\frac{3^{2m+1}+5}{2},\cdots ,\frac{3^{2m+2}-5}{2}$$ and that the first player does not have a winning strategy for $$\small n=\frac{3^{2m}-1}{2},\frac{3^{2m}+3}{2},\frac{3^{2m}+7}{2},\cdots,\frac{3^{2m+1}-7}{2},\frac{3^{2m+1}-1}{2},\frac{3^{2m+1}+3}{2},\frac{3^{2m+1}+7}{2},\cdots ,\frac{3^{2m+2}-7}{2}$$

Now, the first player has a winning strategy for $n=\frac{3^{2m+2}-3}{2}$ choosing to divide by $3$ to get $\frac{3^{2m+1}-1}{2}$.

So, the first player does not have a winning strategy for $n=\frac{3^{2m+2}-1}{2}$, which is not divisible by $3$, since subtracting $1$ gives $\frac{3^{2m+2}-3}{2}$.

So, the first player has a winning strategy for $n=\frac{3^{2m+2}+1}{2}$ by choosing to subtract $1$.

The first player does not have a winning strategy for $n=\frac{3^{2m+2}+3}{2}$ since subtracting $1$ gives $\frac{3^{2m+2}+1}{2}$ and dividing by $3$ gives $\frac{3^{2m+1}+1}{2}$.

Doing similarly, we have that the first player has a winning strategy for $$\small n=\frac{3^{2m+2}-3}{2},\frac{3^{2m+2}+1}{2},\frac{3^{2m+2}+5}{2},\cdots,\frac{3^{2m+3}-5}{2},\frac{3^{2m+3}-3}{2},\frac{3^{2m+3}+1}{2},\frac{3^{2m+3}+5}{2},\cdots ,\frac{3^{2m+4}-5}{2}$$ and that the first player does not have a winning strategy for $$\small n=\frac{3^{2m+2}-1}{2},\frac{3^{2m+2}+3}{2},\frac{3^{2m+2}+7}{2},\cdots,\frac{3^{2m+3}-7}{2},\frac{3^{2m+3}-1}{2},\frac{3^{2m+3}+3}{2},\frac{3^{2m+3}+7}{2},\cdots ,\frac{3^{2m+4}-7}{2}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.