Is there any winning strategy? 2015 and Game with marbles!!!

Question

Two players, Alex and Brad, take turns removing marbles from a jar which initially contains $2015$ marbles. Assume that on each turn the number of marbles withdrawn is a power of two. If Alex has the first turn and the player who takes the last marble wins, is there a winning strategy for either of the players?

---

I try to solve it like the follow:

First) I assume that both player know the amount of marbles they took each other

Second) The problem say they pick power of 2 then the possible picks are $[1 , 2 , 4, 8, 16 ,32,64 128 , 256 , 512 , 1024]$ there are only $2015$ marbles.

Third) the game has 2 players.

Continue:

a) The only odd pick is $1$ due to $2^0$ is $1$. The rest are odds

If player A pick odd (1) B must pick an even number and A continue pick even and also B until complete the $2015$.

And

If player A pick even (2, 4, etc) B must pick an odd (1) number and A continue pick even and also B until complete the $2015$.

I cannot see how can I use 2015 to set a winning rule, I also try use binary but I couldn’t do any advance.

Please, let me know what I am doing wrong and how I can continue. Thanks, Greg Martin and Shailesh for your help.

Note: I try to use brute fore (excel ;-) ) but I see that multiple of 3 are the wining but I can’t not put my assumption in words with the $2015$ number.

Thanks again.

Answer 1

We first prove the following facts:

---

Fact 1. If $x$ is multiple of $3$ and $y < x$ is power of $2$, then $x - y$ can not be multiple of $3$.

proof sketch: Observe that $y$, which is power of $2$, can not be multiple of $3$.

---

Fact 2. If $x$ is not multiple of $3$, it's possible to find a $y \leq x$ such that $y$ is power of $2$ and $x - y$ is multiple of $3$.

proof sketch: Let $y = x\bmod 3$.

---

We next introduce two concepts. Denote the # of marbles remaining in the beginning of a turn as $x$. If $x$ is multiple of $3$, that turn is called a L-turn (lose), otherwise it's a W-turn (win). Easy to observe that ONLY in a W-turn, a player can win the game. (If $x$ is multiple of $3$, it can not be power of $2$.) According to the two facts above, we know that

• If a player's turn is a L-turn, the next player's turn is always a W-turn.
• If a player's turn is a W-turn, the player can smartly remove some marbles such that the next player's turn is a L-turn, thus the next player can NOT win.

Consequently,

• If the # of marbles in the beginning of the game, denoted as $n$, is multiple of $3$, the first player's first turn is a L-turn. No matter how he removes the marbles in the turn, the next player's turn will be a W-turn and the second player can carefully remove some marbles such that the first player's second turn is a L-turn again. Continue this process till end and it's easy to see only the second player can reach W-turn and he will be the winner.
• If $n$ is not multiple of $3$. The first player will win finally by a similar process as above.

---

Summary: Since $n = 2015$ is not multiple of $3$, the first player will win the game if he plays optimally.

Answer 2

For problems like this, the general strategy is to tabulate several small cases until you detect a pattern of which initial numbers of marbles are winning positions (wins for the first player) and which are losing positions, then try to prove the pattern you detected. In this case, brute-force exploration of the first several cases reveals that the multiples of $3$ are all losing positions (wins for the second player), while non-multiples of $3$ are all winning positions. Can you prove this to be true?