This game is played on a staircase of n steps. On each step j for j = 1, ..., n

Question

This game is played on a staircase of n steps. On each step j for j = 1, ..., n is a stack of coins of size x_j greaterthanorequalto 0. Each player, in his turn, picks j and moves one or more coins from step j to step j - 1. Coins reaching the ground (step 0) are removed from play. The game ends when all coins are on the ground, and the last player to move wins. See Figure 1.7. Show that the P-positions in Staircase Nim are the positions such that the stacks of coins on the odd-numbered steps have Nim-sum 0.

Explanation / Answer

Note that if a palyer is moving say 'm' coin from an odd numbered step to an even numbered step then, since the number of steps are odd , there is atleast one more step that can be used by the opponent to move these coins from even numbered step to an odd numbered step and finish the game.

Similarly, if a player is moving 'n'coins from an even numbered step to an odd numbered step then , the oponent can move these coins to the next even numbered step and thus returing the nim_sum on the odd numbered step to previous value. Thus players have no role in the outcome and Nim_sum =0.

Hope this Helps!!

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.