On Thursday 31 August 2006 00:49, Daniel Asimov wrote:
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.)
Well, here's a straw-man set of itineraries, for any 4-connected rectangular torus. (So it works also for your hexagonal tori, which can be thought of as square tori with some extra connections.) Half the people stay where they are throughout. The other half (move up n-1 times, then right once) n times, thus traversing the entire network. Er, that's one move too many (it produces a cycle); omit the last one. If more than half the people stay where they are on any step, then (pigeonhole) two of them must be in the same cell, so they remain in the same cell, so one pairing is wasted, so that's impossible. So my straw-man itinerary-set minimizes the total number of moves. -- g