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.