Nim Game Is XOR Game — Deon Nicholas

Problem

Given an array $A$ of $n$ piles, two players take turns making a move; the last player to make a move wins.

A valid move consists of removing $b_1$ from $A[1]$ , $b_2$ from $A[2]$ , ..., $b_n$ from $A[n]$ , where $b_i \geq 0$ for all $i$ , at least one $b_i > 0$ , and

b_1 \oplus b_2 \oplus \cdots \oplus b_n = 0.

Count the number of winning first moves for the first player.

Initial Observations

Write it in binary.
Nim-sum / Sprague-Grundy theorem (find the xor of the numbers).
Construction.
This is a "two-player impartial game," so every game has a nim-sum — can I compute it?
How do I characterize the losing states easily?
Counting?
Make the xor 0?
[Write It Out], [Exploit the Constraints].
Look for a pattern.

IdeaCharacterize the Sprague-Grundy values of the gameNo Solution

Draw from Experience

This is a two-player impartial game: both players have the same set of moves available at any time, they alternate, and the last player to move wins. By well-known results, any such game is equivalent to a single-pile Nim of some size $g$ — the nim-sum or Sprague-Grundy value of the game. A nim-sum of $0$ is a losing state for the player to move; nonzero is winning. You compute it as the minimum excluded value (MEX) of the nim-sums of all states reachable in one move.

I won't go deeper into the theory here, since (spoiler for this Idea) it didn't end up leading to the solution — see the Sprague–Grundy theorem if you want the full story. Had this direction worked out, it would have earned its own Aside with a proof.

Key Question

What is the nim-sum of this game? Can we characterize and compute a pattern for how the Sprague-Grundy theorem applies here?

Examine Examples

I tried small examples. $[0\ 0\ 0]$ is obviously a losing game with nim-sum $0$ . Any single-pile game is also losing with nim-sum $0$ : there is no way to remove $b > 0$ from one pile while keeping the xor of the removals $0$ — it contradicts the move constraints. Another family: if every pile has size $1$ (single bits), with $n$ piles, the nim-sum is $\lfloor n/2 \rfloor$ — you can remove any even number of piles ( $2, 4, 6, \ldots$ ), and induction on the MEX confirms it. And $[1\ 2\ 3]$ is interesting: the xor of all the piles is $0$ , so you can take everything and win in one move. What makes that so special?

Key Observation

Any game with exactly one non-zero pile (or none) is a losing game for the player to move — there is no valid move at all.

At this point most of my ideas were not leading anywhere. The observations were interesting, but I kept getting stuck. Here are some others that may or may not lead anywhere:

Observation.

The parity of the number of odd piles never changes: every valid move removes values xor-ing to $0$ , so an even number of the $b_i$ are odd. (Not sure if this is useful.)

Key Question

Can I mess around with the highest bit? Proofs about nim-sums often peel off the most significant bit of the nim-sum and then make any xor possible in the remaining bits. (Again, not sure if this is useful.)

Generate and Test

I kept getting stuck — making observations about patterns of nim-sums, but nothing stuck. So I tried to guess and check: zooming out, what would a reasonable strategy be if I were playing this game with friends? What could the MEX be, on intuition, and can I prove it? Maybe count the pairs in each bit position and do something special with that? Is it just the number of odd pairs? Admittedly, none of it led anywhere.

I spent way too long in this idea maze of ways to characterize the MEX. It burned most of my time and got me nowhere. The only genuinely useful observation (in hindsight) was that any zero-pile or single-pile game is a losing game. It's not that insightful — it's obvious — but it is a good starting point.

IdeaCan I always kill most of the piles in one move?AC

What possible valid moves can I make? I was stuck, so I decided to get unstuck by looking at more examples.

Examine Examples

I turned back to the sample test cases, just to make forward progress and get my brain out of a rut. $[1\ 4\ 5\ 2\ 6]$ was the case I looked at. I sorted the items (we can always assume the piles are sorted without loss of generality): $[1\ 2\ 4\ 5\ 6]$ . I don't know why, but once the piles were sorted, this gave me an idea.

