Nim Variant - Strong Induction Proof

Question

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.

Answer 1

HINT: Let $P$ be the set of positions described in the question:

$$P=\{\langle 0,0\rangle\}\cup\{\langle 2n,2n-1\rangle:n\in\Bbb Z^+\}\;.$$

• Show that if $\langle m,n\rangle\notin P$, the person whose turn it is to move can always move to a position in $P$.
• Show that if $\langle m,n\rangle\in P$, every possible move will leave a position that is not in $P$.

This means that if the initial position is not in $P$, then White can always move so that Black is facing a position that is in $P$.

• Explain why this is a winning strategy for White if the initial position is not in $P$.

Use these ideas to describe what Black should do if the initial position is in $P$.

With this approach you don’t really need induction. If you do use induction, the induction hypothesis is that the assertion in the problem about which player has a winning strategy is true if the total number of stones in the two piles is less than $n$, and the induction step is to prove that it is then true if the total number of stones in the two piles is less than or equal to $n$.