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?

It seems that the key is ensuring that, no matter what move your opponent makes, you want to ensure that you will still have a move. So, you want to leave an even number of people in positions that would allow them to be moved after any move.

In one particular case then, if given the situation (where 0 is an empty stair and 1 a full stair) starting at the bottom: 101110110000000 we want to leave both of the top two people in their positions because that guarantees that we can move one of them on the next turn. Thus we move one of the middle group of three down into the hole on the second stair.

Generalizing, I think the key strategy is to maintain an even number of people above the sixth stair from the bottom, where possible. Where this is not possible will only occur where the people are located one each on stairs 7-12. In this case, I would argue that the highest person (stair 12) be moved to one of the other stairs (not 1 or 2). This allows some movement and allows you to adjust accordingly to maintain an even number at a step higher than 6 later on.

This strategy is obviously not fully developed yet, but its a bit of a start.

Posted by Timothy on 2004-04-26 21:46:08