Alice and Bob are playing a game with n piles of marbles. The pile i has ni marbles. Here is the rule. Alice and Bob will take turns (Alice being the first); each time, a player needs to first pick a pile and then take any number of remaining marbles in that pile. Note this player must take at least one marble. Whoever takes the last marble wins the game. As an example, consider there are three piles A, B and C with 3, 4 and 5 marbles respectively. Alice can win as follows. Alice takes 2 from A. Suppose Bob takes 1 from A. Then Alice takes 1 from C. Suppose Bob takes 2 from B. Then Alice takes 2 from C. Bob takes 2 from B. Alice then wins by taking 2 from C. Try to play with this example to convince yourself that Bob cannot prevent Alice from winning the game in this example.

Suppose Alice and Bob are both smart and will play using the optimal strategy. Now tell me exactly when Alice can win the game. Justify your answer. 2

Hint: this seems not easy but it will become easier if you treat ni as binary numbers and then perform a bitwise XOR on these numbers. Alice will win if and only if the resulting number is...

  • 4
    $\begingroup$ Are you just describing the Game of Nim? $\endgroup$
    – lulu
    Feb 25, 2018 at 18:55
  • $\begingroup$ @lulu Same as but here are many piles. $\endgroup$ Feb 25, 2018 at 19:01
  • $\begingroup$ @lulu Thanks I have solve this problem using Game of Nim theory. $\endgroup$ Feb 27, 2018 at 18:39

1 Answer 1


Community wiki answer so the question can be closed as answered:

As noted in the comments, this is the game of Nim, which has been thoroughly studied.


You must log in to answer this question.

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