Math: Field day permutations

Factual Questions
21

Well, I found one myself after about 3 hours of working in Excel, of which probably a half hour was setting up tables to show me where I made errors. For a while I was equally convinced and unconvinced that it was impossible. It seemed like there were enough degrees of freedom to move things around and there didn’t appear to be anything that kept coming up as a recurring problem, but it was just hard to get things aligned. I’ve done a lot of work on similar problems involving matching competitors with various restrictions (though nothing academic), but this was a new one. Apologies for the completely different notation and the likely mutilation of formatting once it gets posted; it’s a product of how I initially set it up to check for errors, and I probably could have done something much nicer if I had been smarter about how to do that.

A A B B C C D D E E F F
1 2 3 4 5 6 7 8 9 10 11 12
3 7 1 11 2 10 4 5 6 12 9 8
9 12 2 8 1 3 6 10 5 11 4 7
11 6 5 7 8 12 1 9 2 4 3 10
5 8 10 12 4 9 3 11 1 7 2 6
4 10 6 9 7 11 2 12 3 8 1 5

My error-checking tables claim this is a solution at least. I haven’t manually verified it.

22

Hung and Mendelsohn also give a modification of Chronos’s rotating circles method for handling even n > 2 (they don’t describe it in this rotating circles language, and indeed they describe it rather more opaquely, but luckily, I’m here to describe it more clearly, hopefully):

I’ll describe it first in the case of n which is a multiple of 4. Indeed, I’ll first describe a schedule which almost but doesn’t quite work, and then I’ll show how to patch it up:

Set up an inner circle and outer circle. At the end of every timeslot, the inner circle rotates one step clockwise, and the outer circle rotates one step counterclockwise, except two special things happen: At the halfway timeslot, when teams are about to face the same opponents as originally, have everyone in the inner circle rotate 1 extra step. And at the last timeslot, when the inner circle is now about to go back to the activities they started at, have them rotate 180 degrees extra, to the activities they missed because of our shenanigans at the halfway timeslot.

Clearly, this satisfies conditions 1 through 3 from the OP, and also it very nearly satisfies condition 4. The only problem is, now our shenanigans have resulted in the opponent pairings at the 75% of the way through timeslot matching the opponents pairings at the last timeslot.

No problem. Take the schedule this produces, and we’ll fuck with that 75% timeslot and one of the timeslots next to it (before or after, your choice, doesn’t matter; the important thing is that they’re adjacent timeslots without special case shenanigans, containing the one timeslot that ever duplicates any pairing from another), to fix things.

Take these two timeslots/rows, and also pair off activities/columns with adjacent activities (so the first and second activity are paired off, the 3rd and 4th activity are paired off, etc). Within any of these two by two cells of our schedule, things look like so:

As Bt
Br Cs

Where A, B, C, … are some inner circle teams and r, s, t, … are some outer circle teams, movement to the left is clockwise and movement to the right is counterclockwise. We will replace each of these blocks with:

AB st
rs BC

Notice that the collection of values appearing in each row stays the same, and the collection of values appearing in each column stays the same. Thus, since we already satisfied conditions 1 through 3, we will continue to do so. But now, instead of inner-circle teams facing outer-circle teams, all competition in these two timeslots is intra-circle (thus, not duplicating what happens in any other timeslots; also, each team plays its two different same-circle neighbors over these two timeslots, so these timeslots do not duplicate pairings with each other); this fixes our problem with condition 4.

After we make this modification, our schedule is perfect and we’re ready to go!

23

If n is even but not a multiple of 4, you can basically do the same thing, but the two timeslots which end up duplicating each other’s pairings are just before the halfway timeslot and just after a quarter of the way through. So you can fuck with either of them the same way to fix things (n.b.: if you choose to patch things up in this way at the just before halfway timeslot, you have to patch it up against its previous timeslot, not against its next timeslot, since its next timeslot is the halfway timeslot that has special-case logic going on).

24

Wait, sorry ignore the last post. Here are all the corrigenda on precise timeslot numbering things (where the timeslots are numbered 1 through n):

By “halfway” timeslot, I actually mean the (n/2 + 1)-th timeslot, just after halfway.

