A staircase of n steps contains coins on some of the steps. Let (x_1,x_2,...,x_n

Question

A staircase of n steps contains coins on some of the steps. Let (x_1,x_2,...,x_n) denote the position with X_j coins on step j, j = 1,..., n. A move of staircase Nim consists of moving any positive number of coins from any step, j, to the next lower step, j - 1. Coins reaching the ground (step 0) are removed from play. A move taking, say, x chips from step j, where 1 lessthanorequalto x lessthanorequalto X_j, and putting them on step j - 1, leaves X_j - x coins on step j and results in X_j - 1 + x coins on step j-1. The game ends when all coins are on the ground. Players alternate moves and the last to move wins. Show that (x_1.x_2,..,x_n) is a P-position if and only if the numbers of coins on the odd numbered steps, (x_1,x_2,...,x_k) where k = n if n is odd and k = n - 1 if n is even, forms a P-position in ordinary Nim

Explanation / Answer

Nim is a mathematical game of strategy in which two players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap. The goal of the game is to be the player to remove the last object.

If x1, x3, . . . is a Nim

N-position then one can move some coins from an odd step and make a Nim P-position.

If x1, x3, . . . is a Nim P-position and the coins are moved from an odd step then the coins on the

odd steps now form a Nim N-position.

If x1, x3, . . . , ... is a Nim P-position and x coins are moved from step 2j to step 2j 1

then this creates a Nim P-position in x1, x3, . . . which can be countered by moving the x coins to step 2j 2.

It is to realize that the coins on the even steps do not matter.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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