Modified NIM Game with more than one pile

255 Views Asked by At

The game is played at two tables; on the first table, there are N heaps containing A1,A2,…,AN stones and on the second table, there are M heaps containing B1,B2,…,BM stones respectively.

Player1 must remove a positive number of stones from one of the piles at her current table and on player2's turn, player2 must remove a positive number of stones from one of the piles at his current table. Whoever cannot remove any stone from a pile loses.

If player1 wants then at her chance she can exchange the table .

Then how can we predict who will win?

I thought if m and n are equal then player2 wins but I think it is wrong.

1

There are 1 best solutions below

0
On

Call the first player A and the second B. If both players have identical distributions of piles, B wins. In all other cases, A wins.

Suppose first that A has more stones than B. Then A removes a single stone at each turn, and B must lose. If B has more stones than A, then A switches tables and wins, so we need only consider the case where they have the same number of stones. From what has gone before, we see that B must always keep the same number of stones as A, or he will lose. If A's largest pile is bigger than B's largest pile, then A removes his largest pile. Whatever B does, he will have more stones than A, and then A will win by switching tables. On the other hand, if A's largest pile is smaller than B's largest, he will switch tables and win.

We may assume therefore that the largest piles are the same. A removes his largest pile, forcing B to do the same. If the second-largest piles are different sizes, A wins, so we assume that they are the same. A continues removing his largest pile so long as it is the same size as B's larges. If the original distribution of piles is different, we eventually arrive at a situation where the players' largest piles are unequal, and A wins, removing his largest pile if it is the bigger one, and switching tables if it is smaller.

If the two distributions are identical, then B wins by copying A's moves. So long as A has a move, so does B.