Key Question

In $[1\ 2\ 4\ 5\ 6]$ , can we kill $1, 2, 4,$ and $5$ entirely, and leave the $6$ (or something in the pile that used to be $6$ )?

Key Observation

We can kill the piles $1, 2, 4, 5$ and take $2$ away from the $6$ -pile, leaving exactly one pile of size $4$ . Why? The xor of $1, 2, 4, 5$ is exactly $2$ , so to make the xor of everything we remove equal $0$ , we just take $2$ from the $6$ -pile. And we already know a single-pile game is a losing state — so this is a winning move.

Key Question

Can we always kill all but one pile in one move? In other words, can we always make a move that forces the other player into a losing game (a game with $0$ or $1$ piles left)?

Write It Out

Say the piles are $[a_1, \ldots, a_n]$ , and try to delete the first $n-1$ entirely: $b_1 = a_1, \ldots, b_{n-1} = a_{n-1}$ . Since the xor of all removals must be $0$ , associativity forces $b_n = a_1 \oplus \cdots \oplus a_{n-1}$ . That's a valid move if and only if $b_n \leq a_n$ . When does that hold? It helps to line the numbers up in binary:

The reason $1 \oplus 2 \oplus 4 \oplus 5 = 2$ is $\leq 6$ : the most significant bit of the xor comes out $0$ , while $6 = 110$ has that bit on — so the xor is certainly smaller. Does it work with other survivors? Keeping the $5$ -pile: $1 \oplus 2 \oplus 4 \oplus 6 = 1 \leq 5$ — yes. But keeping the $1$ -pile: $2 \oplus 4 \oplus 5 \oplus 6 = 5 > 1$ — there is no valid amount to remove. So it works for some survivors and not others.

After working this out and looking at enough examples, I came to the following key observation.

Key Observation

If there is more than one non-zero pile, it is always possible to kill some $n-1$ of the piles entirely and take an amount from the last pile that makes the xor of all removals $0$ — leaving exactly $1$ (or $0$ ) non-zero piles.

Proof.

Start by xor-ing all the numbers together: $X = a_1 \oplus \cdots \oplus a_n$ .

If $X = 0$ , we're done immediately: take every item from every pile. The removals xor to $0$ , and the next player faces no piles and hence no moves. We win.

Otherwise $X \neq 0$ , so some bit of $X$ is $1$ ; let $j$ be the most significant such bit. Since bit $j$ of the xor is $1$ , at least one of the $a_i$ must have bit $j$ set — pick any such index $i^*$ . We claim the xor of all the numbers except $a_{i^*}$ — call it $Y = X \oplus a_{i^*}$ — satisfies $Y \leq a_{i^*}$ (in fact $Y < a_{i^*}$ ):

For every bit above $j$ : that bit of $X$ is $0$ , so $a_{i^*}$ and $Y$ agree on it (they must cancel).
On bit $j$ itself: $X$ has a $1$ , so $a_{i^*}$ and $Y$ differ there — and we chose $a_{i^*}$ to have bit $j$ set, so $Y$ has it clear.

So $a_{i^*}$ and $Y$ match on all higher bits and $a_{i^*}$ wins on bit $j$ : $Y < a_{i^*}$ . Remove all of every other pile and remove $Y$ from pile $i^*$ : the removals xor to $Y \oplus Y = 0$ , the move is valid, and pile $i^*$ survives with $a_{i^*} - Y > 0$ items — a single non-zero pile.

∎

Eureka! This was a really cool observation, and it makes the problem feel much more tractable. First, two quick asides:

Draw from Experience

The proof of the MEX / Sprague-Grundy values in classical Nim leans heavily on the binary representations of the piles and the most-significant-bit of the nim-sum. So this proof wasn't a leap — it rhymed with how nim arguments usually go. For me it was a fairly natural proof once I was pointed at the right question (if you're wondering how I could have gotten here).

