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 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