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.
Best Answer
Hint:
1.- Prove that: the final case (no matches remaining in any of the rows) is a winning setup.
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.
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.
4.- What is the conclusion?
EDIT: Added frogeyedpeas' comments where he explained how he proved the general strategy for Nim.