Here we will play a variant of Nim where there is an additional move option in some cases. If two or more piles have the same number of stones, a player may remove the same number of stones from both of them. For example, if the contents of the piles are (2, 4, 4), the player to move could change this to (2, 3, 3), (2, 2, 2), (2, 1, 1), or (2, 0, 0), in addition to any of the moves available in ordinary Nim. Prove that in this game with two piles, White (the first player) has a winning strategy in any position with two exceptions: (0, 0) and (2n, 2n - 1) for any positive integer n. That is, Black wins if the start position is (0, 0), (2, 1), (4, 3), (6, 5),... and loses otherwise. (Of course there is no ordering on the piles, so (3, 4) is the same position as (4, 3) -- Black wins in either one.) Remember that a winning strategy must have a winning response to any legal move by the opponent. You probably want to use strong induction here, though it is not a requirement.
I've been thinking about this one for a while and I'm having difficulty even starting. I don't know what the inductive hypothesis would be, or how I would use strong induction on this. Since white will win as long as the start position isn't (2n, 2n - 1), will it suffice to prove white wins everything except in that case? Or that it must lose that specific case? How can you prove something by strong induction if it's not a simple matter of "n + 1?" Should I instead prove that black will only win if it starts at (2n, 2n - 1)? I understand this is somewhat of a big problem, and I've got a lot of big questions about it, but I would really appreciate any pointers or help.