1
$\begingroup$

I was reading Elementary Number Theory and Its Applications by Rosen wherein I came across the problem (located on Page 31 summarized below)

Consider the Game Nim. In this game there exist a finite set of finite-sized sets of matches on the ground. Players take turns picking up one or more matches from one pile at a time. The Player to pick up the last match wins.

Define a Winning setup as a set of piles labelled $1,2 ... n$ each with number of matches $m_1 ... m_n$ such that a Player can force a win against his/her opponent if the opponent starts the game on this setup.

An example is 2 matches on the ground in separate piles, the second player will always win. Since whatever match the first player picks leaves exactly 1 other match (in a separate pile) behind.

A more involved example arises if you consider 2 sets of k matches. This too is a winning setup since if the first player picks up R matches from 1 pile, then the second player need only to pick up R matches from the opposite pile re-setting the game only this time with (k-r) matches. As this strategy evolves eventually the first player will be forced to exhaust one of the piles allowing the second player to win.

Having understood the game here is the main question:

if you express the number of matches in each pile $u_1 ... u_n$ in binary notation and line up the binary numbers (so 1's digits lines up, 2's digit lines up, 4's digit lines up etc...) Prove that:

if the number of 1's in each column is an even number that this set up is a winning setup.

Now I can clearly see how the two examples I produced both satisfy this, but i'm not sure how to prove the general case.

I'm thinking induction on the piles and numbers in the piles (some sort of 2 dimensional inductive strategy)

But the behavior gets very complex imo when considering more than 2 seperate piles.

$\endgroup$
1

1 Answer 1

Reset to default
3
$\begingroup$

Hint:

1.- Prove that: the final case (no matches remaining in any of the rows) is a winning setup.

Trivial base case

2.- Prove that you if in your turn you get from the other player a situation where at least for one of the columns, the amount of ones is odd, then you can make a move that leaves every column with an even amount of ones.

If the #1's is odd in a single column that means that there exists a value $2^k$ that is less than the size of the heap such that if I subtract exactly that many matches the rest of the columns are unaffected and that particular column is now balanced (by introducing a $0$ where there was a $1$). Now select the LARGEST PILE and note for every individual odd column $c_i$ there exists a unique $k_i$ so the combination of all these can balance ALL the odd columns (removing $1$'s) and there exist $h_i$ such that $2^{h_i}$ can be added back to the pile (reducing what we take) to add $1$'s for balance.

3.- Prove that any move on a board that has an even amount of ones in every column will leave at least one column with an odd amount of ones.

Now any move on the board will either remove at least a single 1 digit (unbalancing it). Which to be balance requires the removal of additional 1's elsewhere: guaranteeing that it cannot be balanced after a single move (this is induction, but i'm not going to be too formal).

4.- What is the conclusion?

Thus we conclude that given a game with even 1's in all columns, the opposing player is forced to make it into odd 1's in some columns, and we can fix it, repeating this endlessly until the base case is achieved and we win.

EDIT: Added frogeyedpeas' comments where he explained how he proved the general strategy for Nim.

$\endgroup$
8
  • $\begingroup$ So point 1. trivial base case (i'm separating the proofs of the separate points) $\endgroup$
    – Sidharth Ghoshal
    Jul 25, 2014 at 5:43
  • $\begingroup$ point 2: if the #1's is odd in a single column that means that there exists a value $2^k$ that is less than the size of the heap such that if I subtract exactly that many matches the rest of the columns are unaffected and that particular column is now balanced (by introducing a 0 where there was a 1). Now select the LARGEST PILE and note for every individual odd column $c_i$ there exists a unique $k_i$ so the combination of all these can balance ALL the odd columns (removing 1's) and there exist h_i such that 2^{h_i} can be added back to the pile (reducing what we take) to add 1's for balance $\endgroup$
    – Sidharth Ghoshal
    Jul 25, 2014 at 5:43
  • $\begingroup$ Point 3: Now any move on the board will either remove at least a single 1 digit (unbalancing it). Which to be balance requires the removal of additional 1's elsewhere: guaranteeing that it cannot be balanced after a single move (this is induction, but i'm not going to be too formal) $\endgroup$
    – Sidharth Ghoshal
    Jul 25, 2014 at 5:48
  • $\begingroup$ Thus we conclude that given a game with even 1's in all columns, the opposing player is forced to make it into odd 1's in some columns, and we can fix it, repeating this endlessly until the base case is achieved and we win $\endgroup$
    – Sidharth Ghoshal
    Jul 25, 2014 at 5:49
  • 1
    $\begingroup$ derp... i'll just blame it on the fact it was 3:00 in the morning $\endgroup$
    – Sidharth Ghoshal
    Jul 25, 2014 at 17:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .