# Multiplying game strategy

Given the following game, what is the strategy to win?

Given $X,N\in \mathbb{N}$ such that $N>X$ and $N>1000$, two players play against each other. Each player multiply $X$ by $2$ or by $3$ by his own choice. The player who reach $N$ or above- wins.

I realized that if it's my turn and my opponent reached $\lceil \frac{N}{3} \rceil$ I win, so I tried to see how can I "make" him get there recursively, but nothing solid came to my mind so I'm pretty stuck.

Any help would be appreciated.

• Hint: make a tree of the possible outcomes of the game. Your branching factor on every step is only two, so it's easy to visualize.
– Newb
Commented Nov 27, 2014 at 19:56

The best method of attack for this is probably to work backwards. So, you see that if the number given to you is above $\frac{N} 3$, you win. What numbers, less than this, can you give to your opponent such that they have to give you a number at least $\frac{N}3$? Well, since they have to multiply by at least two, if you give them some number between $\frac{N}6$ and $\frac{N}3$, you will win on your next turn. For what numbers is it possible for you to give your opponent such a number? Well, anything between $\frac{N}{18}$ and $\frac{N}{6}$ will suffice, since you can choose which move to do.
No matter what your opponent does, you can always ensure that the number increases by a factor of $6$ between their turns.
• I found out that when $\frac{N}{6^k} \leq x < \frac{N}{6^{k-1}\cdot3}$ I let my opponent be the first player. When $\frac{N}{6^{k}\cdot2} \leq x < \frac{N}{6^{k}}$ I multiply x by 2 and when $\frac{N}{6^{k}\cdot3} \leq x < \frac{N}{6^{k}\cdot2}$ I multiply x by 3. Was that your intention?