Let he who has no sin cast the first stone

Now, because in the question we are only allowed to take an amount of stones that is a power of $2$ , it is instructive to think $(mod 3)$ to hunt for losing positions. In fact, another hint to looking $(mod 3)$ is that we want Lino to remove 4 stones. So, trivially, if a pile of stone is a multiple of $3$ it is a losing position and if otherwise, then it is a winning position. Also, because there are multiple piles, it is also a good idea to think of parity . Because, suppose all $4$ piles are in a winning position, it is clear that the second player would win. Extending this logic, we see that if an even number of piles contain either $\equiv 1,2 (mod 3 )$ number of stones, then it would be a losing position for the first player. Obviously, if we are not in such a configuration we may always end up in this configuration and if we are in such a configuration we may always enter a new configuration. Basically, this means that if there is an odd number of piles for each residue $mod 3$ then it is a winning position.

Now, consider if there is an even number of piles of each $\equiv 0,1,2 (mod 3)$ . Obviously once Lino makes his move of removing $4$ stones, he would change the parity of the number of piles of that residue, thus making it a winning position for Calvin. It is routine to verify that if the starting configuration is otherwise, Lino can always, with his first move, make it a losing position for Calvin, in other words, make the number of piles per residue even (the interested reader should really attempt this!)

Now, notice that the losing configurations for Lino are easier to count. Whence we use the method counting the compliment . Keep in mind that there is a total of $4^6 = 4096$ different starting positions. We will group the dice throws into the different residue classes for easy referencing later, so a dice throw of $0, 3, 6$ would result in piles of $\equiv 1 (mod 3)$ , a dice throw of $1, 4, 7$ would result in piles of $\equiv 2 (mod 3)$ and a dice throw of $2, 5$ would result in piles of $\equiv 0 (mod 3)$ . Now, for it to be a losing position for Lino:

(a) if all $4$ piles are of a certain residue class. This is trivial to count. It's just $3^4 + 3^4 + 4^4 = 178$

(b) or $2$ piles each are of $2$ different residue classes. Firstly, there are $4 \choose 2 = 6$ ways to assign each pile a certain residue class. So the total number of ways is $6(3^2 \times 2^2 + 3^2 \times 3^2 + 3^2 \times 2^2) = 918$ .

Combining both scenarios, we find that the fraction that we desire is $1 - \frac{918+178}{4096} = \frac{375}{512}$ and $a + b$ is 887 .

Let $G(n)$ be the Grundy number of a single pile of size $n$ . Then $G(0) = 1$ , $G(1) = 1$ , and $G(n) \; = \; \mathrm{mex}\big\{ G(n-2^j) \, \big| \, j \ge 0\,,\,2^j \le n \big\} \qquad n \ge 2$ I claim that $G(n) \in \{0,1,2\}$ and $G(n) \equiv n$ modulo $3$ . This is easily proved by induction. Certainly $G(2) = \mathrm{mex}\{G(0),G(1)\} = 2$ . Suppose that $N \ge 3$ and the result holds for all $G(n)$ with $0 \le n \le N-1$ . Since $4 \equiv 1$ modulo $3$ , we deduce that $G(N - 2^{2j}) \, \equiv \, G(N-1) \qquad G(N-2^{2j+1}) \, \equiv \, G(N-2)$ modulo $3$ for all $j \ge 0$ , and hence $G(N) \,=\, \mathrm{mex}\{G(N-1),G(N-2)\}$ . That the result holds for $G(N)$ follows by checking cases.

As usual, the Grundy score for a board of this game, consisting of four piles containing $x_1,x_2,x_3,x_4$ counters is $G(x_1,x_2,x_3,x_4) \; = \; G(x_1) \oplus G(x_2) \oplus G(x_3) \oplus G(x_4)$ and the position is a losing one precisely when $G(x_1,x_2,x_3,x_4)=0$ . Thus we are interested in the Grundy score of the opening position $G(10+d_1,100+d_2,1000+d_3,10000+d_4)$ which is the same as $G(1+d_1) \oplus G(1+d_2) \oplus G(1+d_3) \oplus G(1+d_4)$ Since each of $G(1+d_j)$ is either $0$ , $1$ or $2$ , this opening Grundy score is either $0,1,2$ or $3$ , and is easy to calculate. Let $N_0$ be the number of $d_j$ such that $G(1+d_j) = 0$ , let $N_1$ be the number of $d_j$ such that $G(1+d_j)=1$ , and let $N_2$ be the number of $d_j$ such that $G(1+d_j)=2$ . Then it is clear that the value of $G(10+d_1,100+d_2,1000+d_3,10000+d_4)$ is determined by the parity of the numbers $N_0,N_1,N_2$ (which, of course, add to $4$ ).

