This is originally a question from https://codeforces.com/contest/1383/problem/B, but this is more of a math problem than an algorithmic one, so I decided to post here.
There is a game where two players take turns to take an element from an array $A$ containing non-negative integers. Say Alice is the one who go first and Bob is the second. Both Alice and Bob has an initial score of $0$. For each turn, a player can pick an element $v$ from $A$ and remove it), and his score becomes $\text{his original score} \oplus v$, where $\oplus$ denotes $\text{xor}$. When $A$ becomes empty, the game ends, and the one with larger sum wins. If both players play optimally, who will be the one winning, or the game will end in a draw.
Solution can be found here: https://codeforces.com/blog/entry/80562
Basically the strategy is simple. For example $A = \{110_2, 100_2, 010_2, 010_2\} $. Consider the most significant bit, If the number of ones is odd, then one of them will win immediately (depending on the parity of the number of zeros and number of ones $mod$ 4).
However, the solution mentions that when the number of ones of the most significant bit is even, we move on to the next bit and do the same.
I do not understand why we can do the same on the next bit because the choice of $1^{st}$ most significant bit somehow limit the choice of the $2^{nd}$ most significant bit. Using the example mentioned above, when we are considering the $2^{nd}$ bit, we know that $110_2$ and $100_2$ must go to different players, otherwise it will not end in a tie in the $1^{st}$ bit. Furthermore, the choice of $1^{st}$ and $2^{nd}$ bit will limit the choice of $3^{rd}$ bit.
However, the solution in the editorial seems to imply these won't affect the result but there is no explanation. Can anyone kindly explain why this is the case? Thanks in advance.
With an even number of $1^{st}$ significant bits, the winner cannot be decided on the $1^{st}$ significant bit no matter how Alice and Bob play.
In order for it to affect a game’s outcome. One side must have a move history containing an odd number of $1^{st}$ significant bits. But the total number is even, so the other player will also have made an odd number of such moves. Both players’ scores have a $1$ in front, and the winner is decided based on the remainder.