Fragmented Nim

Flip the recurrence

This is not normal Nim. XOR is bait. In normal Nim, the current player chooses the pile. Here the opponent chooses the pile, so the quantifiers flip.

Call a position winning if the player to move can force a win. Then a non-empty position is winning iff:

$$\text{for every pile the opponent may choose, there exists a reduction of that pile to a losing position.}$$

And a position is losing iff the opponent can point at some pile where every legal reduction leaves a winning position.

The empty position is losing.

Why piles of size $1$ matter

If the opponent points at a pile of size $1$, the mover has no choice. They must remove it.

That means $1$-piles are forced moves. No strategy, no finesse, just bonk, pile gone.

Let $c$ be the number of piles equal to $1$.

There are three cases.

Case 1: No pile has size $1$

If $n=1$, Alice just removes the only pile and wins.

If $n>1$, no matter which pile Bob chooses, Alice can reduce it to exactly $1$. The new state has exactly one $1$-pile and at least one bigger pile. As we will prove below, that is losing for the next player.

So if $c=0$, the position is winning.

Case 2: All piles have size $1$

Then every move is forced: each turn removes exactly one pile.

So the winner is determined by parity:

• if $n$ is odd, Alice removes the last pile;
• if $n$ is even, Bob removes the last pile.

Thus, when $c=n$, Alice wins iff $n$ is odd.

Case 3: Some, but not all, piles have size $1$

Now there is at least one $1$-pile and at least one larger pile.

If $c$ is odd, the position is losing.

Why? The opponent chooses a $1$-pile. The mover is forced to delete it, so the number of $1$-piles becomes $c-1$, which is even. The position still has a larger pile, unless there were no larger piles, but this case explicitly has one. An even number of $1$-piles in a mixed position is winning for the next player.

So with odd $c$, the opponent has a pile choice that gives the mover no good option. That is exactly losing.

If $c$ is even, the position is winning. We must answer every possible pile choice:

• If the opponent chooses a $1$-pile, delete it. Now $c-1$ is odd, and the position is mixed, so it is losing for the next player.
• If the opponent chooses a larger pile and there is another larger pile left, reduce the chosen pile to $1$. Now the number of $1$-piles is $c+1$, odd, and the position is still mixed, so it is losing.
• If the opponent chooses the only larger pile, remove it completely. The remaining position consists of exactly $c$ piles of size $1$; since $c$ is even, that all-ones position is losing.

So when the position is mixed, Alice wins iff $c$ is even.

Final rule

Let $c$ be the number of piles equal to $1$.

• If $c=0$: Alice.
• Else if $c=n`: `Alice` iff$n$ is odd.
• Else: Alice iff $c$ is even.

That is it. The whole game is just the tyranny of size-$1$ piles. Brutal, but clean.

Complexity

We only count piles equal to $1$.

$$O(n)$$

per test case, with total $n \le 2\cdot 10^5$.