Generate and Test

Technically, "we can always kill all but one pile in one move" was just a conjecture — tried out on examples first, proven after. That's Generate and Test. It was a reasonable conjecture to make, and it led to the solution.

Key Observation

Since it is always possible to move the next player into a losing state, any move that doesn't leaves them in a winning state — from which they can do the same to you. So the winning moves are exactly the moves that leave $1$ or $0$ non-zero piles.

We're now pretty close to a solution: try every move that kills all but one pile, check whether it's valid, and count (plus possibly one more for the move that kills every pile).

Algorithm

Given n and the piles A[1..n]
 
choices = 0                                        # the answer
X = A[1] XOR A[2] XOR ... XOR A[n]                 # xor of all piles, precomputed
 
# for each i: can we kill everything except pile i?
for i in 1..n:                                     # (only meaningful when n >= 2)
    Y = X XOR A[i]                                 # xor of all piles except A[i]
    if Y < A[i]:                                   # remove Y from pile i, all of the rest
        choices += 1
 
if X == 0: choices += 1                            # the take-everything move

Each "kill all but pile $i$ " move is forced once $i$ is chosen (the amount removed from pile $i$ must be exactly $Y$ ), so no move is counted twice. With the xor of all piles precomputed, the whole thing is $O(n)$ .

And we're done. Accepted.

Review

The winning moves are exactly the moves that leave at most one non-zero pile, and there are at most $n + 1$ candidates — one per surviving pile, plus take-everything — each checkable with one xor. The path:

A game with at most one non-zero pile is losing — with one pile, any removal has nonzero xor, so there is no valid move at all. [1]
With more than one non-zero pile, you can always kill all but one pile in a single move. The proof is by construction: xor everything to get $X$ ; if $X = 0$ take everything; otherwise pick any pile $a_{i^*}$ with the top bit of $X$ set — the xor of the others is then strictly smaller than $a_{i^*}$ , so removing it from pile $i^*$ (and all of everything else) is a valid move leaving one pile. [3]
Not doing so hands the win away: any other move leaves the opponent two or more piles, from which they can do the same to you. [4]
So the winning moves are exactly the kill-all-but-one moves (plus take-everything when the total xor is $0$ ), and each candidate survivor $i$ is checked by one comparison: $X \oplus A[i] < A[i]$ .
Count them in $O(n)$ by precomputing the xor of all piles.
Done...? (Don't forget to take it modulo $998244353$ .)

References

Problem-solving techniques used:

Examine Examples

Always a good place to start — and at the times I got stuck, it seemed to jog my brain loose and get me unstuck.

Draw from Experience

Useful in the final proof, but it admittedly sent me astray for the first part of the problem: I kept trying to find a complicated characterization via the Sprague-Grundy theorem, which was fine background but not how I should have spent my time.

Generate and Test

Trying "what I think the right answer should be" conjectures or strategies is often useful in construction-style and game-style problems — thinking about what I would actually do if playing this game intuitively. It didn't help all the way, but it moved us along.

Write It Out

A lot of this problem (and the final proof) relied on the binary representations. Keeping it in my head was not helping; writing out the example in binary let me visually see and work the patterns.

Learning points:

This problem took me way too long. A Div. 1 Codeforces A should take 5–15 minutes tops; it took me about an hour in the end (during practice, not a full competition).
I spent too much time in my head, trying to prove and work a characterization that wasn't the right route.
Instead, looking at examples and asking "what are the valid possible $b$ ?" and "what are some examples of obvious winning moves?" would have short-circuited all of it.
That last question is probably the biggest one: "what are some examples of obvious winning moves?" — a Generate-and-Test-style prompt — would very likely have led me to the kill-all-but-one move, and the correct solution, much faster.
Alas, we persist! Onto the next one!

Topics:

Game theory / Nim games / Sprague-Grundy theorem
Greedy
Counting / combinatorics
Binary representation / XOR
Constructive algorithms / proof by construction