useless steps in staircase nim

1.1k Views Asked by At

Why are even steps useless in staircase nim and why do coins in even steps don't affect the game of nim ? I am trying to understand the stair case nim from this blog link to blog

but could not understand much .

1

There are 1 best solutions below

4
On

Let's have Alice and Bob play.

Alice decides to ignore the even stairs in making her game choices. She is so devoted to this idea that she cannot even see the even stairs. She will always move coins from odd stairs, never even, and consider them removed from play. She will consider herself as having lost if the odd stairs are empty at the start of her turn.

To Alice, this is almost Nim. The only difference is that Bob has a bunch of coins available to add to the piles on his turn, though he can only add to one pile at a time. This is bothersome to Alice, but she knows that Bob's supply is limited, so eventually he will not be able to add anymore. Her strategy is this: Place the odd stairs in a winning Nim position on her first turn. From then on, if Bob removes coins from odd stairs, she plays as per Nim strategy to move to a new winning position. If Bob adds coins to an odd stair, she just removes them again on her turn, which will restore her to the winning position she was in the turn before.

As long as she can move to a winning Nim position on the odd stairs on her first turn (i.e., the initial position is not a first-player loss), Bob has no strategy to avoid her. No matter what he does, she can move to a winning Nim position on odd stairs on her turn. This is true even after all the odd stairs are cleared. Bob may have more coins to add (by moving from even stairs), but this doesn't change the fact that Alice can just remove them again (i.e., move them down to the next even stair) on her next turn. Even though clearing the odd stairs does not mean an automatic win for Alice like it would in Nim, this just prolongs the game. It doesn't change the outcome.

Since there are always coins on odd stairs at the beginning of Alice's turn, she always has a move she can make. Therefore it will be Bob who eventually finds himself unable to move, and so loses.