There are 15 stairs arranged in a line. There are 6 people on various different steps.

The only rule is you can only move a person if you move it to any lower vacant stair.

In a two player game, you alternate moving single people. The last one to move a person wins! What strategy should you use in order to win?

What strategy would be used if the people couldn't pass each other when moving down the stairs?

The second part (no passing) is actually the easier of the two versions.  In this case, you are playing a cleverly disguised game of nim - the stacks are the alternating distances.

If the people stand on steps 3, 5, 9, 12, 17, 18 then the nim values are (18-17)-1=0, (12-9)-1=2, and (5-3)-1=1.  In this case a winning move is moving 12 to 11.

If there are an odd number of people, then the lowest is considered singly.  If the people are on 3, 5, 9, 12, 17, then the nim values are (17-12)-1=4, (9-5)-1=3, and (3)-1=2.  A winning move in this case is moving 17 to 14.

Posted by Brian Smith on 2004-04-27 08:40:16