0
$\begingroup$

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...

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

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.

$\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.