Two players $A$ and $B$ take stones one after the other from a heap with $n \ge 2$ stones. $A$ begins the game and takes at least one stone, but no more than $n -1$ stones. Thereafter, a player on turn takes at least one, but no more than the other player has taken before him. The player who takes the last stone wins. Who of the players has a winning strategy?
Problem
Source: 1995 Bulgaria NMO, Round 4, p3
Tags: combinatorics, game, winning strategy, game strategy
jelena_ivanchic
14.08.2021 07:38
When $n$ is not a perfect power of $2$ then $A$ wins. If $n$ is a perfect power of $2,$ then $B$ wins.
Solved with PC
Claim: If there are an odd number of stones then $A$ wins.
Because then $A$ takes $1$ stone and then $B$ is forced to take only $1$ stone. And then $A$ takes $1$ stone and so on. Since we have odd number of stones. $A$ will be the last person to take the stone, hence $A$ wins.
Claim: If $v_2(n)=1,~~n\ne 2,$ then $A$ wins.
$A$ starts with taking $2$ stones. Now, $B$ won't take $1$ stone, because then $A$ will get odd stones, and we know having odd stones means we can win. Hence $B$ will take $2$ stones. Since $v_2(n)=1,$ we know that $A$ will be the last person to take the stone.
Claim: If $v_2(n)=2,n\ne 4$ then $A$ wins
$A$ starts with taking $4$ stones. Now, $B$ knows that if $A$ gets a stones with $v_2(n)=0,1;$ $A$ wins. Hence $B$ will take $4$ stones and will try to maintain $v_2(n)=2.$ But then we know $n=4k,~k\ne 1 $ odd. Hence, $A$ will win.
So this gives induction vibes.
Claim: If $n$ not a perfect power of $2,$ $A$ wins. We prove it using induction.
Consider $v_2(n).$ For $v_2(n)=0,1,2$ $A$ wins. Suppose $A$ wins for $v_2(n)=0,1,\dots k.$
Now we will show that $A$ wins for $v_2(n)=k+1\implies n=2^{k+1}\cdot m,~~m>1$ is odd.
$A$ will subtract $2^{k+1}.$ $B$ knows that $A$ will win if $A$ has $v_2(n)<k+1.$ Hence $B$ will try to maintain $v_2(n)=k+1.$ So $B$ subtarcts $2^{k+1}.$ And then again $A$ subtracts $2^{k+1}$ and so on. But $A$ will win since $m>1$ is odd.
And we are done.
Claim: When $n$ is a perfect power of $2.$ Then $B$ wins.
If $n=2^k,$ $A$ has to take less than $2^{k-1}$ stones because if not in the next move $B$ can take everything.
But then whatever $A$ takes, $B$ will receive a "non-perfect power of $2$" number of stones. Which we know is a winnable situation. So $B$ wins.