On Fri, 8 Sep 2006 franktaw@netscape.net wrote:
Well, it isn't the minimum for the case n=1 (8 people, 2x2 grid), where my previous posting showed a solution with the absolute minimum of 28 person moves (which were all to an adjacent cell).
Franklin T. Adams-Watters
Franklin, If you don't count the moves to get to the original configuration then your method and mine (for the case of 8 people) each take only 6*4 = 24 moves)--as my formula as well as direct implementation shows. But, your new "circular" method certainly beats mine in all other cases! I think your solution wins the cigar. And, it works for any configuration which is "Hamiltonian". I wonder if there is an existing square dance based on that pattern? --Edwin
-----Original Message----- From: eclark@math.usf.edu
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. ... 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
________________________________________________________________________ Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading spam and email virus protection.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
--------------------------------------------------------- W. Edwin Clark, Math Dept, University of South Florida http://www.math.usf.edu/~eclark/ ---------------------------------------------------------