1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 2015 is a nice number that it has only one zero in its binary representation. Removing a power of 2 means removing the 1's or that zero. There are two cases. These ones are removed one by one, or someone removes the power associated with the zero in which case the left over number is also nice. $\endgroup$ – Shailesh Sep 8 '15 at 3:24
  • $\begingroup$ Note that the players can take turns removing one marble each, many times in a row. In other words, other 0s appear in the binary expansion, but that doesn't prevent that "0 from being removed" again. $\endgroup$ – Greg Martin Sep 8 '15 at 3:59
  • $\begingroup$ A pedantic answer to the question as worded would be "Yes, there is a winning strategy for one of the players". Proof: the game must be finite (taking at most 2015 turns) and cannot end in a draw. $\endgroup$ – Peter Taylor Sep 18 '15 at 21:04
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

I think this is essentially the same as what @PSPACE-Hard said, but here is my take on the winning strategy;

A winning strategy revolves all around the number $3$. This is because;

  1. Every number is either a multiple of $3$, or is $1$ ($2^0$) or $2$ ($2^1$) below a multiple of $3$.
  2. Also, if either player is left with the number $3$, they are guaranteed to lose, because whether they choose $1$ or $2$, the other player is left with $1$ or $2$, and it is possible to win from either of these two numbers.

As a number that is a power of $2$ is just like any other number, it fits with point (1), so $2^n+1$ or $2^n+2$ are multiples of $3$. Obviously $2^n$ cannot be a power of $3$, given its prime factors will be just $2$.

As long as the player does this right up until $2^1+1$, they will leave the other player with $3$, which is a guaranteed victory given point (2).

Therefore, the strategy to win is to simply leave the other player with a number that fits $3n$, where $n$ is a whole number. The thing that makes this a guaranteed win, is that the other player will not be able to reply with a number that is divisible by $3$, because taking away a multiple of of $2$ (or the number $1$) from a multiple of $3$, you will be left with a number that isn't a multiple of $3$.

This means that the first player is guaranteed to win, as long as they;

  1. Play the number $2$ as their first number, leaving $2013$, which is divisible by $3$, and;
  2. Play tactically to ensure that after each of the other player's move, they play $1$ or $2$ to leave a number divisible by $3$.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.