2
$\begingroup$

Alice and Bob are playing a game. The rules of this game are as follows:

  • Initially, there are $N$ piles of stones, numbered $1$ through $N$. The i-th pile contains $A[i]$ stones.

  • The players take alternate turns. If the bitwise XOR of all piles equals 0 before a player's turn, then that player wins the game.

  • In his/her turn, a player must choose one of the remaining piles and remove it. (Note that if there are no piles, that player already won.)

We need to decide which player wins, given that both play optimally and Alice starts the game.

Example : Let $N=4$ and stones in piles are : $[1,2,4,8]$ in this Alice will win. But if $N=3$ and stones in piles are : $[2,3,3]$ then Bob is going to win.

$\endgroup$
3

1 Answer 1

1
$\begingroup$

Alice wins if and only if the number of piles is even.

In any given situation, there is only one way to lose immediately, namely by removing a pile corresponding to the current XOR sum. Thus, the only situation in which a player is forced to lose immediately is when there is only one size of piles left. If there had been an even number of them, the player would have won at the beginning of the turn, so it must be an odd number. Since one can only be forced to lose when encountering an odd number of piles and it's always the same player who encounters an odd number of piles, the claim follows.

$\endgroup$

You must log in to answer this question.

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