On Wed, 30 Aug 2006, Ed Pegg Jr wrote:

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.

Here is a solution which requires 64*134 unit person moves. (Instead of cells I'm using 64 tables. Each with two chairs-- one on the left and one on the right.) One person moving from one table to an adjacent table is what I'm calling a "unit person move". While explaining it to Ricardo Restrepo he noticed that a lower bound would be 64*127 (at each of the 127 bell ringings at least one person must move from each of the 64 tables since in all there must be binomial(128,2) = 64*127 meetings. So the 64*134 is pretty close to the minimum. The idea is the following: Stage #1: Start with the 8x8 array of tables. There is an obvious Hamiltonian cycle through the array (think of it as a grid graph). Say that each table has a left side and a right side. Each person on the right of a table moves to the next table along the Hamiltonian cycle. Those on the left of each table remain seated. After 63 moves everybody on the left has been paired with everybody on the right of the tables. This gives a total of 64*63 unit person moves. Stage #2: Now the lefts must be paired with the lefts and the rights with the rights. To do this we do some major shifting: Each person sitting on the right side of a table in the first four columns interchanges places with the person on the left side of the table 4 places to his right. This gives us two 8 x 4 grids of previously unpaired people. This shifting requires 64*4 unit person moves. (Each interchange is 2*4 unit person moves.) Stage #3: Now as before each of the 8x4 grids of unpaired people has a Hamiltonian cycle. Again those on the left of a table stay fixed and those on the right move to the next table along the Hamiltonian cycle. After 31 moves everybody on the left has been paired with everybody on the right in each of the two 8x4 grids. This adds another 64*31 unit person moves. Stage #4: Now we shift people again in each of the 8x4 girds so that those on the left are moved to the top 4 rows and the rights are moved to the bottom 4 rows. Doing this for each of the 2 8x4 grids gives us 4 4x4 grids of tables of previously unmatched people. To get to this stage requires 64*4 unit person steps. Stage #5: Then using a Hamiltonian shift as above for each of the 4x4 grids we pair up those on the left with those on the right. In all this requires 64*15 unit person moves. Stage #6: Next the 4 4x4 grids are shifted to 8 4x2 grids in 64*2 unit person moves. .....And so forth till one reaches 64 1x1 grids. When all is completed, the total is 64*134 unit person moves. Clearly this method generalizes from 128 to any number of the form 2^(2n+1). In which case the number of unit person moves taken by this method is 2^(2n)(2^(2n+1)-4+2^(n+1)-2n) Could this be the true minimum? --Edwin