1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Newb
    Commented Nov 27, 2014 at 19:56

1 Answer 1

1
$\begingroup$

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.

You can continue backwards to figure out which numbers you have a winning strategy for (i.e. how can you force your opponents move to be in the desired interval)? An important hint on seeing the general strategy is this:

No matter what your opponent does, you can always ensure that the number increases by a factor of $6$ between their turns.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – MS93
    Commented Dec 2, 2014 at 21:13
  • $\begingroup$ Yes, that's the strategy I was thinking of. $\endgroup$ Commented Dec 2, 2014 at 22:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .