P.S. Re: [math-fun] Chinese Mathematicians Prove Poincare Conjecture
P.S. I did not see this in the Ximhua press release, but the Asian Journal of Mathematics says (in the link provided by Ray) that the article in question finishes the proof of the Thurston Geometrization Conjecture (of which the Poincare conjecture is just one of many important consequences). Up to now, a few media (Scientific American in 1994, New York Times in the past year) have claimed the Poincare conjecture has been proved, although no respectable professional journal has reported any such thing (only comments like "time will tell.") And not even media outlets have reported that the Geometrization conjecture was proved. Hmm. I guess time will tell. --Dan
dasimov@earthlink.net wrote:
P.S. I did not see this in the Ximhua press release, but the Asian Journal of Mathematics says (in the link provided by Ray) that the article in question finishes the proof of the Thurston Geometrization Conjecture (of which the Poincare conjecture is just one of many important consequences).
Up to now, a few media (Scientific American in 1994, New York Times in the past year) have claimed the Poincare conjecture has been proved, although no respectable professional journal has reported any such thing (only comments like "time will tell.")
And not even media outlets have reported that the Geometrization conjecture was proved.
On the Arxiv there is a 192 page preprint http://arxiv.org/PS_cache/math/pdf/0605/0605667.pdf which claims that the Geometrization conjecture _is_ proved. Gary McGuire
I'm not sure if it's been mentioned here. The latest Al Zimmermann Programming contest shattered all existing records in the field of Prime Generating Polynomials. For example, one polynomial that generates 49 primes is x^4 - 97*x^3 + 3294*x^2 - 45458*x + 213589, first found by Mark Beyleveld and later by 5 other participants. Even better polynomials were found. More results: CUBIC: -66 x^3 + 3845 x^2 - 60897 x + 251831. Prime for x=0 to 45. Ivan Kazmenko and Vadim Trofimov. 42 x^3 + 270 x^2 - 26436 x + 250703. Prime for x=0 to 39. Jaroslaw Wroblewski and Jean-Charles Meyrignac. QUARTIC: x^4 - 97x^3 + 3294x^2 - 45458x + 213589. Prime for x=0 to 49. Mark Beyleveld. QUINTIC: (x^5 - 133 x^4 + 6729 x^3 - 158379 x^2 + 1720294 x - 6823316)/4. x=0 to 56. Shyam Sunder Gupta. x^5 - 99x^4 + 3588x^3 - 56822x^2 + 348272x - 286397. x=0 to 46. Jaroslaw Wroblewski & Jean-Charles Meyrignac. SEXTIC: (x^6 - 126 x^5 + 6217 x^4 - 153066 x^3 + 1987786 x^2 - 13055316 x + 34747236)/36. Prime for x=0 to 54. Jaroslaw Wroblewski & Jean-Charles Meyrignac. Full details and findings will eventually be published at At http://www.mathpuzzle.com/ I have about 40 other math stories... it's been a busy month. Ed Pegg Jr
In connexion with the following, does
the Hardy-Littlewood asymptotic density
c * sqrt(n) / ln n
apply here? Or should it be d-th root
where d is the degree of the polynomial?
How many primes among the first 10000
values of n in each case?
Has anyone calculated the values of c
(if that's relevant) ?
On Mon, 26 Jun 2006, Ed Pegg Jr wrote:
> I'm not sure if it's been mentioned here.
>
> The latest Al Zimmermann Programming contest shattered all existing records in the field of Prime Generating Polynomials.
> For example, one polynomial that generates 49 primes is x^4 - 97*x^3 + 3294*x^2 - 45458*x + 213589, first found by Mark
> Beyleveld and later by 5 other participants. Even better polynomials were found. More results:
>
> CUBIC:
> -66 x^3 + 3845 x^2 - 60897 x + 251831. Prime for x=0 to 45. Ivan Kazmenko and Vadim Trofimov.
> 42 x^3 + 270 x^2 - 26436 x + 250703. Prime for x=0 to 39. Jaroslaw Wroblewski and Jean-Charles Meyrignac.
>
> QUARTIC:
> x^4 - 97x^3 + 3294x^2 - 45458x + 213589. Prime for x=0 to 49. Mark Beyleveld.
>
> QUINTIC:
> (x^5 - 133 x^4 + 6729 x^3 - 158379 x^2 + 1720294 x - 6823316)/4. x=0 to 56. Shyam Sunder Gupta.
> x^5 - 99x^4 + 3588x^3 - 56822x^2 + 348272x - 286397. x=0 to 46. Jaroslaw Wroblewski & Jean-Charles Meyrignac.
>
> SEXTIC:
> (x^6 - 126 x^5 + 6217 x^4 - 153066 x^3 + 1987786 x^2 - 13055316 x
+ 34747236)/36. Prime for x=0 to 54. Jaroslaw Wroblewski & Jean-Charles Meyrignac.
>
> Full details and findings will eventually be published at
>
> At http://www.mathpuzzle.com/ I have about 40 other math stories... it's been a busy month.
>
> Ed Pegg Jr
> _______________________________________________
> math-fun mailing list
> math-fun@mailman.xmission.com
> http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
>
It's an old problem to find a formula for primes. With so little success, we lower our sights, and look for formulas that produce primes for a while, or that produce more primes than expected. For polynomials, it looks like a formula can raise the percentage of primes by a constant factor. (Trivial example: 30N+1 has 3.75 times as many primes as N.) Challenge: Find a formula with a better "score" -- One whose values are more likely than average to be prime, with the improvement more than a constant factor. N!+1 might work, but any improvement over 1/logN is microscopic. The baseline assumes a prime likelihood of 1/logN. I'm not sure how to score formulas like 1+2^2^N, which we would accept as a perfectly valid prime formula if it worked, but whose total sum 1/logN is bounded. If we limit ourselves to formulas with sum 1/logN unbounded, the universe of potential formulas is much smaller. But if we don't, the set of numbers grows too fast to test very many. More sophisticated challenge: Find a formula whose prime likelihood is something different from Constant * 1/logN. Or a formula that generates numbers *less* likely to be prime, excluding trivialities like X^2 + X + 4. Or a formula that has anything other than the usual expected distribution for the number of distinct prime factors. (Again, excluding trivialities like N^2 or N^2-1.) Rich -----Original Message----- From: math-fun-bounces+rschroe=sandia.gov@mailman.xmission.com on behalf of Ed Pegg Jr Sent: Mon 6/26/2006 8:09 AM To: math-fun Subject: [math-fun] Prime Generating Polynomials I'm not sure if it's been mentioned here. The latest Al Zimmermann Programming contest shattered all existing records in the field of Prime Generating Polynomials. For example, one polynomial that generates 49 primes is x^4 - 97*x^3 + 3294*x^2 - 45458*x + 213589, first found by Mark Beyleveld and later by 5 other participants. Even better polynomials were found. More results: CUBIC: -66 x^3 + 3845 x^2 - 60897 x + 251831. Prime for x=0 to 45. Ivan Kazmenko and Vadim Trofimov. 42 x^3 + 270 x^2 - 26436 x + 250703. Prime for x=0 to 39. Jaroslaw Wroblewski and Jean-Charles Meyrignac. QUARTIC: x^4 - 97x^3 + 3294x^2 - 45458x + 213589. Prime for x=0 to 49. Mark Beyleveld. QUINTIC: (x^5 - 133 x^4 + 6729 x^3 - 158379 x^2 + 1720294 x - 6823316)/4. x=0 to 56. Shyam Sunder Gupta. x^5 - 99x^4 + 3588x^3 - 56822x^2 + 348272x - 286397. x=0 to 46. Jaroslaw Wroblewski & Jean-Charles Meyrignac. SEXTIC: (x^6 - 126 x^5 + 6217 x^4 - 153066 x^3 + 1987786 x^2 - 13055316 x + 34747236)/36. Prime for x=0 to 54. Jaroslaw Wroblewski & Jean-Charles Meyrignac. Full details and findings will eventually be published at At http://www.mathpuzzle.com/ I have about 40 other math stories... it's been a busy month. Ed Pegg Jr _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
A friend of mine has a cube, composed of several convex objects. He has to provide 2 cross sections of this cube, from left and right. What is the minimum number of colors needed so that no two shapes within a cross section have the same color? I'm thinking it is 9, based on the Earth-Mars 2-pire problem. http://www.fortunecity.com/emachines/e11/86/mpire.html (Has any progress been made on this problem? Has a map needing 10 colors been found?) How about if top, left, right cross sections must be provided? What is the minimal number of colors then? Ed Pegg Jr
At a convention, 120 people all need to meet with each other, 1 on 1. Suppose a room is divided into a 8x8 square, and a clock is set up to ring 60 times, once per minute. Each person is given a map of their starting square, and a map of their route over the next hour. What is the simplest set of maps? What is the length of the minimal walks people need to take? Ed Pegg Jr
On 8/30/06, Ed Pegg Jr <ed@mathpuzzle.com> wrote:
At a convention, 120 people all need to meet with each other, 1 on 1.
Suppose a room is divided into a 8x8 square, and a clock is set up to ring 60 times, once per minute. Each person is given a map of their starting square, and a map of their route over the next hour.
What is the simplest set of maps? What is the length of the minimal walks people need to take?
Ed Pegg Jr
This problem does not appear to be well-defined. (1) How many people can occupy one cell simultaneously --- two? (2) Are diagonal moves permitted, or just orthogonal? (3) Are moves only to adjacent cells? (4) Why 120 rather than (say) 128? (5) What criteria constitute "simplicity" in this context? (6) Is the length of the maximum walk to be minimised? The mean? WFL
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
Upper bound: One classic approach to a round-robin tournament is to arrange a line of chessboards with seats on opposite sides. One player, say X, is selected to sit still. All other players move one seat to their left, skipping past player X. A player who reaches the end of the line moves to the other side of the same table. (In other words, all players move one seat counter-clockwise, skipping X.) This approach readily translates to the checkerboard once you fix a Hamilton path. If I've counted correctly, 1 person stands still. 1 person moves 127 squares. All others move 126 squares. On 8/30/06, Ed Pegg Jr <ed@mathpuzzle.com> 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
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
On 9/1/06, Otto Smith <otto@olympus.net> wrote:
There is a simple solution that requires that 127 people to take 126 king move steps each. One person remains fixed. ... [etc]
I've a feeling that diagonal moves are necessary for a solution; but can't put my finger on the precise reason ... WFL
No. In fact, Otto's solution does not require any diagonal moves. On the other hand, it probably isn't the optimal solution (in terms of max total distance moved). Let's look at the 2x2 case with 8 people and 7 rounds. the following solution: 15 26 37 48 16 25 38 47 36 45 18 27 35 46 17 28 13 24 57 68 14 23 58 67 12 34 56 78 has exactly 4 people making an orthogonal move each round, with the others staying in place, and nobody moves more than 4 times. I'm not sure that this is optimal; it may be possible to have nobody move more than 3 times - which would mean that everybody moves exactly 3 times. (It is, of course, optimal for the total distance moved by all the participants.) This doesn't prove that you can beat Otto's solution on a larger board, but it does suggest it. Note that, if Otto's solution looks like line dancing, this one looks like square dancing - although square dancers usually only want to dance with the dancers of the opposite sex. Franklin T. Adams-Watters -----Original Message----- From: fred.lunnon@gmail.com On 9/1/06, Otto Smith <otto@olympus.net> wrote:
There is a simple solution that requires that 127 people to take 126 king move steps each. One person remains fixed. ... [etc] I've a feeling that diagonal moves are necessary for a solution; but can't put my finger on the precise reason ... WFL
________________________________________________________________________ Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading spam and email virus protection.
Melbourne now has two spectacular geometrical buildings. #1. Digital Harbour Port 1010 http://www.a-r-m.com.au/news.php This building demonstrates the Cafe-Wall or Munsterburg Illusion. http://mathworld.wolfram.com/CafeWallIllusion.html #2. Melbourne Federation Square http://local.wasp.uwa.edu.au/~pbourke/texture/pinwheel/ This building demonstrates aperiodic pinwheel tiling. Other than buildings in particular shapes (pyramids, spheres, domes, cubes), are there any other buildings that demonstrate math principles? Can any city compare to Melbourne now? A nice cube is the Atomium. http://mathworld.wolfram.com/Cube.html Ed Pegg Jr
Ed Pegg Jr wrote:
Melbourne now has two spectacular geometrical buildings.
A third example is the use of Penrose tiles in Storey Hall at RMIT. I live in Melbourne and did my degree at RMIT, but long before Storey Hall had its dramatic facelift: http://condellpark.com/kd/rmit20_25.jpg (part of an interesting site: http://condellpark.com/kd/quasig.htm) Andrew
Other spectacular buildings: http://www.uniquedaily.com/articles/TMULBOOEE.html but not demonstrating math principles, I think... Christian.
Otto's answer is perfectly correct and certainly the simplest possible answer by any measure, but I'm afraid his mail may be misunderstood, so I'd like to rephrase it. The problem does not actually require an 8x8 chess board: it would be enough to have a 64-square-long hallway, in which each square is adjacent to only two others, and the end squares to only one. (Clearly this solves the original problem, since you can make a chessboard into such a hallway by setting up rope dividers like they do at airport check-in lines, making the people walk boustrophedon-style.) Arrange your 128 convention-goers in the hallway with two on each square, one facing right and one facing left. Except that one poor attendee broke his leg running to make his flight, so he gets to sit in the square all the way at the left end of the hallway, and doesn't move during the entire process. Exchange papers with the person in your square, and then at each clock chime, move one square forewards. The person who enters the square at the left edge should exchange papers with the seated guy and turn around immediately, ready to move right next. The rightwards-facing person entering the square on the right edge should turn exchange papers and then turn around *instead of* moving on, so as to remain in that square for a second turn, this time facing leftwards. This means that after 127 chimes, everyone ends up right where they started. The seated guy clearly gets an audience with everyone else. Other than him, everyone is following the same path, and it is obvious that each person must pass each other one twice. Spending two turns in the square at the right end of the hallway makes it so that one of those two meetings involves walking past each other during a chime, like ships passing in the night, while the other involves sharing a square for 30 seconds. --Michael Kleber On 8/31/06, Otto Smith <otto@olympus.net> wrote:
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
-- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
In my rephrasing of Otto's solution, I should have mentioned that this method of having everyone meet everyone else is commonly used in English Country line dances, those described by the original source (John Playford, from 1651 on) as "longways for as many as will". In this context, the basic unit is a couple (two dancers), and instead of exchanging papers, a pair of couples spends one repetition of the dance engaged in some four-person choreography. At the end of the measure, the couples have switched places. Half the couples always move "up the hall" and the other half move "down the hall", except that when you fall off the top or bottom of the line, you may (depending on the parity of the number of couples dancing) have to sit out one round before coming back in going the other way. I don't know of a 17th c. source for the observation that the result is each couple dancing with each other one, but I have no doubt that the observation was made. I'll ask a friend who might know. --Michael Kleber On 9/1/06, Michael Kleber <michael.kleber@gmail.com> wrote:
Otto's answer is perfectly correct and certainly the simplest possible answer by any measure, but I'm afraid his mail may be misunderstood, so I'd like to rephrase it.
The problem does not actually require an 8x8 chess board: it would be enough to have a 64-square-long hallway, in which each square is adjacent to only two others, and the end squares to only one. (Clearly this solves the original problem, since you can make a chessboard into such a hallway by setting up rope dividers like they do at airport check-in lines, making the people walk boustrophedon-style.)
Arrange your 128 convention-goers in the hallway with two on each square, one facing right and one facing left. Except that one poor attendee broke his leg running to make his flight, so he gets to sit in the square all the way at the left end of the hallway, and doesn't move during the entire process.
Exchange papers with the person in your square, and then at each clock chime, move one square forewards. The person who enters the square at the left edge should exchange papers with the seated guy and turn around immediately, ready to move right next. The rightwards-facing person entering the square on the right edge should turn exchange papers and then turn around *instead of* moving on, so as to remain in that square for a second turn, this time facing leftwards. This means that after 127 chimes, everyone ends up right where they started.
The seated guy clearly gets an audience with everyone else. Other than him, everyone is following the same path, and it is obvious that each person must pass each other one twice. Spending two turns in the square at the right end of the hallway makes it so that one of those two meetings involves walking past each other during a chime, like ships passing in the night, while the other involves sharing a square for 30 seconds.
--Michael Kleber
On 8/31/06, Otto Smith <otto@olympus.net> wrote:
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
-- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
-- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
In my rephrasing of Otto's solution, I should have mentioned that this method of having everyone meet everyone else is commonly used in English Country line dances, those described by the original source (John Playford, from 1651 on) as "longways for as many as will". ... I don't know of a 17th c. source for the observation that the result is each couple dancing with each other one, but I have no doubt that the observation was made. I'll ask a friend who might know.
In another context, it's more or less equivalent to a famous algorithm for testing whether a linked list is "proper" or whether it has a loop; or, equivalently, for testing whether an iteration is eventually periodic: you have a "tortoise" moving forward on alternate steps and a "hare" moving forward every step. (Or: a "tortoise" moving one step at a time and a "hare" moving two steps at a time.) Its soundness depends on the fact that if there's a cycle then every pair of elements will eventually get checked against one another, which is exactly the property required here. -- g
Here's a nearly optimal solution. It minimizes the total distance walked by all people. All moves are to an orthogonally adjacent cell. One person does not move at all; everyone else moves either half the time, or once more than half the time. The orderliness is very high. I'm going to reformulate the problem in terms in 2n people moving through a series of n cells arranged in a circle. The original problem can be translated into these terms by choosing a Hamiltonian cycle. Choose a nice, symmetric one to maximize orderliness. Designate one person as the "Guru", who does not move. In each round, each person moves if they did not move the previous round; and the person with the Guru also moves. (In the first round, arbitrarily choose who will move in each room other than the Guru's.) On even numbered rounds, the people who are moving move clockwise; on odd numbered rounds, those moving move counter-clockwise. That's it. Note that each person moves in the same direction each time until meeting the Guru, at which point they turn around and move the other way for the remaining time. Franklin T. Adams-Watters P.S. This works particularly well when there is an obvious choice to be the Guru. Otherwise there might be some hard feelings. -----Original Message----- From: ed@mathpuzzle.com 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 ________________________________________________________________________ Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading spam and email virus protection.
participants (13)
-
Andrew Trevorrow -
Christian Boyer -
dasimov＠earthlink.net -
David Wolfe -
Ed Pegg Jr -
franktaw＠netscape.net -
Fred lunnon -
Gareth McCaughan -
Gary McGuire -
Michael Kleber -
Otto Smith -
Richard Guy -
Schroeppel, Richard