All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Games
The Fifteen Steps (Posted on 2004-04-26) Difficulty: 5 of 5
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?

No Solution Yet Submitted by Gamer    
Rating: 3.8000 (5 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Hints/Tips Four man game | Comment 6 of 16 |

Before I begin on the four man game, first consider the two man game.  If a player puts a man on step 0, the other player wins by placing the other man on step 1.  Similarily, if a player puts a man on step 1, the other player wins by placing the other man on step 0.  Therefore whoever is first to force their opponent to put a man on step 0 or 1 wins. 

The first to put a man on 2 or 3 will lose since the opponent can take the other of 2 or 3, thereby forcing the first player to move to 0 or 1.

The general strategy for the two man game is to create a couple on steps (0,1), (2,3), (4,5), ..., (2n, 2n+1), ... etc.  If the game started as {9,16} then the winning move is to move 16 to 8.

The three man game is just like the four man game with a man on step 0 and the others shifted up by one step.  The three man game {2,4,7}, it is equivalent to the four man game {0,3,5,8}

The four man game breaks into three cases:
1) There are two couples.  This is essentially two two-man games played simultaneously.
2) There is one couple.  The player will want to reduce the game to case 1.
3) There are no couples.  The player will want to keep it this way to force the opponent to make the first couple.

We can plan case 3 by using a recursion.  We will zoom out and view two steps as one.  The case 3 game X{1,4,7,11} becomes Y{0,2,3,5}.  In game Y, the winning move is moving 5 to 1.  So we will want to move X5 to X2 or X3, but which one?

When we zoomed out, we lost some detail, that detail is whether the original game's men were on even or odd steps.  We want to keep the number of odd steps to an even number.  That way if the opponent moves within a couple (1 to 0 or 7 to 6), we can respond with an identical kind of move. 

In game X there were three odd steps (1,7,11), so we will want to choose 11 to 2 over 11 to 3 to make the number of odd steps even.

Sometimes the recursion will show us two couples at the higher level.  Consider X{1,3,9,10} (9,10 is not a couple).  The recursion gives Y{0,1,4,5}.  The two couples are (0,1) and (4,5). 

The player will want to keep the couples as they are, so we will make a move within a single element of a couple.  The odd men in game X are 1, 3, and 9.  Our move is to move one of those down by one.  Note this is a winning move because there are three odd steps.  If there were only two odd steps like in game {1,3,8,10}, there would be no winning move due to parity.

Sometimes multiple recursions are necessary.  One such example is game A{5,12,33,43}.  The first recursion gives B{2,6,16,21}, the second gives us C{1,3,8,10} and finally the third gives us D{0,1,4,5}.  D has two couples, so we want to keep it as two couples and move within the scope of a single step on D.

A has three odd steps, an adjustment of 1 is needed.  B has one odd step, an adjustment of 2 is needed.  C has two odd steps, an adjustment of 4 is NOT needed.  We need to find which of the steps in A satisfies (n nim 3) mod 8 = 0.  n=43 works so the move is 43 to 40.

Another example is game A{3,18,29,41}  Then we have B{1,9,14,20}, C{0,4,7,10} and D{0,2,3,5}.  Clearly from game D, we need to move from 5 to 1.  This entails moving 41 to some value in the range 8 to 15 (D1 covers A8 to A15).

A has three odd steps, B has two odd steps, and C has one odd step.  An adjustment of 1+0+4=5 mod 8 is needed.  (41 nim 5) mod 8 = 4 and 12 mod 8 = 4, so our move is 41 to 12.


  Posted by Brian Smith on 2004-04-27 15:24:16
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information