Anna and Bob are playing the following game: The number $2$ is initially written on the blackboard. With Anna playing first, they alternately double the number currently written on the blackboard or square it. The person who first writes on the blackboard a number greater than $2023^{10}$ is the winner. Determine which player has a winning strategy.
Problem
Source: JBMO Shortlist 2023, C4
Tags: game, JBMO, JBMO Shortlist, combinatorics
Assassino9931
02.07.2024 00:27
Fun fact: the corresponding game when one adds $1$ or multiplies by $2$ was originally supposed to be JBMO 2023 P2 (and 2023 P3 to be the inequality which ended up as P2), but was found in StackExchange 5 min after the leaders voted. On the other hand, many were against putting the original version due to the necessity to estimate $k$ such that $2^k < 2023^{10}$ (and the suggested solution was with Bernoulli's inequality, which is surely not suitable for juniors). Here is a decent way to take care of everything in this problem.
Let $k$ be the smallest integer such that $2^k > 2023^{10}$. Then the game is equivalent to the following: initially is written $1$ and on each move the player adds $1$ or multiples by $2$; winner is who firstly writes a number greater than or equal to $k$.
In fact, $k=110$. Indeed, $2023^{10} < 2048^{10} = 2^{110}$, while $2023^{10} > 2^{109}$ is equivalent to $\displaystyle \left(\frac{2023}{2048}\right)^{10} > \frac{1}{2}$, which holds since $\displaystyle \frac{2023}{2048} > \frac{19}{20}$ and $\displaystyle \left(\frac{19}{20}\right)^{10} > \frac{360^5}{400^5} = \frac{9^5}{10^5} = \frac{81 \cdot 729}{100000} > \frac{80 \cdot 700}{100000} = \frac{14}{25} > \frac{1}{2}$.
Now we compute from top to bottom the winning and losing positions. (Here we call a position winning if the player whose turn it is now, with this number on the board, has a winning strategy.) The positions $55$, $56$, $\ldots$, $109$ are winning (one doubling is enough), so $28$, $30$, $\ldots$, $54$ are losing and $27$, $29$, $31$, $\ldots$, $53$ are winning, hence $14$, $15$, $\ldots$, $26$ are winning (with a doubling we reach the abovementioned losing positions) and so $3$, $5$, $\ldots$, $13$ are losing and $2$, $4$, $\ldots$, $12$ are winning, therefore $1$ is losing. Since in this game the initial number is $1$, the result of the first move of $A$ is $2$ and therefore $B$ is the winning player.
Btw, (I think) this problem was proposed by Cyprus.