RNIM - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: theoneyouwant
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

Alice and Bob play a game of nim, with N piles of stones - the i-th having A_i.
However, on their turn, a player can choose only the pile - the number of stones removed will be random, between 1 and the pile’s size.

Find the probability that Alice wins, under optimal play.

EXPLANATION:

It’s seemingly quite hard to even begin to analyze what “optimal play” could be here, at a glance.

Let’s try to work on a simple version of the problem first: what if we only have a single pile?

Solution for one pile

Suppose there’s one pile with K stones.

If K = 0 then Alice loses immediately, and if K = 1 then Alice wins immediately on her move since one stone must be removed.

That leaves K \ge 2.
Let’s define p(K) to be the probability that the current player wins when the pile has K stones.
Then, after Alice’s move there will be strictly less than K stones, and each state occurs with equal probability.
So, we have

p(K) = \frac{1}{K} \cdot \left((1 - p(0)) + (1 - p(1)) + \ldots + (1 - p(K))\right)

because if there are x stones remaining after Alice’s move, Bob has a p(x) chance of winning; and so Alice’s chance is (1 - p(x)).

We know p(0) = 0 and p(1) = 1.
Quite nicely, it turns out that for all K \ge 2, we have p(K) = \frac{1}{2}.

This can be proved via induction: it’s true for K = 2, because we have p(2) = \frac{1}{2} \cdot \left(1 + 0\right) = \frac{1}{2}, and for larger K we have

p(K) = \frac{1}{K} \cdot \left(1 + 0 + (K-2)\cdot\frac{1}{2}\right) = \frac{1}{K}\cdot\frac{K}{2} = \frac{1}{2}

where the (K-2)\cdot\frac{1}{2} is obtained from the fact that all of p(2), p(3), \ldots, p(K-1) are \frac{1}{2} via the inductive hypothesis.

With the case of one pile having a very simple solution, we can now attempt to extend the idea to multiple piles.

Note that for one pile, our cases were zero stones, one stone, or more than one stone.
In particular, for \leq 1 stone the process was deterministic in that only one choice was possible at all, so the winner could always be uniquely determined.

Now, if every pile has only one stone, it’s easy to see that again the winner is uniquely determined: each turn, a player must choose a pile and remove the only stone from it, so if the number of piles is odd, Alice wins; and if it’s even, Bob wins.

That leaves us with the case where at least one pile has \ge 2 stones.
This turns out to be very similar to the one-pile case: the probability is always \frac{1}{2}.

Proof

We use induction, this time on the total number of stones across all piles, i.e. (A_1 + A_2 + \ldots + A_N).

Our claim is: if all A_i are \le 1, the winner is uniquely determined so the probability is either 0 or 1, and in all other cases the probability is \frac{1}{2}.

So, let K = (A_1 + A_2 + \ldots + A_N).
If K \le 1 the hypothesis is trivially true, so let’s look at K \gt 1 now (while assuming the hypothesis true for all integers smaller than K).

If all A_i are \le 1 the winner is uniquely determined: we’ve already seen why.
So, suppose some pile has \ge 2 stones.

Alice now has two options: either choose a pile with \geq 2 stones, or choose a pile with one stone (if it exists).
Let’s analyze both possibilities.

Case 1: Alice chooses a pile with \ge 2 stones.
Now, if there’s some other pile that also contains \ge 2 stones, then no matter what, after Alice’s move there will be a pile with \geq 2 stones remaining, while the total number of stones decreases.
By the inductive hypothesis Bob has a \frac{1}{2} probability of winning all such scenarios - so Alice also has a \frac{1}{2} chance of winning them. This means Alice has a \frac{1}{2} chance of winning from the current state as well.

That leaves the case where the current pile is the only one that contains \ge 2 stones.
The analysis for this is the same as what was done for the one pile case: there’s a \frac{K-2}{K} chance of leaving \ge 2 stones remaining (which each give a \frac{1}{2} chance of victory), and there’s a \frac{1}{K} chance each of leaving 0 and 1 stone in this pile.
Since every other pile has \leq 1 stone in it, leaving \le 1 stone in this pile determines the winner uniquely by parity; thus one of them has a winning probability of 0 and the other has 1.
So, Alice’s win probability in this case is \frac{1}{K} \left(0 + 1 + \frac{K-2}{2}\right) = \frac{1}{2} again.

Case 2: Alice choose a pile with one stone.
Here, after Alice’s move there will still be a pile with \ge 2 stones, which by induction Bob has a \frac{1}{2} chance of winning - and so Alice has a \frac{1}{2} chance of winning too.

Interestingly, the above proof also shows that there is no optimal strategy at all!
No matter which piles Alice and/or Bob choose on their moves, they cannot affect their probability of victory, and the result of the game is decided entirely by randomness.

To recap:

  • If all piles have one stone, Alice wins if N is odd and Bob wins otherwise, so the respective probabilities are 1 and 0.
  • If some pile has \geq 2 stones, the answer is \frac{1}{2}, which under the given modulo is 499122177.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    if a.count(1) == n:
        print(1 if n%2 == 1 else 0)
    else:
        print(499122177)
3 Likes