By “75% of the way through timeslot”, I mean the (3n/4)-th timeslot, which is probably what you expected anyway, but it’s not quite the same as what I meant with the halfway timeslot.

This was a dumb brainfart error; rather, the two timeslots which end up duplicating each other’s pairings when n is 2 mod 4 are the last timeslot as before, and the just after a quarter of the way timeslot, i.e. (n + 2)/4-th timeslot.

This method actually handles even n > 4. (When n = 4, different special case timeslots line up, causing issues, and accidental match issues are only exacerbated further for n = 2, of course)

25

Anyway, let’s actually illustrate this method. Take n = 6. Our teams will be A, B, C, D, E, F (rotating left as we go down), r, s, t, u, v, w (rotating right as we go down).

The semi-naive schedule is like so:

Ar Bs Ct Du Ev Fw
Bw Cr Ds Et Fu Av
Cv Dw Er Fs At Bu
Eu Fv Aw Br Cs Dt [here, just after halfway, the A, B, C… circle has taken an extra step, to avoid duplicating the original pairings]
Ft Au Bv Cw Dr Es
Ds Et Fu Av Bw Cr [here, at the very end, the A, B, C… circle has taken an extra 180 degree rotation, to hit the activities they missed just after halfway]

Everything’s cool except there are repeated pairings between the last timeslot and the 2nd timeslot; i.e., the ceiling(n/4)-th timeslot. [This is because n = 2 mod 4; if n = 0 mod 4, the repeated pairings would be between the last timeslot and the (3n/4)-th timeslot].

To patch this up, we take that 2nd timeslot and one of the timeslots next to it, let’s say the 1st one. And we fuck with them like so:

We turn

Ar Bs Ct Du Ev Fw
Bw Cr Ds Et Fu Av

Into

AB rs CD tu EF vw
rw BC st DE uw AF

Preserving the values which appear in each column and in each block of two within a row, and having each team play its two same-circle neighbors. Putting this back into our semi-naive schedule, we get the modified schedule:

AB rs CD tu EF vw
rw BC st DE uw AF
Cv Dw Er Fs At Bu
Eu Fv Aw Br Cs Dt
Ft Au Bv Cw Dr Es
Ds Et Fu Av Bw Cr

And this will do everything we want. I’ve illustrated it here for n = 6, but the same process works for n = 10. Indeed, we can now handle any n other than 2 or 4 in a fairly uniform and simple way.

[Actually, it seems like maybe things still can work for n = 4 with the same method also, despite special-case things lining up, but whatever, I’m done for today]

26

Interestingly, the almost-good-enough solution that Indistinguishable just described is what my sister and niece, working together, came up with on their own, and were going to actually implement until I got back to her with DPRK’s graeco-latin solution.

It didn’t occur to me, though, to add an epicycle to that solution, to fix the one duplicate matchup.

27

No one ever thinks to add another epicycle atop a prior epicycle! (Oh, wait, no, I guess that happens all the time…)

28

I don’t like all these inner-circle/outer-circle techniques. The teams might start to think it’s just one circle vs. another, because every team in a given circle plays every team in the other circle, and none of the teams in their own circle. We can’t have that; it’s every team for themselves! 10 teams enter; one team leaves!

Is there a solution (for any n) that fulfills not only Chronos’ original constraints, but in addition ensures that no two teams have an identical set of opponents?

29

Yeah, it turns out a solution for n = 4 is indeed similar, but not quite the same; there’s the same idea of messing with the bad row and one adjacent row at the end by preserving values in a column and setting up same-team matches. But because the bad row is necessarily a special-case row, things are different enough that when one does this, one doesn’t preserve values in each two-column block within a row. But it still works well enough. It’s similar.

30

The approach I outlined for even n > 4 ensures no two teams have a precisely identical set of opponents: each team plays within its circle precisely its two neighbors (and more than two teams from the other circle), ensuring that the mapping from teams to their sets of opponents is injective.

The “fuck with two adjacent rows (related by opposite direction one-step turns of the two circles)” step I outlined can also be applied to any schedule, preserving constraints 1 through 3, allowing us to do this for odd n just as well.

It’s sort of a just barely differentiated set of opponents, still, but it is differentiated.