Problem 923

Solution. If the initial value of $N$ is even, let's see that A wins: by either subtracting 1 or dividing by 2 (in the case $N=4 k+2, \frac{N}{2}=2 k+1$ odd), A will always leave B with an odd number, forcing B to subtract 1 as division by 2 is not possible, which means that when A plays again, they will encounter an even number, smaller than the previous one. Thus, A will eventually encounter a 2, and win.

It is important to note that when A has two valid options to leave B with an odd number, A will always prefer to divide by 2, to get closer to the goal more quickly.

Next, we will use the following result:

Let $y$ be an even number that A encounters on their turn. Then, two turns before, A was with a number greater than or equal to $2 y+4$.

Indeed, we will distinguish two cases: (1) Case $y=4 k+2$. It comes from a forced move of B from $4 k+3$. Before that, A could have been in $8 k+6$, or $4 k+4$ (this is viable, since from $4 k+4$ A cannot divide because $2 k+2$ is even). That is, B was in $8 k+7$ or $4 k+5$ before. If B was in $8 k+7$, A could have been in $16 k+14$ or $8 k+8$, while if B was in $4 k+5$, A could only have been in $8 k+10$, not in $4 k+6$, because in that case A would have preferred to divide instead of subtracting. In summary, if $y=4 k+2$, two turns before, A could have been in $16 k+14, 8 k+10$ or $8 k+8$, with the smallest option being just $2 y+4$.

(2) Case $y=4 k$. Reasoning similarly, it is deduced that two turns before, A was in $8 k+4(2 y+4)$ or

The solution to the problem will be obtained by repeatedly applying the above result.

We define the sequence $a_{0}=2, a_{n+1}=2 a_{n}+4$, whose explicit formula is

$$a_{n}=6 \cdot 2^{n}-4$$

By repeatedly applying the result, we see that for all $n$, any $N$ from which one can reach 2 in $2 n$ turns must satisfy $N \geq a_{n}$. That is, counting that A goes from 2 to 1 in one turn, we have proved that for all $n$, the numbers $N$ that require at least $2 n+1$ moves from A satisfy $N \geq a_{n}$.

Since for $n=1007$ we have $2 n+1=2015$, it follows that $N$ is greater than or equal to the term $a_{1007}$ of the considered sequence, that is, the number $6 \cdot 2^{1007}-4$. It remains to prove that equality can be achieved. For this, it is enough to see that for all $n \geq 1$, if A encounters $a_{n}$, after two turns they will be in $a_{n-1}$. Indeed,

$$\underbrace{6 \cdot 2^{n}-4}_{a_{n}} \xrightarrow{A} 6 \cdot 2^{n}-5 \xrightarrow{B} 6 \cdot 2^{n}-6 \xrightarrow{A} 3 \cdot 2^{n}-3 \xrightarrow{B} 3 \cdot 2^{n}-4=\underbrace{6 \cdot 2^{n-1}-4}_{a_{n-1}}$$