In my rephrasing of Otto's solution, I should have mentioned that this method of having everyone meet everyone else is commonly used in English Country line dances, those described by the original source (John Playford, from 1651 on) as "longways for as many as will". In this context, the basic unit is a couple (two dancers), and instead of exchanging papers, a pair of couples spends one repetition of the dance engaged in some four-person choreography. At the end of the measure, the couples have switched places. Half the couples always move "up the hall" and the other half move "down the hall", except that when you fall off the top or bottom of the line, you may (depending on the parity of the number of couples dancing) have to sit out one round before coming back in going the other way. I don't know of a 17th c. source for the observation that the result is each couple dancing with each other one, but I have no doubt that the observation was made. I'll ask a friend who might know. --Michael Kleber On 9/1/06, Michael Kleber <michael.kleber@gmail.com> wrote:
Otto's answer is perfectly correct and certainly the simplest possible answer by any measure, but I'm afraid his mail may be misunderstood, so I'd like to rephrase it.
The problem does not actually require an 8x8 chess board: it would be enough to have a 64-square-long hallway, in which each square is adjacent to only two others, and the end squares to only one. (Clearly this solves the original problem, since you can make a chessboard into such a hallway by setting up rope dividers like they do at airport check-in lines, making the people walk boustrophedon-style.)
Arrange your 128 convention-goers in the hallway with two on each square, one facing right and one facing left. Except that one poor attendee broke his leg running to make his flight, so he gets to sit in the square all the way at the left end of the hallway, and doesn't move during the entire process.
Exchange papers with the person in your square, and then at each clock chime, move one square forewards. The person who enters the square at the left edge should exchange papers with the seated guy and turn around immediately, ready to move right next. The rightwards-facing person entering the square on the right edge should turn exchange papers and then turn around *instead of* moving on, so as to remain in that square for a second turn, this time facing leftwards. This means that after 127 chimes, everyone ends up right where they started.
The seated guy clearly gets an audience with everyone else. Other than him, everyone is following the same path, and it is obvious that each person must pass each other one twice. Spending two turns in the square at the right end of the hallway makes it so that one of those two meetings involves walking past each other during a chime, like ships passing in the night, while the other involves sharing a square for 30 seconds.
--Michael Kleber
On 8/31/06, Otto Smith <otto@olympus.net> wrote:
There is a simple solution that requires that 127 people to take 126 king move steps each. One person remains fixed.
Consider: If we arrange people in a line of two rows facing each other but as a circle joined at the ends a rotation looks as follows:
1 2 3 4 8 7 6 5
2 3 4 5 1 8 7 6
3 4 5 6 2 1 8 7
4 5 6 7 3 2 1 8
And finally back where we started at, but with the rows exchanged
5 6 7 8 4 3 2 1
Here we have met exactly half of the people.
Note that each even person meets every odd person and vice versus.
Now if we have an odd number of people and one square with no partner, a time out square, we start as follows.
1 2 3 4 9 8 7 6 5
And we do the rotation
2 3 4 5 1 9 8 7 6
3 4 5 6 2 1 9 8 7
4 5 6 7 3 2 1 9 8
5 6 7 8 4 3 2 1 9
6 7 8 9 5 4 3 2 1
7 8 9 1 6 5 4 3 2
8 9 1 2 7 6 5 4 3
9 1 2 3 8 7 6 5 4
Everybody meets everybody. Note that we move through the pairs at mod 2. Since there are an odd number of people, we are guaranteed to meet everyone with no repeats.
Now we can make use of this to generate a simple solution to the problem. For 10 folks do, the rotation but leave number one person fixed.
1 2 3 4 5 10 9 8 7 6
And we do the rotation
1 3 4 5 6 2 10 9 8 7
1 4 5 6 7 3 2 10 9 8
etc.
The algorithm is then to fix the first person and rotate the rest.
128 people can easily be arranged on an 8 X 8 grid.
Here are some smaller examples arranged on a grid.
Here it is with 8 folks in 4 squares
START -- STEP 1 (1, 8) (2, 7) (3, 6) (4, 5)
STEP 2 (1, 2) (3, 8) (4, 7) (5, 6)
STEP 3 (1, 3) (4, 2) (5, 8) (6, 7)
STEP 4 (1, 4) (5, 3) (6, 2) (7, 8)
STEP 5 (1, 5) (6, 4) (7, 3) (8, 2)
STEP 6 (1, 6) (7, 5) (8, 4) (2, 3)
STEP 7 (1, 7) (8, 6) (2, 5) (3, 4)
Here it is 16 folks in 32 squares
( 1, 32) ( 2, 31) ( 3, 30) (4, 29) ( 5, 28) ( 6, 27) ( 7, 26) ( 8, 25) ( 9, 24) (10, 23) (11, 22) (12, 21) (13, 20) (14, 19) (15, 18) (16, 17) ---- ( 1, 2) ( 3, 32) ( 4, 31) ( 5, 30) ( 6, 29) ( 7, 28) ( 8, 27) ( 9, 26) (10, 25) (11, 24) (12, 23) (13, 22) (14, 21) (15, 20) (16, 19) (17, 18)
( 1, 3) ( 4, 2) ( 5, 32) ( 6, 31) ( 7, 30) ( 8, 29) ( 9, 28) (10, 27) (11, 26) (12, 25) (13, 24) (14, 23) (15, 22) (16, 21) (17, 20) (18, 19)
... ... ...
( 1, 31) (32, 30) ( 2, 29) ( 3, 28) ( 4, 27) ( 5, 26) ( 6, 25) ( 7, 24) ( 8, 23) ( 9, 22) (10, 21) (11, 20) (12, 19) (13, 18) (14, 17) (15, 16)
Next step gets back to beginning
( 1, 32) ( 2, 31) ( 3, 30) ( 4, 29) ( 5, 28) ( 6, 27) ( 7, 26) ( 8, 25) ( 9, 24) (10, 23) (11, 22) (12, 21) (13, 20) (14, 19) (15, 18) (16, 17)
etc.
On an 8 by 8 grid, 127 people take 127 steps each. the 128th person remains fixed. Regards Otto
On Wednesday 30 August 2006 15:00, Ed Pegg Jr wrote:
Rewrite, to correct the errors.
At a convention, 128 people all need to meet with each other, 1 on 1, for a paper exchange.
Suppose a room is divided into a 8x8 square, and a clock is set up to ding 127 times, once every 30 seconds. Each person is given a map of their starting square, and a map of their route over the next hour and 4 minutes. Only two people can be in each cell.
Ideally, most moves should be King moves. Not needing to move during a turn is acceptable.
Simplicity is judged by the amount of text needed to explain the choreography, and the orderliness of the room.
Alternately, the length of the maximum walk should be minimised. Ed Pegg Jr _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
-- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.