So I'm trying to do qn $6$ (on pg I-13) about staircase Nim in Game Theory by Ferguson Game Theory, Ferguson and it's asking to prove that $(x_1, x_2, \ldots, x_k) \in P $ only if $(x_1, x_3, x_5, \ldots, x_k) \in P$ in ordinary Nim.

I have read the solutions here (on page I-4), solution and they don't make much intuitive sense to me. It'd be great if someone could offer a more concrete explanation.

  • $\begingroup$ Rather late in commenting on this, I apologize. But this game is not Lasker's Nim. So the title is misleading. Like the body of your question says, this is staircase Nim. $\endgroup$
    – user61318
    Sep 18 '19 at 10:16

They say that the winning strategy is to keep $(x_1, x_3, x_5, \ldots, x_k) \in P$ in ordinary Nim.

This can be shown by following the same $3$ steps as in the proof of Bouton's Theorem on Page I-11. Some notation first:

$$P_n := P \mbox{ in ordinary nim}$$

$$N_n := N \mbox{ in ordinary nim}$$

$$P_s := P \mbox{ in staircase nim}$$

$$N_s := N \mbox{ in staircase nim}$$

"Odd nim sum" is the nim sum of only the odd-numbered components, $x_1,x_3, \ldots,x_k$.

(1) The terminal position, $(0,0, \ldots ,0)$ has "odd nim sum" = $0$.

(2) If $(x_1, x_2, x_3, \ldots, x_n) \in N_s$, which we claim means $(x_1, x_3, x_5, \ldots, x_k) \in N_n$, then by the same reasoning as in the proof, if you arrange the odd-numbered components as a column addition (as in the examples on Page I-10), then you can choose the left-most column having an odd number of $1$s and choose any row having a $1$ in that column, changing that $1$ to $0$ and then changing any other digits to the right of it that will produce a $0$ odd-nim-sum. This moves the game to a position in $P_s$.

What this means is that if the game position is in $N_s$ then there is an odd-numbered step with at least one chip and you should choose to move the appropriate number of chips from one of those steps, using the same method as in ordinary nim.

(3) If $(x_1, x_2, x_3, \ldots, x_n) \in P_s$, which we claim means $(x_1, x_3, x_5, \ldots, x_k) \in P_n$, then again the same reasoning as in the proof can be applied. Any move made, whether it is to an odd- or an even-numbered step, necessarily changes the number of chips on exactly one odd-numbered step. This necessarily changes the odd-nim-sum from $0$ to some non-zero value, thus moving the game to a position in $N_s$.

In their solution, sentence $1$ refers to Step (3) above, and sentence $2$ (and $3$ I guess) refers to Step (2) above.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.