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 2n 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.
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.
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.
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.
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:
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…
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 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.
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?
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.
It’s possible for all n except n = 2 and n = 6; see the Wiki article on Graeco-Latin squares. The fact that n = 6 is impossible was conjectured by Euler in the 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.
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?
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?