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.)
Finally, the solution for the no-passing game. | Comment 14 of 16 |

This post expands on the method described in the Four man game post.

The six man game has four possible cases:
1) There are no couples
Use the recursion technique to reduce the game to one of the three other cases.

2) There are three couples
This is similar to the four man game with two couples.

3) There are two couples
This is similar to the four man game with one couple.

4) There is one couple
To solve this case, a new technique is needed, extraction.  Extraction is creating a related game by removing the couple(s) and splicing together the remaining parts of the game.  If a man is on a higher step than an extracted couple, he is moved down in the new game according to the number of couples removed.

Lets use the game A{2,6,8,9,16,21} as an example.  The couple is (8,9).  Extract the couple (8,9) from the game.  The new game is B{2,6,14,19}.
Using the technique discussed in the 'Four Man Game' post to find that the winning move in B is 19 to 18.  Working from game A to game B we find that 18 in game B is equivalent to 20 in game A, so the winning move in game A is 21 to 20.

If we have a larger game, the extraction strategy can be applied multiple times, alongside recursion.  Let the game be A{2,6,14,34,56,98,100,122,156,197}  The table below shows the steps in reducing the game.  The first column is a identifier for the game, the second column is the sqeuence of reduced games and the third column is the method used to generate that game.

A | 2,6,14,34,56,98,100,122,156,197 | Start
B | 1,3, 7,17,28,49, 50, 61, 78, 98 | Recursion
C | 0,1, 3, 8,14,24, 25, 30, 39, 49 | Recursion
D |      1, 6,12,        26, 35, 45 | Extraction
E |      0, 3, 6,        13, 17, 22 | Recursion
F |      0, 1, 3,         6,  8, 11 | Recursion
G |            1,         4,  6,  9 | Extraction
H |            0,         2,  3,  4 | Recursion


In game H it is easy to see that the winning move is 4 to 1.  Working backwards, the winning move for game A can be constructed:
H: 4 to 1
G: 9 to 3
F: 11 to 5
E: 22 to 11
D: 45 to 22
C: 49 to 26
B: 98 to 52
A: 197 to 104

A second example is A{5,25,33,43,61,63,96,101}

A | 5,25,33,43,61,63,96,101 | Start
B | 1,12,16,21,30,31,48, 50 | Recursion
C | 1,12,16,21,      46, 48 | Extraction
D | 0, 6, 8,10,      23, 24 | Recursion
E | 0, 3, 4, 5,      11, 12 | Recursion
F | 0, 3,             9, 10 | Extraction
G | 0, 1,             4,  5 | Recursion


In game G there is no winning move.  So, while working backwards through the game, we will continue to find there are no winning moves until one of the earlier games shows a parity difference.
G: none
F: none
E: none
D: none
C: 21 to 20
B: 21 to 20
A: 43 to 40

This time a parity difference was found in game C, if we found no parity difference in any of the games while working back, then there would have been no winning move at all.  If you are ever forced to play when there is no winning move, I recommend moving the highest man down one step and hope your opponent makes a mistake.

Edited on April 19, 2005, 3:42 pm
  Posted by Brian Smith on 2005-04-19 15:36:55

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 (2)
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