$\begin{array}{|c|c|c|c|}\hline N_0 & N_1 & N_2 & G \\ \hline E & E & E & 0 \\ O & O & E & 1 \\ O & E & O & 2 \\ E & O & O & 3 \\ \hline \end{array}$ In each of the opening positions with winning Grundy scores, it is possible to make a winning move by taking $4$ off a pile:

1. If $N_0$ and $N_1$ are odd, take $4$ off a pile with $G(1+d_j)=1$ , reducing the number $N_1$ by $1$ and increasing the number $N_0$ by $1$ , making both even.

2. If $N_0$ and $N_2$ are odd, take $4$ off a pile with $G(1+d_j)=0$ , reducing the number $N_0$ by $1$ and increasing the number $N_2$ by $1$ , making both even.

3. If $N_1$ and $N_2$ are odd, take $4$ off a pile with $G(1+d_j)=2$ , reducing the number $N_2$ by $1$ and increasing the number $N_1$ by $1$ , making both even.

Since each pile contains at least $10$ stones initially, there is no difficulty taking $4$ stones off any pile. Let us count the number of losing starting positions (for Lino), namely the ones where $N_0,N_1,N_2$ are all even. Note that there are two values of $d$ for which $G(1+d)=0$ three values of $d$ for which $G(1+d)=1$ , and three for which or $G(1+d) = 2$ . $\begin{array}{|c|c|c|c|} \hline N_0 & N_1 & N_2 & \mathrm{Count} \\ \hline 4 & 0 & 0 & 2^4 = 16 \\ 0 & 4 & 0 & 3^4 = 81 \\ 0 & 0 & 4 & 3^4 = 81 \\ 2 & 2 & 0 & {4 \choose 2}\times2^2\times3^2 = 216 \\ 2 & 0 & 2 & {4 \choose 2}\times2^2\times3^2 = 216 \\ 0 & 2 & 2 & {4 \choose 2}\times3^2\times3^2 = 486 \\ \hline \end{array}$ making a grand total of $1096$ losing positions. Thus there are $8^4 - 1096 = 3000$ winning opening positions for Lino, and hence his probability of winning is $\frac{3000}{8^4} = \frac{375}{512}$ . Thus the required answer is $375+512 = 887$ .

Consider first if there were only one pile of $n$ stones. We can give it a "Nim-sum" of $n \mod 3$ . If the Nim-sum is $0$ the player to move loses (I'll call this a losing position), otherwise the player to move wins.

Since $3 \nmid 2^k$ , if the position is $0$ then any move makes it non-zero. And if the position is $1$ then we can remove $2^0 = 1$ stones, and if the position is $2$ we can remove $2^1 = 2$ stones. So, this is a correct definition for a Nim-sum because if it is non-zero then there exists a move to make it zero; and if it is zero then all moves make it non-zero.

As an aside, that means that the rule "remove any power of two" could be replaced with "remove either one or two stones" and the outcome of the game would remain the same.

According to the Sprague-Grundy theorem, we can extend this from one pile to multiple piles by taking the bitwise-XOR of the Nim-sum of each pile, i.e. $i ⊕ i = 0, 1 ⊕ 2 = 0, 1 ⊕ 0 = 1, 2 ⊕ 0 = 2$ .

Now to consider the condition that Lino must remove $4$ stones to start. By the pigeonhole principle, since there are $3$ possible Nim-sums, any position with $4$ piles must have two piles with the same Nim-sum.

Now consider the remaining two piles. In a winning position, they must be either $\{0,1\}, \{1,2\}, \mbox{or} \{0,2\}$ They can't be the same otherwise the Nim-sum of the entire position would be $0$ . In these positions, the following moves leave a losing position respectively: $\{1 \rightarrow 0\}, \{2 \rightarrow 1\}, \{0 \rightarrow 2\}$

Each of those moves can be done by removing $4 \equiv 1 \mod 3$ stones, so this condition on Lino's first move can be fulfilled in any winning position.

Finally, we just need to count up how many winning positions there are. In fact it's simpler to count the number of losing positions. Since $10^i \equiv 1 \mod 3$ , each pile will start off with a Nim-sum of $P(0) = {3 \over 8}, P(1) = {3 \over 8}, \mbox{or} P(2) = {2 \over 8}$ .

Here is a list of all the losing combinations (i.e. Nim-sum zero) along with how many of the $8^4$ possible starting positions have that combination:

$\begin{aligned} 0000 &\rightarrow \binom{4}{0} 3^4 \\ 1111 &\rightarrow \binom{4}{0} 3^4 \\ 2222 &\rightarrow \binom{4}{0} 2^4 \\ 0011 &\rightarrow \binom{4}{2} 3^4 \\ 0022 &\rightarrow \binom{4}{2} 3^2 2^2 \\ 1122 &\rightarrow \binom{4}{2} 3^2 2^2 \\ \end{aligned}$ Totalling those up gives ${1096 \over 8^4} = {137 \over 512}$ . The number of winning positions is the complement of this, i.e. $\boxed{375 \over 512}$