Alice and Bob Multiplication Game

Question

I am stucked in solving one problem.

The problem is below.

DESCRIPTION :

Alice and Bob are playing a game. First, they define $N$($N$ is natural number), and a number '$x$'(initiated to 1) is given. Alice will play first, and they play alternatively. In each turn, they play the work below.

[WORK]

substitute $x$ to $2x$ or $2x+1$.

if x>N, the player who played the work lose.

For example,

if $N=1$, Alice loses because $2>N, 3>N$.

if $N=2$, if Alice choose $2x$, then $x$ will be 2, So, Bob loses.

if $N=3$, if Alice choose $2x+1$, then $x$ will be 3, So, Bob loses.

if $N=4$, if Alice choose $2x+1$, then $x$ will be 3, So, Bob loses.

if $N=5$, if Alice choose $2x+1$, then $x$ will be 3, So, Bob loses.

Then, if N is given, how can we know who is winner?

---

I tried some approaches such as balanced binary tree, dynamic programming, etc.

I get an insight that if $N=2^m-1$, if $m$ is even, first player 'Alice' will win, and in other case, 'Bob' will win.

But I couldn't get more insights. Can anyone help me have a insight to this question?

Answer 1

Really amusing problem.

The answer can be written in a lot of ways, so the one I'll expose is probably not the best one:

Let $$x = 3N+5, \qquad z = \lfloor\log_4(x)\rfloor.$$

Then Bob wins if and only if $$5\cdot 4^{z-1}<x\le 2\cdot 4^{z}$$

---

Proof:

The idea to prove it is common to many games of the kind, that is to divide the number $1,2,\dots,N$ between "loser"(L) and "winner"(W) numbers. For example, if it is Alice's turn, and she gets the number $N$, then she loses, so $N$ is a loser number.

It's easy to see that the numbers from $N$ to $\lceil (N+1)/2\rceil$ are loser numbers, since if you multiply them by 2, you get a number $>N$. If you call $M=\lceil (N+1)/2\rceil$, then you find that the numbers from $M-1$ to $\lfloor M/2\rfloor$ are W, since there exists a move that bring them to a L number.

Given a specified $N$, and applying the reasoning above til you get to 1, you find that Alice wins if and only if 1 is a W number. In particular, it holds that

Given $N$, let me define the sequence $m_n$, where $m_0 = N+1$ and they are generated by the following recurrence: $$ m_{2n} = \lfloor m_{2n-1}/2\rfloor $$ $$ m_{2n+1} = \lceil m_{2n}/2\rceil $$ Then Alice wins if and only if the first $m_n$ to reach the value 1 has $n$ even.

So the whole problem is reduced to find all the $N$ for which we get 1 for the first time after an even number of iterations.

After a bit of meddling, you will see that the number 1 starts to be W when $N$ is in the form $4^{n} + \frac 53 (4^{n}-1) +1$ and starts to be L when $N$ is in the form $\frac 53 (4^{n}-1) +1$.

This means that Bob wins when $$ \frac 53 (4^{n}-1) < N \le 4^{n} + \frac 53 (4^{n}-1) $$ $$ 5\cdot 4^{n} < 3N + 5 \le 8\cdot 4^{n} = 2 \cdot 4^{n+1} $$ but we have that $$ 4^{n+1} < 5\cdot 4^{n} < 3N + 5 \le 8\cdot 4^{n} = 2 \cdot 4^{n+1} < 4^{n+2} $$ so $\lfloor\log_4(3N+5)\rfloor = n+1$ and this coincides with the formula above.

Answer 2

Let's first do some further investigation, so as to try and find a general pattern:

For $N=6$ through $N=9$, Alice will lose, since if she makes it $2$, Bob will make that $5$, and now Alice loses, and when Alice picks $3$, any move by Bob will also make Alice lose on the next turn

