Ed writes: << 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.
This is a lovely problem, even if we're still discussing its precise definition. I'm partial to the triangular lattice since it's the only symmetric 2D lattice such that any intersecting pair of Voronoi regions (in this case closed hexagons) intersect along an edge. (Though there is no necessary reason the network need be 2D; there is a natural generization in each dimension; in 3D it's the tiling by truncated octahedra). And I'm notorious in these quarters for preferring a torus over a bounded region, to avoid those pesky edge effects. Imo the most symmetric such tori of all are those arising from an iterative tiling by rosettes of 7 (of the preceding rosette, the first one just being 6 hexagons around 1 of them). Thus the number of nodes in these cases is a power of 7: 7, 49, 343, 2401, 16807, . . .. A torus of 49 seems a nice place to start. (Though 49 is clearly not as friendly a number as 120, which is my guess why Ed wanted to use that one -- its being both 5! and T_15.) Another nice feature of 7^n tori like this is that their network can be colored with 7 colors in a highly symmetric repeating pattern. A compromise would be considering the next most symmetrical such (triangular-lattice-based) tori, which imo are those which arise from an n x n rhombus; the nicest of reasonable size might be 12 x 12, since it's a both a square and a Fibonacci number, and also has more factors than any nearby number other than 120. (All these 60-deg. rhombic tori are in a strong sense "hexagonal" too, but the hexagon doesn't interact as nicely with the network when the # of nodes is not a power of 7.) But I'm interested in starting with the highly symmetric 7 x 7 hexagonal torus network of 49 nodes, each connected to 6 others. We can ask this question: Given 98 people, two on each node of this network at each stage, we want each one to have an itinerary (moving to an adjacent node, or staying put, on each step) such that each person shares a node with each of the other 49, such that the least total number of moves-to-an-adjacent-node are used. (Making no assumptions about the number of steps necessary.) This is clearly only one of many possible ways the details can be made precise. --Dan