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