# Math: Field day permutations **URL:** \ **Category:** Factual Questions\ **Created:** [May 29, 2019, 9:00pm UTC](https://boards.straightdope.com/t/math-field-day-permutations/834734 "2019-05-29T21:00:46Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [May 29, 2019, 9:00pm UTC](https://boards.straightdope.com/t/math-field-day-permutations/834734/1 "2019-05-29T21:00:46Z")
A school is planning a field day. There will be _n_ different activities (in this specific case, _n_ = 10), over the course of _n_ timeslots, with 2_n_ teams competing in them. The goals are: 1: Every team participates in every activity 2: No team is in two different activities at the same time. 3: At every timeslot, every activity has exactly two teams participating in it. 4: No pair of teams will ever compete against each other twice. The challenge, of course, is coming up with a schedule for each of the teams that makes this happen. For any odd _n_, this is easy: Put the activities in a circle, with the teams divided into an inner circle and an outer circle. At the end of every timeslot, the inner circle rotates one step clockwise, and the outer circle rotates one step counterclockwise. But for even _n_ (like, say, 10), this fails condition 4: After _n_/2 steps, everyone will be facing teams they’ve already faced. And, in fact, I suspect that it’s impossible for even _n_. But I’ve so far been unable to either prove this, or to find a counterexample. ---
**Author:** ![OldGuy](https://avatars.discourse-cdn.com/v4/letter/o/3bc359/32.png) [@OldGuy](https://boards.straightdope.com/u/OldGuy)\ **Post date:** [May 29, 2019, 9:14pm UTC](https://boards.straightdope.com/t/math-field-day-permutations/834734/2 "2019-05-29T21:14:16Z")
> [@Chronos](#): > > But I’ve so far been unable to either prove this, or to find a counterexample. I’m pretty sure you’re correct. This is a standard problem for a duplicate bridge tournament. If there were a solution, I’d think someone would have found it, but I’ve never seen such. And your solution for N odd is essentially what is called a Mitchell movement in Duplicate. But one time sits while the sets of cars to be played rotate counter to the moving pairs. ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [May 29, 2019, 10:20pm UTC](https://boards.straightdope.com/t/math-field-day-permutations/834734/3 "2019-05-29T22:20:22Z")
I don’t get it. Say n = 4. What’s wrong with the schedule 1 2 3 4 5 6 7 8 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1 6 5 8 7 n = 10 should be fine, too. ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [May 29, 2019, 10:49pm UTC](https://boards.straightdope.com/t/math-field-day-permutations/834734/4 "2019-05-29T22:49:05Z")
There is an explicit example with n=10 in _The Art of Computer Programming,_ Volume 4, in the part on Combinatorial Searching. Naturally all this kind of stuff is in Knuth. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [May 29, 2019, 11:20pm UTC](https://boards.straightdope.com/t/math-field-day-permutations/834734/5 "2019-05-29T23:20:15Z")
OK, there we go, counterexamples. Is the n=10 case too big to copy out? Or at least, what does Knuth call this problem, so I might search it out? ---
**Author:** ![glowacks](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/glowacks/32/5548_2.png) [@glowacks](https://boards.straightdope.com/u/glowacks)\ **Post date:** [May 29, 2019, 11:28pm UTC](https://boards.straightdope.com/t/math-field-day-permutations/834734/6 "2019-05-29T23:28:16Z")
So if you want to have the same movement every period, you would have one set of teams move k events and another set of teams move p events. After x movements the teams that started at event 0 (or n) would be at events kx and px, so we would need to show that there exists some p and k such that kx = px mod n only has solution x = 0 mod n for n even. The problem with this is that x = n/2 is always a solution to this when n is even, because that means k and p can be written 2m + 1, so k \* n /2 = nm + n/2 = n/2 mod n which is independent of m. Are there irregular movements that work? Apparently yes. But regular ones will not work. ---
**Author:** ![glowacks](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/glowacks/32/5548_2.png) [@glowacks](https://boards.straightdope.com/u/glowacks)\ **Post date:** [May 29, 2019, 11:35pm UTC](https://boards.straightdope.com/t/math-field-day-permutations/834734/7 "2019-05-29T23:35:09Z")
> [@glowacks](#): > > So if you want to have the same movement every period, you would have one set of teams move k events and another set of teams move p events. After x movements the teams that started at event 0 (or n) would be at events kx and px, so we would need to show that there exists some p and k such that kx = px mod n only has solution x = 0 mod n for n even. The problem with this is that x = n/2 is always a solution to this when n is even, because that means k and p can be written 2m + 1, so k \* n /2 = nm + n/2 = n/2 mod n which is independent of m. > > Are there irregular movements that work? Apparently yes. But regular ones will not work. I failed to mention the obvious that k and p have to be relatively prime with n in order for the space to be filled, so k and p must be odd when n is even. ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [May 29, 2019, 11:38pm UTC](https://boards.straightdope.com/t/math-field-day-permutations/834734/8 "2019-05-29T23:38:53Z")
Eh, I’m just lazy. The example occurs in the discussion on Graeco-Latin squares. In your terms, divide the 20 teams into an “inner circle” and an “outer circle” and number the teams in each circle from 0 to 9. Then the two matrices from Knuth are: 0123456789 1832547690 2956308471 3709861524 4675290813 5094783162 6547132908 7418029356 9281674035 and 0285947361 1749365028 2564870193 3690458217 4817536902 5178029436 6902713845 7351204689 8023691754 9436182570 It’s near the beginning of Chapter 7 (Combinatorial searching) if you want to check in case I made some typos copying it in. ---
**Author:** ![glowacks](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/glowacks/32/5548_2.png) [@glowacks](https://boards.straightdope.com/u/glowacks)\ **Post date:** [May 29, 2019, 11:44pm UTC](https://boards.straightdope.com/t/math-field-day-permutations/834734/9 "2019-05-29T23:44:14Z")
> [@DPRK](#): > > There is an explicit example with n=10 in _The Art of Computer Programming,_ Volume 4, in the part on Combinatorial Searching. Naturally all this kind of stuff is in Knuth. I take it then that finding a working example is not trivial, and requires using a computer to search every combination of possible permutations for one that satisfies the criteria. I don’t think writing such a program would really be all that difficult, and given the speeds of modern computers I don’t think run time would be much of an issue. It would take me a while to do because I’m rusty at coding, but I think I’d figure it out eventually. The question is does Chronos have that time… ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [May 29, 2019, 11:49pm UTC](https://boards.straightdope.com/t/math-field-day-permutations/834734/10 "2019-05-29T23:49:48Z")
If I’m reading those matrices correctly: In round 1, team 0a faces team 0b in event 1, team 1a faces team 2b in event 2, team 2a faces team 8b in event 3, etc. and then in round 2, team 1a faces 1b in event 1, team 8a faces team 7b in event 2, 3a faces 4b in event 3, etc. Is that correct? Wait, either I’m not reading it correctly, or that’s not a solution: By that interpretation, teams 5a and 5b face each other both in event 1, round 6, and in event 9, round 9. ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [May 30, 2019, 12:06am UTC](https://boards.straightdope.com/t/math-field-day-permutations/834734/11 "2019-05-30T00:06:06Z")
> [@glowacks](#): > > I take it then that finding a working example is not trivial, and requires using a computer to search every combination of possible permutations for one that satisfies the criteria. I don’t think writing such a program would really be all that difficult, and given the speeds of modern computers I don’t think run time would be much of an issue. It would take me a while to do because I’m rusty at coding, but I think I’d figure it out eventually. The question is does Chronos have that time… That’s exactly the subject of Knuth’s book: in the introduction he explains how an appropriate algorithm reduces the running time from searching every combination (which is what a couple of guys tried to do in 1959, and ended up giving up after five hours since they estimated their program would take 4.8 x 10[sup]11[/sup] hours to run) by 12 orders of magnitude. > [@Knuth](#): > > The moral of this story is clear: Combinatorial problems might confront us with a huge universe of possibilities, yet we shouldn’t give up too easily. A single good idea can reduce the amount of computation by many orders of magnitude. ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [May 30, 2019, 12:10am UTC](https://boards.straightdope.com/t/math-field-day-permutations/834734/12 "2019-05-30T00:10:51Z")
> [@Chronos](#): > > If I’m reading those matrices correctly: In round 1, team 0a faces team 0b in event 1, team 1a faces team 2b in event 2, team 2a faces team 8b in event 3, etc. and then in round 2, team 1a faces 1b in event 1, team 8a faces team 7b in event 2, 3a faces 4b in event 3, etc. Is that correct? > > Wait, either I’m not reading it correctly, or that’s not a solution: By that interpretation, teams 5a and 5b face each other both in event 1, round 6, and in event 9, round 9. That’s because I somehow deleted a row of the first matrix (you can tell because the first column has 0 through 9 in order): row 9 is: 8360915247 so in event 9, round 9 we should have 4a versus 5b ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [May 30, 2019, 12:13am UTC](https://boards.straightdope.com/t/math-field-day-permutations/834734/13 "2019-05-30T00:13:36Z")
take 2: 0 1 2 3 4 5 6 7 8 9 1 8 3 2 5 4 7 6 9 0 2 9 5 6 3 0 8 4 7 1 3 7 0 9 8 6 1 5 2 4 4 6 7 5 2 9 0 8 1 3 5 0 9 4 7 8 3 1 6 2 6 5 4 7 1 3 2 9 0 8 7 4 1 8 0 2 9 3 5 6 8 3 6 0 9 1 5 2 4 7 9 2 8 1 6 7 4 0 3 5 and 0 2 8 5 9 4 7 3 6 1 1 7 4 9 3 6 5 0 2 8 2 5 6 4 8 7 0 1 9 3 3 6 9 0 4 5 8 2 1 7 4 8 1 7 5 3 6 9 0 2 5 1 7 8 0 2 9 4 3 6 6 9 0 2 7 1 3 8 4 5 7 3 5 1 2 0 4 6 8 9 8 0 2 3 6 9 1 7 5 4 9 4 3 6 1 8 2 5 7 0 ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [May 30, 2019, 2:21am UTC](https://boards.straightdope.com/t/math-field-day-permutations/834734/14 "2019-05-30T02:21:03Z")
OK, that about wraps it up for the concrete problem in question (I, my sister, and my nephew’s school thank you, **DPRK** ), but I’m still curious about the general problem. Is it always possible, for arbitrary _n_? Is it still always possible if we add the additional condition of two “circles”, such that a team from one circle is always playing a team from the other? EDIT: Of course it’s not always possible, because n=2 definitely doesn’t work. So what I mean to ask is, under what conditions is it possible? ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [May 30, 2019, 2:26am UTC](https://boards.straightdope.com/t/math-field-day-permutations/834734/15 "2019-05-30T02:26:07Z")
Oh, and I somehow missed **glowaks** ’ posts before, about the relatively-prime movements. Yup, I had already considered that, and rejected it for basically the same reason, which was part of why I suspected that no solution existed. It comes of my physics background, I suppose: I’m so used to looking for symmetry in problems, that I’m blind to an asymmetric solution. ---
**Author:** ![MikeS](https://avatars.discourse-cdn.com/v4/letter/m/919ad9/32.png) [@MikeS](https://boards.straightdope.com/u/MikeS)\ **Post date:** [May 30, 2019, 11:47am UTC](https://boards.straightdope.com/t/math-field-day-permutations/834734/16 "2019-05-30T11:47:50Z")
> [@Chronos](#): > > Is it always possible, for arbitrary _n_? Is it still always possible if we add the additional condition of two “circles”, such that a team from one circle is always playing a team from the other? > > EDIT: Of course it’s not always possible, because n=2 definitely doesn’t work. So what I mean to ask is, under what conditions is it possible? It’s possible for all n except n = 2 and n = 6; see the Wiki article on [Graeco-Latin squares.](https://en.wikipedia.org/wiki/Graeco-Latin_square) The fact that n = 6 is impossible was conjectured by Euler in the [thirty-six officers problem,](https://en.wikipedia.org/wiki/Thirty-six_officers_problem) but it wasn’t actually proven until 1901. Euler also conjectured that it was impossible for all n that are equal to 2 modulo 4; but in 1959 it was proved that solutions exist for all n \> 6, including the n = 10 case you’re interested in. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [May 30, 2019, 1:44pm UTC](https://boards.straightdope.com/t/math-field-day-permutations/834734/17 "2019-05-30T13:44:26Z")
OK, now I feel a _lot_ better, that even Euler thought it was impossible. ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [June 1, 2019, 12:04pm UTC](https://boards.straightdope.com/t/math-field-day-permutations/834734/18 "2019-06-01T12:04:13Z")
Sorry it took me a while to return to this thread. The linked article on Graeco-Latin squares, which apply to this problem, pretty much sums up the history as recounted by **MikeS**. One thing it does not explicitly say is that Parker’s finding such a square of order 10 took both Euler’s original insight _and_ nevertheless on the order of 10[sup]8[/sup] calculations. Now, it remains to point out that any solution to the problem as formulated by **Chronos** , for any n, always has two independent “circles” of teams, and therefore reduces to a mutually orthogonal Latin-square design. This seems relatively straightforward enough, but am I missing something where it is completely obvious from the get-go? ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [June 1, 2019, 2:07pm UTC](https://boards.straightdope.com/t/math-field-day-permutations/834734/19 "2019-06-01T14:07:25Z")
And, for instance, we know that there’s no solution for n=6 with the two circles constraint, but that wasn’t one of my original constraints. Is there a solution for my original problem for n=6? ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [June 1, 2019, 8:49pm UTC](https://boards.straightdope.com/t/math-field-day-permutations/834734/20 "2019-06-01T20:49:01Z")
Your original problem is for an H(n, 2n) Howell design, and yes, it has a solution for n = 6, e.g.: 17 28 39 4A 5B 6C 23 7C 45 89 16 AB BC 34 78 56 9A 12 5A 6B 1C 27 38 49 69 1A 2B 3C 47 58 48 59 6A 1B 2C 37 I took this example from “On Howell Designs” by Hung and Mendelsohn, which you can consult for much more information. [Next page](https://boards.straightdope.com/t/math-field-day-permutations/834734.md?page=2)