4-pile Same-Nim

The first player will lose if a and b are the same number. If they are, a=b=x, there will be two group of same number of stones, group (30,30) and group (x,x). Whatever move the first player do, the second player just have to imitate that move to another pile in the same group. This will guarantee that the second player will get the last move.

If a and b are different numbers, the first player just have to get a number of stones from one of those two piles so those two piles consist of the same number of stones. Then it will be losing condition for the second player and winning condition for the first player.

So, there are $30 \times 29 = \boxed{870}$ ordered pairs of a and b for the first player to have winning strategy

My first guess for winning strategies in games where the last moves wins is "mimic the opponent": you create a symmetric position in which it doesn't matter what you opponent does because you can copy his move.

In this game such a strategy is possible:

If $a \neq b$ we can take away stones from the largest of these two piles to create the situation $(30, 30, x, x)$ . Now when your opponent takes some stones from a pile, you take away the same amount of stones from the other pile that had the same amount of stones before his move. This is always possible and leads to all piles having $0$ stones after your move. You win!

If $a=b$ then your opponent can use the strategy described above to win, so you will always lose.

There are $30$ ordered pairs with $a=b$ , so we have $900-30=870$ winning ordered pairs.

First we note that the game will always end with all four values equal to the original lowest value. WLOG, we assume that the smallest value is $a$ (i.e. assume $b≥a$ ). Then there are two cases to examine. First, if $a=b$ , then the first player must move to make one of the thirties into an $a$ (or $b$ , doesn't matter what you call it). Then the second player finishes the game by changing the other thirty, and the second player wins. If $a\not=b$ , then the first player can reduce $a$ so it is equal to $b$ , leaving the second player in the losing situation described earlier. Thus the first player can win whenever $a\not=b$ , which happens $900-30=\boxed{870}$ times.

Let's define a function $\text{Nim}[x_1,x_2,x_3,x_4]$ that computes whether it is possible for the first player to win a game of Same-Nim with the configuration $x = (x_1,x_2,x_3,x_4) \in \mathbb{X}$ where $x_1 \le x_2 \le x_3 \le x_4$ .

Now, in order for player one to have a winning strategy, there must be some move that we can make that ensures that player 2 loses. Equivalently, there exists some valid move/transformation $\sigma : \mathbb{X} \to \mathbb{X}$ (where $\sigma$ 's image is always ordered) such that we can ensure that when the second player plays the game on $\sigma(x)$ , he cannot win:

$\text{Nim}[x] = \bigvee_{\sigma} \neg \text{Nim}[\sigma(x)]$

Now, the problem we're given has an extremely interesting structure. We're counting all instances of $\text{Nim}[a,b,30,30]$ that are true. Going through a few trials, it seems that all cases of $a = b$ do not have a winning strategy:

*Lemma: * $\text{Nim}[x,x,y,y] = \bot$

Proof: There's only one valid move (up to permutations) for the configuration $(x,x,y,y)$ : the partial function $\sigma_1 = (x,x,y,y) \mapsto (x,x,x,y)$ Similarly, there's also only one valid move for $(x,x,x,y)$ : $\sigma_2 = (x,x,x,y) \mapsto (x,x,x,x)$ Therefore $\text{Nim}[x,x,y,y] = \neg\text{Nim}[x,x,x,y] = \neg\neg \text{Nim}[x,x,x,x]$ It's easy to verify that the configuration $(x,x,x,x)$ has no winning strategy, so $\text{Nim}[x,x,y,y] = \bot~~~~\blacksquare$

Therefore, we know immediately that all $\text{Nim}[a,a,30,30] = \bot$ . So if we have $b > a$ , then the move $\sigma = (a,b,30,30) \mapsto (a,a,30,30)$ is valid, so we know that $\text{Nim}[a,b,30,30] = \neg \text{Nim}[a,a,30,30] = \top$ ; hence, all $a \ne b$ will have a winning strategy, which counts to $900 - 30 = 870$ .

Claim The same-nim game $(30, 30, a, b)$ is winning if and only if the normal nim game $(a,b)$ is winning.

Proof We shall prove the sufficient condition first. We have to prove that if the normal nim game $(a,b)$ is winning, so is the same-nim game $(30, 30, a, b)$ . We consider this same-nim game as the combination of two games: $(30, 30)$ and $(a,b)$ . We call the first game $G_1$ , and we call the second game $G_2$ . We have to show that a winning strategy exists for the first player. More precisely, we shall prove that the winning strategy of the first player is to give his optimal move in the game $G_x$ , where the second player gave his last move in $G_x$ .

First, let's see what happens when both the players ignore the $(30,30)$ pile, and give their moves on the $(a,b)$ pile. Note that we don't have the restriction that the number of stones in each pile must be equal here, since we already have equal piles in $G_1$ . Since $(a,b)$ is winning, we know that the first player removes the last stone from this pile. Now this is the second player's move, and he has to give a move from the $(30,30)$ pile. Obviously he cannot do this, since he can remove stones from only one pile, and that makes the number of stones in each pile distinct.

Unfortunately, the proof isn't this simple. All we have been able to show that the optimal strategy of the second player is not to give his moves entirely in $G_2$ . Let's say he gives a move in $G_1$ . The general position of the game will then be of the form $(30, x, x, y)$ . Now, the first player changes the $30$ to $x$ , so we now have the game $(x, x, x, y)$ . It is easy to see that if they continue doing this, we will reach a point of time when the game $G_2$ is over (which means the first player has removed the last stone from it), and we have a pile of the form $(x,x)$ remaining, and it is the turn of the second player. This proves the sufficient condition.

The proof of the necessary condition is essentially the same, except that we flip the first player and the second player. We shall skip this proof.
$$ From our claim, we just need to the number of ordered positive integer pairs $(a, b)$ such that $1 \leq a, b \leq 30$ and $(a,b)$ is winning. Grundy theorem states that $(a,b)$ will be losing if and only if the nim sums of $a$ and $b$ are equal, i.e their binary representations are equal, i.e $a=b$ . So, for any $a \neq b$ , $(a,b)$ will be winning. Our desired answer is simply the number of ways of choosing and permuting two distinct elements from the set $\{1, 2, \cdots, 30\}$ , which is $^{30}P_{2} = \frac{30!}{28!}= \boxed{870}$ .

In order for the first player to have a winning strategy, the starting pile must have a nim-sum not equal to zero.

Since the first two piles already have a nim-sum equal to zero, the condition that needs to be satisfied by the two remaining piles(a,b) is that they should have a non-zero nim-sum which occurs whenever their starting sizes are not equal.

Note that there are only 30 possible ways to have equal starting sizes for this two piles.

Thus, the first player has a winning strategy on 900-30 = 870 possible pairs of (a,b)