Two player game with marbles using optimal strategies

Question

Consider the two-player game that consists of a single bowl of $n$ marbles. The players alternate turns. During each turn, a player can remove $2^k$ marbles, for any $k \ge 0$ of his or her choice. The winner is the person who removes the last marble. Determine all $n \ge 0$ for which the first player wins, supposing both players use optimal strategies.

Here is what I have done so far: n=1 is a winner. n=5 is a winner.

This is a problem I am doing for fun, it would not harm me to show me the answer and work

Answer 1

You can try and think about this problem inductively. Note that every single position is either a winning position or a losing position assuming both players play the optimal strategy. Furthermore, a position is winning if and only if you can put your opponent in a losing position by taking out $2^k$ marbles for some $k \geq 0$. Using this idea:

1 is winning because player one can simply take all the marbles

2 is winning for the same reason

3 is losing because player one can only put player two in a winning position

4 is winning

5 is winning because player one can take 2 marbles and put player two in a losing position (3)

Now we can continue this process for each $n$: $n$ is winning if and only if $n$ is a power of 2 or $n$ is $2^k$ more than one of the previous losing positions for some $k \geq 0$.

(Though this idea is assuming every position is either winning or losing, which probably requires more thought.)

Answer 2

You’ve discovered that the multiples of $3$ appear to be the losing positions, the other non-negative integers being the winning positions. There is a standard way to prove this kind of result (when it’s true!).

Let $W$ be the set of winning positions, and let $L$ be the set of losing positions. As you may have realized in analyzing the smaller positions, a winning position is one from which you can put your opponent in a losing position, and a losing position is one from which every legal move leaves your opponent in a winning position. In the case of this game that means:

• if $n\in W$, then there is some $k\ge 0$ such that $n-2^k\in L$, and
• if $n\in L$, then for every $k\ge 0$ either $2^k>n$, or $n-2^k\in W$.

In fact, the cases

$$n-2^k\in L\text{ for some }k\ge 0$$

and

$$\text{for each }k\ge 0\text{ either }2^k>n,\text{ or }n-2^k\in W$$

are mutually exclusive, so we can go further:

• $n\in W$ if and only if there is some $k\ge 0$ such that $n-2^k\in L$, and
• $n\in L$ if and only if for every $k\ge 0$ either $2^k>n$, or $n-2^k\in W$.

You’ve conjectured that $L=\{3n:n\ge 0\}$, and $W=\Bbb N\setminus L$. You can prove this by showing that two bulleted statements above are true for this choice of $W$ and $L$.