However, Bob loses for $N=10$, for Alice will pick $2$ for the first move. So whether Bob makes that $4$ or $5$, Alice will just double that again and after that Bob is guaranteed to lose. Notice that this also works for $N=11$ through $N=15$, and starting with $N=16$ Alice will pick $3$, so that after Bob's $6$ or $7$, Alice can just double that to win. And that works for up to $N=25$: Even when Bob picks $6$ after Alice's $3$, Alice will make that into $13$, and now Bob will lose.

But starting with $N=26$, Alice will start losing again: If she picks $2$, Bob can make that either $4$ or $5$, and whatever Alice does after that, and whatever Bob does after that, Alice will lose the turn after that. If Alice start with $3$, Bob will turn that into a $6$, and if Alice makes that into $13$, Bob can just double to $26$ and Alice will lose (she loses when picking $12$ regardless of what Bob does after that)

So: Alice loses for $N=6$ through $N=9$, then Bob loses for $N=10$ through $N=25$, then Alice for $N=26$ through ...

OK, so let's say that $2$, $6$, $10$, $26$, ... are 'transition numbers'. What defines those transition numbers?

Well, we see that the crucial 'chain of moves' leading up to the transition numbers seems to involve one person doubling and adding $1$ to increase the number as much as possible, while the other just doubles to prevent the number from growing that fast. Let's call these the 'agressive' and 'defensive' strategy. Also, let's call the winner of the game $W$, and the loser $L$. Which player employs which strategy?

Well, looking at the examples, we find that $W$ plays defensively, and $L$ plays agressively:

Alice started losing at $6$, which is $2(2\cdot 1+1)=2(2+1)$ (i.e. after Alice doubles and adds $1$, Bob just doubles) and at $26$, which is $2(2(2\cdot 1+1)+1)=2(2(2(2+1))+1)$ (i.e. Alice keeps doubling and adding $1$, while Bob just keeps doubling).

On the other hand, Bob started losing at $2=2 +0$ (Alice just doubled), and at $10=2(2(2 \cdot 1)+1)=2(2(2+0)+1)$ (Alice doubles, while Bob doubles and adds $1$)

Indeed, it makes intuitive sense that in general, $W$ plays defensively: For any transition number $N$ , $W$ aims to create exactly that transition number $N$ on his or her last turn, and pass that to $L$, who will therefore indeed lose on the next turn. Of course, $L$ is trying to foil that plan by trying to give $W$ a number greater than $\frac{N}{2}$, and $L$ will therefore have the goal of increasing the number as much as possible, and thus play agressively. But by playing 'perfect defense', $W$ will prevent the number from growing too fast, and indeed in the last move will go from $\frac{N}{2}$ to $N$ and hand defeat to $L$.

One worry: what if a player realizes that playing agressively is not going to work given perfect defense, and decides to play defensively as well? That is, maybe a player can slow the ever-growing number down enough so that it in fact drops to a number where the roles get reversed? Well, we need not be concerned, for this is impossible: Indeed, it is easy to see that after $k$ moves, it will always be true for the growing number $x$ that:

$ 2^k \le x < 2^{k+1}$

So, this strategy should always work ... and continuing the pattern, we thus find that Bob will start losing again at $2(2(2(2(2+0)+1))+1)=42$, and after that Alice will start losing again on $2(2(2(2(2(2+1))+1))+1)=106$, etc.

Or, in a closed form, Alice starts losing whenever for some whole number $k$, $N$ reaches the value of:

$$N=2(2^{2k+1}+\sum_{i=0}^k 2^{2i}) $$

While Bob starts losing whenever for some whole number $k$, $N$ reaches the value of:

$$N=\sum_{i=1}^k 2^{2i+1}$$

Or, in terms of intervals:

Alice loses for any $N$ that lies in the interval:

$$[2(2^{2k+1}+\sum_{i=0}^k 2^{2i}), \sum_{i=1}^k 2^{2i+1} -1]$$

for some $k$, while Bob loses for any value of $N$ that lies in the interval:

$$[\sum_{i=1}^k 2^{2i+1}, 2(2^{2k+1}+\sum_{i=0}^k 2^{2i})-1]$$

for some $k$