The game Same-Nim is a two player game played with piles of stones. A valid move consists of removing a positive number of stones from one of the piles, such that there is some pair of piles that contains the same number of stones. The players alternate turns to make a move. A player loses the game if they are unable to remove any stones on their turn.

A game of Same-Nim is played with 4 piles of sizes $(30,30,a,b),$ where $1 \leq a, b \leq 30.$ For how many of the $900$ possible ordered pairs $(a,b)$ does the first player have a winning strategy?

**
Details and assumptions
**

A valid move may result in more than 1 pair of piles that contain the same number of stones.

The pair of piles with the same number of stones may both have $0$ stones, if the piles had stones in them when the game started.

The answer is 870.

**
This section requires Javascript.
**

You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.

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.

4 Helpful
0 Interesting
0 Brilliant
0 Confused

2 Helpful
0 Interesting
0 Brilliant
0 Confused

Can you explain why the game ends with all 4 values equal to the original lowest value?

Lino Demasi
- 7 years, 6 months ago

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$ .

1 Helpful
0 Interesting
0 Brilliant
0 Confused

Can you explain why from $(x,x,x,y)$ the only valid move is to go to $(x,x,x,x)?$ Isn't it also a valid move to go to any point of the form $(z,x,x,y),$ for $z < x?$

Lino Demasi
- 7 years, 6 months ago

**
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}$
.

1 Helpful
0 Interesting
0 Brilliant
0 Confused

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)

0 Helpful
0 Interesting
0 Brilliant
0 Confused

×

Problem Loading...

Note Loading...

Set Loading...

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