[math-fun] round robin
Hi Funsters, Surely this is well known, but somehow not to me. How do you arrange round robin tournament pairings? I actually needed to do it for six teams, and after a little doodling I came up with a pretty symmetric- looking pairing scheme. Numbering points in cyclic order, you pair 1-2 3-4 5-6 and its (one) cyclic shift, and pair 1-4 2-6 3-5 and its (two) cyclic shifts. The first two match each person with the two sitting on either side of them, and the last three match each person with their antipode and antipode's neighbors. Is it always possible to do this? (Where "this" is a set of pairings that's invariant under cyclic shifts.) For an odd number of people, I can certainly come up with one. Number the people from -n to n, and have each k play -k, with 0 sitting out. This plus its cyclic shifts (just adding mod n) do the job, and it's easy to see why -- draw the people in order in a circle, and each round's pairings are a full family of parallel lines. For any even number of players, you can run the above scheme, with one distinguished person playing againt the guy who would have sat out above. But I don't like singling someone out like that. (Though I guess you can still draw asymmetric-looking picture of it, by having the distinguished person sitting in the middle of the circle.) But is there always a way that's as symmetric as the 6-person example? And of course there are the counting questions: in how many different ways (modulo renaming the players, of course!) can you pair people up, both in general and with the symmetry requirement. I looked in the EIS for round-robin and didn't get any answers. Okay, now you can all tell me how well-known all this is. --Michael Kleber kleber@brandeis.edu
At 11:16 AM 9/15/2003, Michael Kleber wrote:
Hi Funsters,
Surely this is well known, but somehow not to me. How do you arrange round robin tournament pairings?
If you don't do it right, you can get in a situation where a round can't be done. Here is a way, I'll illustrate with 5 teams: 1 stays in place and 2, 3, 4... follow each other. 1 - 2 6 - 3 5 - 4 1 - 3 2 - 4 6 - 5 1 - 4 3 - 5 2 - 6 1 - 5 4 - 6 3 - 2 1 - 6 5 - 2 4 - 3
Oops, another math criminal on the loose, from the LA Times this morning. If someone from the LAPD or the FBI recognized "Euler's Theorem", then I'm pretty impressed with them! (Back in the 1980's, there was an article about the "art detective" on the LAPD who "knew instantly that a piece was a fake, because the original was hanging in the Louvre" -- we were all impressed.) The LA Times article declined to elaborate on what "Euler's Theorem" said, or what its significance was. http://www.latimes.com/news/local/la-me-hummer18sep18,1,5051975.story?coll=l... Man Claims Role in SUV Firebombings A self-described member of the Earth Liberation Front says he took part in Hummer vandalism By Jessica Garrison, Jia-Rui Chong and Greg Krikorian, Times Staff Writers A man claiming membership in the Earth Liberation Front has told The Times that he helped firebomb a San Gabriel Valley car dealership and vandalize three others last month and said the Pomona man arrested by the FBI last week had nothing to do with the crimes. Communicating via three e-mails and in two telephone interviews over the last three days, the man provided details of the attack that authorities said were known only by investigators and those involved in the incidents. He refused to give his name, say where he lives or agree to be interviewed in person. .. He described himself as a high school dropout with a passion for math as well as Greek and Roman history. He gave his age as between 20 and 25. .. Law enforcement sources, however, said details of the attacks match previously unreported evidence. Details obtained from the man in the telephone interviews include: "A math formula Euler's Theorem was spray painted on one of the SUVs as a way of distinguishing the participants' work. "We thought it would be nice to have something a little kooky just in case this happened," he said, adding that he finds the formula "beautiful." .. "I did it," the caller said Tuesday night. He claimed he was calling from a pay phone in Los Angeles County and identified himself as Tony Marsden, but said that is not his real name. .. The caller said he was not alarmed when he later learned that he had been videotaped. "You wouldn't recognize me," he said, adding that he has since cut his hair.
The LA Times article declined to elaborate on what "Euler's Theorem" said, or what its significance was. ... "A math formula Euler's Theorem was spray painted on one of the SUVs as a way of distinguishing the participants' work. "We thought it would be nice to have something a little kooky just in case this happened," he said, adding that he finds the formula "beautiful."
From context, I'd guess e^(i pi) = -1. --Michael Kleber kleber@brandeis.edu
Well, the first reference Google turned up is considerably more obscure (by LATimes standards). I'm trying to find an LAPD/FBI person who knows what Euler's totient function is! BTW, I've asked one of my friends, who is an editor at the LATimes, to find out for me what the theorem really was, and how they recognized it. http://primes.utm.edu/glossary/page.php?sort=EulersTheorem Euler's Theorem states that if gcd(a,n) = 1, then a^phi(n) = 1 (mod n). Here phi(n) is Euler's totient function: the number of integers in {1, 2, . . ., n-1} which are relatively prime to n. When n is a prime, this theorem is just Fermat's little theorem. ---- At 12:11 PM 9/18/03 -0400, Michael Kleber wrote:
The LA Times article declined to elaborate on what "Euler's Theorem" said, or what its significance was. ... "A math formula Euler's Theorem was spray painted on one of the SUVs as a way of distinguishing the participants' work. "We thought it would be nice to have something a little kooky just in case this happened," he said, adding that he finds the formula "beautiful."
From context, I'd guess e^(i pi) = -1.
--Michael Kleber kleber@brandeis.edu
The article never says that the FBI or LA PD recognized Euler's theorem. The arson could've explained it in some of his emails or phone calls. Gershon Bialer ----- Original Message ----- From: "Henry Baker" <hbaker1@pipeline.com> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Thursday, September 18, 2003 3:23 PM Subject: Re: [math-fun] Mathematical criminals & "Euler's Theorem"
Well, the first reference Google turned up is considerably more obscure (by LATimes standards).
I'm trying to find an LAPD/FBI person who knows what Euler's totient function is!
BTW, I've asked one of my friends, who is an editor at the LATimes, to find out for me what the theorem really was, and how they recognized it.
http://primes.utm.edu/glossary/page.php?sort=EulersTheorem
Euler's Theorem states that if gcd(a,n) = 1, then a^phi(n) = 1 (mod n). Here phi(n) is Euler's totient function: the number of integers in {1, 2, . . ., n-1} which are relatively prime to n. When n is a prime, this theorem is just Fermat's little theorem. ----
At 12:11 PM 9/18/03 -0400, Michael Kleber wrote:
The LA Times article declined to elaborate on what "Euler's Theorem" said, or what its significance was. ... "A math formula Euler's Theorem was spray painted on one of the SUVs as a way of distinguishing the participants' work. "We thought it would be nice to have something a little kooky just in case this happened," he said, adding that he finds the formula "beautiful."
From context, I'd guess e^(i pi) = -1.
--Michael Kleber kleber@brandeis.edu
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
At 12:11 PM 9/18/03 -0400, you wrote:
The LA Times article declined to elaborate on what "Euler's Theorem" said,...
From context, I'd guess e^(i pi) = -1.
i think that's a special case of de moivre's theorem. http://scholar.hw.ac.uk/site/maths/topic17.asp?outline= --- ray tayek http://tayek.com/ actively seeking mentoring or telecommuting work vice chair orange county java users group http://www.ocjug.org/ hate spam? http://samspade.org/ssw/
It occurred to me in retrospect that the constant function f(math statement) -> "Euler's Theorem" is probably statistically better than almost any other such constant function, given that Euler did so much (including much that doesn't have his name attached). So perhaps the LAPD and the FBI have this as a usual heuristic... At 08:57 AM 9/18/03 -0700, Henry Baker wrote:
If someone from the LAPD or the FBI recognized "Euler's Theorem", then I'm pretty impressed with them!
It occurred to me in retrospect that the constant function
f(math statement) -> "Euler's Theorem"
is probably statistically better than almost any other such constant function, given that Euler did so much (including much that doesn't have his name attached).
"Everything in mathematics is named after the second person to discover it, becuase you can't call *everything* `Euler's Theorem.'" I no longer recall whom I first heard use this line... --Michael Kleber kleber@brandeis.edu
I think they're called one factorizations Yes K_2n always has a one-factorization, with 2n-1 "factors", that's a folk theorem. I'm not sure about cyclic ones There's a notion of orthogonality between one factors---the orthogonality property is that they should have at most one edge in common. below, Stuff I copied from a 1985 paper by dinitz/wallis I just found: orthogonal one-factorizations of complete graphs correspond to "room squares" just like orthogonal one factorizations of bipartite graphs corrspond to latin squares For Michael's case, k_6, it admits fifteen one factors and six one-factorizations; each factor lies in exactly two factorizations and any two factorizations have exactly one factor in common; the six factorizations are isomorphic. So there is one factorization up to isomorphism, so no pairs of orthogonal factorizations, up to order 6. I think there's a relationship to the outer automorphism of K_6? k_8 has six non-iso one factorizations, k_10 has 396 and four mutually orthogonal ones it's known that the # of mutually orthogonal ones goes to infinity Thane Plambeck 650 321 4884 office 650 323 4928 fax http://www.qxmail.com/ehome.htm ----- Original Message ----- From: "Michael Kleber" <kleber@brandeis.edu> To: <math-fun@mailman.xmission.com> Sent: Monday, September 15, 2003 8:16 AM Subject: [math-fun] round robin
Hi Funsters,
Surely this is well known, but somehow not to me. How do you arrange round robin tournament pairings?
I actually needed to do it for six teams, and after a little doodling I came up with a pretty symmetric- looking pairing scheme. Numbering points in cyclic order, you pair 1-2 3-4 5-6 and its (one) cyclic shift, and pair 1-4 2-6 3-5 and its (two) cyclic shifts. The first two match each person with the two sitting on either side of them, and the last three match each person with their antipode and antipode's neighbors.
Is it always possible to do this? (Where "this" is a set of pairings that's invariant under cyclic shifts.)
For an odd number of people, I can certainly come up with one. Number the people from -n to n, and have each k play -k, with 0 sitting out. This plus its cyclic shifts (just adding mod n) do the job, and it's easy to see why -- draw the people in order in a circle, and each round's pairings are a full family of parallel lines.
For any even number of players, you can run the above scheme, with one distinguished person playing againt the guy who would have sat out above. But I don't like singling someone out like that. (Though I guess you can still draw asymmetric-looking picture of it, by having the distinguished person sitting in the middle of the circle.) But is there always a way that's as symmetric as the 6-person example?
And of course there are the counting questions: in how many different ways (modulo renaming the players, of course!) can you pair people up, both in general and with the symmetry requirement. I looked in the EIS for round-robin and didn't get any answers.
Okay, now you can all tell me how well-known all this is.
--Michael Kleber kleber@brandeis.edu
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Monday, September 15, 2003, at 12:05 PM, Thane Plambeck wrote:
I think they're called one factorizations
Yes K_2n always has a one-factorization, with 2n-1 "factors", that's a folk theorem. I'm not sure about cyclic ones
Ah, thank you Thane. Of course -- I knew the definition of k-factorizations, but it didn't occur to me to look things up that way. I now find: --------- Hartman, Alan; Rosa, Alexander Cyclic one-factorization of the complete graph. European J. Combin. 6 (1985), no. 1, 45--48. It is shown that the complete graph $K_n$ has a cyclic 1-factorization if and only if $n$ is even and $n\neq2^t, t\geq3$. Further, the number of cyclic 1-factorizations of $K_n$ for $n\leq16$ is determined. --------- I assume that a "cyclic 1-factorization" is the symmetry I was asking about. Since my first email, I noticed that the method I used for n=6 generalizes to any n=2*odd, but I haven't had the time to think about other cases. That still leaves the counting problem, which I haven't thought about at all. Maybe tomorrow I'll grab a copy of the above paper and see what they did up to n=16. (NJAS fodder, I'm sure...) --Michael Kleber kleber@brandeis.edu
It's well known to those who well know it that you can put the players, 0 at the centre, and 1, ... ,2n-1 at the vertices of a regular (2n-1)-gon. Pair player i with player 2n-i and 0 with n [i.e. a radius and n-1 parallel chords]. Now rotate these n lines as a rigid conguration about the centre, giving n rounds. For an odd number of players, leave out 0 and let n have a bye. In practice this is implemented with 2n-1 unit cubes in a 2 x n box. R. On Mon, 15 Sep 2003, Michael Kleber wrote:
On Monday, September 15, 2003, at 12:05 PM, Thane Plambeck wrote:
I think they're called one factorizations
Yes K_2n always has a one-factorization, with 2n-1 "factors", that's a folk theorem. I'm not sure about cyclic ones
Ah, thank you Thane. Of course -- I knew the definition of k-factorizations, but it didn't occur to me to look things up that way. I now find:
--------- Hartman, Alan; Rosa, Alexander Cyclic one-factorization of the complete graph. European J. Combin. 6 (1985), no. 1, 45--48.
It is shown that the complete graph $K_n$ has a cyclic 1-factorization if and only if $n$ is even and $n\neq2^t, t\geq3$. Further, the number of cyclic 1-factorizations of $K_n$ for $n\leq16$ is determined. ---------
I assume that a "cyclic 1-factorization" is the symmetry I was asking about.
Since my first email, I noticed that the method I used for n=6 generalizes to any n=2*odd, but I haven't had the time to think about other cases.
That still leaves the counting problem, which I haven't thought about at all. Maybe tomorrow I'll grab a copy of the above paper and see what they did up to n=16. (NJAS fodder, I'm sure...)
--Michael Kleber kleber@brandeis.edu
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Monday, September 15, 2003, at 02:51 PM, Richard Guy wrote:
It's well known to those who well know it that you can put the players, 0 at the centre, and 1, ... ,2n-1 at the vertices of a regular (2n-1)-gon. Pair player i with player 2n-i and 0 with n [i.e. a radius and n-1 parallel chords]. Now rotate these n lines as a rigid conguration about the centre, giving n rounds.
Yes, I didn't think I was the first to come up with that :-). But let me stress that I had been hoping for more symmetry: this scheme has a distinguished player Oh, and to preseve NJAS's honor, let me note that the EIS contains the counts if you leave off the symmetry part of my question: ID Number: A000474 Sequence: 1,1,1,6,396,526915620 Name: Non-isomorphic 1-factorizations of K_{2n}. and ID Number: A000438 Sequence: 1,1,6,6240,1225566720,252282619805368320 Name: 1-factorizations of K_{2n}. Extension: For K_14 the answer is approx 9.8 x 10^28, for K_16 1.48 x 10^44 and for K_18 1.52 x 10^63. - Dinitz et al. both with references: CRC Handbook of Combinatorial Designs (see pages 655, 720-723). Dinitz, Jeffrey H.; Garnick, David K.; McKay, Brendan D.; There are 526,915,620 nonisomorphic one-factorizations of K_{12}. J. Combin. Des. 2 (1994), no. 4, 273-285. W. D. Wallis, 1-Factorizations of complete graphs, pp. 593-631 in J. H. Dinitz and D R. Stinson, Contemporary Design Theory, Wiley, 1992. --Michael Kleber kleber@brandeis.edu
If you want more symmetry, put them at the vertices of a regular 2n-gon and pair i with 2n-1-i, giving n parallel chords, which rotate much as before. For an odd number, 0 doesn't get to play -- his opponent having the bye. In fact, the `box' description is really for this method. R. On Mon, 15 Sep 2003, Michael Kleber wrote:
On Monday, September 15, 2003, at 02:51 PM, Richard Guy wrote:
It's well known to those who well know it that you can put the players, 0 at the centre, and 1, ... ,2n-1 at the vertices of a regular (2n-1)-gon. Pair player i with player 2n-i and 0 with n [i.e. a radius and n-1 parallel chords]. Now rotate these n lines as a rigid conguration about the centre, giving n rounds.
Yes, I didn't think I was the first to come up with that :-). But let me stress that I had been hoping for more symmetry: this scheme has a distinguished player
Oh, and to preseve NJAS's honor, let me note that the EIS contains the counts if you leave off the symmetry part of my question:
ID Number: A000474 Sequence: 1,1,1,6,396,526915620 Name: Non-isomorphic 1-factorizations of K_{2n}.
and
ID Number: A000438 Sequence: 1,1,6,6240,1225566720,252282619805368320 Name: 1-factorizations of K_{2n}. Extension: For K_14 the answer is approx 9.8 x 10^28, for K_16 1.48 x 10^44 and for K_18 1.52 x 10^63. - Dinitz et al.
both with references:
CRC Handbook of Combinatorial Designs (see pages 655, 720-723). Dinitz, Jeffrey H.; Garnick, David K.; McKay, Brendan D.; There are 526,915,620 nonisomorphic one-factorizations of K_{12}. J. Combin. Des. 2 (1994), no. 4, 273-285. W. D. Wallis, 1-Factorizations of complete graphs, pp. 593-631 in J. H. Dinitz and D R. Stinson, Contemporary Design Theory, Wiley, 1992.
--Michael Kleber kleber@brandeis.edu
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Monday, September 15, 2003, at 03:52 pm, Richard Guy wrote:
If you want more symmetry, put them at the vertices of a regular 2n-gon and pair i with 2n-1-i, giving n parallel chords, which rotate much as before. For an odd number, 0 doesn't get to play -- his opponent having the bye.
For 2n people, this always pairs players of opposite parody (no matter how you rotate it). So the rotations of this only get you to play half of the people in the group. The simple fix is to also take the pairings of i with 2n-i, except that this leaves out 0 and n. Well, it pairs them each with themselves. You could give both of them byes, and get a nice symmetric tournament -- but one that that takes a full 2n rounds, instead of the 2n-1 that you get if everyone plays every time. --Michael Kleber kleber@brandeis.edu
I've just heard that 32% of accidents are caused by people who've been drinking. This means that 68% are caused by people who haven't been. So it's clear that the chance of your causing an accident if you've been drinking is only 8/17 of the chance if you haven't. R.
I've just heard that 32% of accidents are caused by people who've been drinking. This means that 68% are caused by people who haven't been. So it's clear that the chance of your causing an accident if you've been drinking is only 8/17 of the chance if you haven't.
This ignores the likelihood that few drivers are drinking. So it's sloppy thinking, but it might be true anyway, because the civilized drinkers don't drive, and thereby don't cause accidents. Let's get the odds down to 0/17. (Dr. Guy: thank you for posting instead of driving in that state. :-) -- Don Reble djr@nk.ca
At 07:24 PM 9/15/2003, Don Reble wrote:
I've just heard that 32% of accidents are caused by people who've been drinking. This means that 68% are caused by people who haven't been. So it's clear that the chance of your causing an accident if you've been drinking is only 8/17 of the chance if you haven't.
This ignores the likelihood that few drivers are drinking. So it's sloppy thinking, but it might be true anyway, because the civilized drinkers don't drive, and thereby don't cause accidents. Let's get the odds down to 0/17.
I've read that about 2% of the drivers on the road are drinking. So 2% of the drivers are causing 32% of the accidents.
Additionally, do we distinguish between the boolean short-circuit analysis of drinking and driving, and driving and drinking? Jon Perry perry@globalnet.co.uk http://www.users.globalnet.co.uk/~perry/maths/ http://www.users.globalnet.co.uk/~perry/DIVMenu/ BrainBench MVP for HTML and JavaScript http://www.brainbench.com -----Original Message----- From: math-fun-bounces@mailman.xmission.com [mailto:math-fun-bounces@mailman.xmission.com]On Behalf Of Don Reble Sent: 16 September 2003 00:25 To: math-fun Subject: Re: [math-fun] Drinking and driving
I've just heard that 32% of accidents are caused by people who've been drinking. This means that 68% are caused by people who haven't been. So it's clear that the chance of your causing an accident if you've been drinking is only 8/17 of the chance if you haven't.
This ignores the likelihood that few drivers are drinking. So it's sloppy thinking, but it might be true anyway, because the civilized drinkers don't drive, and thereby don't cause accidents. Let's get the odds down to 0/17. (Dr. Guy: thank you for posting instead of driving in that state. :-) -- Don Reble djr@nk.ca _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (9)
-
Don Reble -
Gershon Bialer -
Henry Baker -
Jon Perry -
Jud McCranie -
Michael Kleber -
Ray Tayek -
Richard Guy -
Thane Plambeck