Skip to content

Instantly share code, notes, and snippets.

@czlee

czlee/bp-round-robin.txt

Last active Aug 23, 2016
Embed
What would you like to do?
Enumeration of 16-team BP round robins
Allocate the first round arbitrarily, and call the rooms "A" through "D". Then
allocate the second round such that every room has one of each of A, B, C and D
(this must be true, otherwise someone's seen someone twice), and call those
rooms "1" through "4". What we have now is, without loss of generality, labels
for each team that indicate their first two rounds. In the grid below, columns
are first-round rooms, and rows are second-round rooms:
A1 B1 C1 D1
A2 B2 C2 D2
A3 B3 C3 D3
A4 B4 C4 D4
From now, in all tables, rows are rooms (not columns), and we assume without
loss of generality that A1 is in the first room, A2 in the second, and so on.
Since in every round after the first round, one of each of A, B, C and D must be
in each room, we'll just by convention put As in the first column, Bs in the
second, and so on.
Now, at some point, A1 has to face each of B2, B3 and B4, none of whom are
allowed to see each other. Without loss of generality, assume A1 faces B2 in
round 3. If A1 sees B2, only C3-D4 and D4-C3 remain, so there are only two
possibilities for the first room:
A1 B2 C3 D4
A2
A3
A4
A1 B2 C4 D3
A2
A3
A4
(Note that already, we can't "rename" teams to make these two equivalent,
because the first two rounds ensure uniqueness.)
Then A2 must see some B team that round, and there are only B1, B3 and B4:
A1 B2 C3 D4 A1 B2 C3 D4 A1 B2 C3 D4
A2 B1 A2 B3 A2 B4
A3 A3 A3
A4 A4 A4
A1 B2 C4 D3 A1 B2 C4 D3 A1 B2 C4 D3
A2 B1 A2 B3 A2 B4
A3 A3 A3
A4 A4 A4
To avoid a repeat meeting, each number (1 to 4) must appear exactly once in each
row and once in each column. That's actually enough to dictate all eight
possibilities for round 3:
A1 B2 C3 D4 A1 B2 C3 D4 A1 B2 C3 D4 A1 B2 C3 D4
A2 B1 C4 D3 A2 B1 C4 D3 A2 B3 C4 D1 A2 B4 C1 D3
A3 B4 C1 D2 A3 B4 C2 D1 A3 B4 C1 D2 A3 B1 C4 D2
A4 B3 C2 D1 A4 B3 C1 D2 A4 B1 C2 D3 A4 B3 C2 D1
A1 B2 C4 D3 A1 B2 C4 D3 A1 B2 C4 D3 A1 B2 C4 D3
A2 B1 C3 D4 A2 B1 C3 D4 A2 B3 C1 D4 A2 B4 C3 D1
A3 B4 C1 D2 A3 B4 C2 D1 A3 B4 C2 D1 A3 B1 C2 D4
A4 B3 C2 D1 A4 B3 C1 D2 A4 B1 C3 D2 A4 B3 C1 D2
Now, for round 4. At some point, A1 must see B3, so assume it's in round 4.
Since A1 has seen one of C4/D4, they must see the other in this round (otherwise
they'd see the same team twice, since they're already seeing a 3 team). It turns
out that the rounds 1 to 3 completely dictate round 4; the eight possibilities
below correspond to those above for round 3 (i.e. the first table below is what
must happen in round 4 if the first table above was round 3).
A1 B3 C4 D2 A1 B3 C4 D2 A1 B3 C4 D2 A1 B3 C4 D2
A2 B4 C3 D1 A2 B4 C3 D1 A2 B4 C1 D3 A2 B1 C3 D4
A3 B1 C2 D4 A3 B2 C1 D4 A3 B1 C2 D4 A3 B4 C2 D1
A4 B2 C1 D3 A4 B1 C2 D3 A4 B2 C3 D1 A4 B2 C1 D3
A1 B3 C2 D4 A1 B3 C2 D4 A1 B3 C2 D4 A1 B3 C2 D4
A2 B4 C1 D3 A2 B4 C1 D3 A2 B4 C3 D1 A2 B1 C4 D3
A3 B2 C4 D1 A3 B1 C4 D2 A3 B1 C4 D2 A3 B4 C1 D2
A4 B1 C3 D2 A4 B2 C3 D1 A4 B2 C1 D3 A4 B2 C3 D1
The last round, of course, is dictated by the first four.
Here are the eight tournaments. Each major row is one possible tournament;
each major column is a round.
EDIT: It turns out some of these involve teams seeing each other twice ---
entire columns, in fact. Those ones are marked, which leaves just two unique
tournaments satisfying the constraints.
A1 A2 A3 A4 A1 B1 C1 D1 A1 B2 C3 D4 A1 B3 C4 D2 A1 B4 C2 D3
B1 B2 B3 B4 A2 B2 C2 D2 A2 B1 C4 D3 A2 B4 C3 D1 A2 B3 C1 D4
C1 C2 C3 C4 A3 B3 C3 D3 A3 B4 C1 D2 A3 B1 C2 D4 A3 B2 C4 D1
D1 D2 D3 D4 A4 B4 C4 D4 A4 B3 C2 D1 A4 B2 C1 D3 A4 B1 C3 D2
A1 A2 A3 A4 A1 B1 C1 D1 A1 B2 C3 D4 A1 B3 C4 D2 A1 B4 C2 D3 x C-D conflict
B1 B2 B3 B4 A2 B2 C2 D2 A2 B1 C4 D3 A2 B4 C3 D1 A2 B3 C1 D4 x rounds 4 & 5
C1 C2 C3 C4 A3 B3 C3 D3 A3 B4 C2 D1 A3 B2 C1 D4 A3 B1 C4 D2 x B-C conflict
D1 D2 D3 D4 A4 B4 C4 D4 A4 B3 C1 D2 A4 B1 C2 D3 A4 B2 C3 D1 x rounds 3 & 5
A1 A2 A3 A4 A1 B1 C1 D1 A1 B2 C3 D4 A1 B3 C4 D2 A1 B4 C2 D3 x C-D conflict
B1 B2 B3 B4 A2 B2 C2 D2 A2 B3 C4 D1 A2 B4 C1 D3 A2 B1 C3 D4 x rounds 3 & 5
C1 C2 C3 C4 A3 B3 C3 D3 A3 B4 C1 D2 A3 B1 C2 D4 A3 B2 C4 D1 x B-C conflict
D1 D2 D3 D4 A4 B4 C4 D4 A4 B1 C2 D3 A4 B2 C3 D1 A4 B3 C1 D2 x rounds 3 & 4
A1 A2 A3 A4 A1 B1 C1 D1 A1 B2 C3 D4 A1 B3 C4 D2 A1 B4 C2 D3 x B-C conflict
B1 B2 B3 B4 A2 B2 C2 D2 A2 B4 C1 D3 A2 B1 C3 D4 A2 B3 C4 D1 x rounds 3 & 5
C1 C2 C3 C4 A3 B3 C3 D3 A3 B1 C4 D2 A3 B4 C2 D1 A3 B2 C1 D4 x C-D conflict
D1 D2 D3 D4 A4 B4 C4 D4 A4 B3 C2 D1 A4 B2 C1 D3 A4 B1 C3 D2 x rounds 3 & 4
A1 A2 A3 A4 A1 B1 C1 D1 A1 B2 C4 D3 A1 B3 C2 D4 A1 B4 C3 D2 x B-C conflict
B1 B2 B3 B4 A2 B2 C2 D2 A2 B1 C3 D4 A2 B4 C1 D3 A2 B3 C4 D1 x rounds 3 & 5
C1 C2 C3 C4 A3 B3 C3 D3 A3 B4 C1 D2 A3 B2 C4 D1 A3 B1 C2 D4 x C-D conflict
D1 D2 D3 D4 A4 B4 C4 D4 A4 B3 C2 D1 A4 B1 C3 D2 A4 B2 C1 D3 x rounds 4 & 5
A1 A2 A3 A4 A1 B1 C1 D1 A1 B2 C4 D3 A1 B3 C2 D4 A1 B4 C3 D2
B1 B2 B3 B4 A2 B2 C2 D2 A2 B1 C3 D4 A2 B4 C1 D3 A2 B3 C4 D1
C1 C2 C3 C4 A3 B3 C3 D3 A3 B4 C2 D1 A3 B1 C4 D2 A3 B2 C1 D4
D1 D2 D3 D4 A4 B4 C4 D4 A4 B3 C1 D2 A4 B2 C3 D1 A4 B1 C2 D3
A1 A2 A3 A4 A1 B1 C1 D1 A1 B2 C4 D3 A1 B3 C2 D4 A1 B4 C3 D2 x C-D conflict
B1 B2 B3 B4 A2 B2 C2 D2 A2 B3 C1 D4 A2 B4 C3 D1 A2 B1 C4 D3 x rounds 3 & 5
C1 C2 C3 C4 A3 B3 C3 D3 A3 B4 C2 D1 A3 B1 C4 D2 A3 B2 C1 D4 x B-C conflict
D1 D2 D3 D4 A4 B4 C4 D4 A4 B1 C3 D2 A4 B2 C1 D3 A4 B3 C2 D1 x rounds 4 & 5
A1 A2 A3 A4 A1 B1 C1 D1 A1 B2 C4 D3 A1 B3 C2 D4 A1 B4 C3 D2 x C-D conflict
B1 B2 B3 B4 A2 B2 C2 D2 A2 B4 C3 D1 A2 B1 C4 D3 A2 B3 C1 D4 x rounds 3 & 4
C1 C2 C3 C4 A3 B3 C3 D3 A3 B1 C2 D4 A3 B4 C1 D2 A3 B2 C4 D1 x B-C conflict
D1 D2 D3 D4 A4 B4 C4 D4 A4 B3 C1 D2 A4 B2 C3 D1 A4 B1 C2 D3 x rounds 3 & 5
So here are the two good ones:
A1 A2 A3 A4 A1 B1 C1 D1 A1 B2 C3 D4 A1 B3 C4 D2 A1 B4 C2 D3
B1 B2 B3 B4 A2 B2 C2 D2 A2 B1 C4 D3 A2 B4 C3 D1 A2 B3 C1 D4
C1 C2 C3 C4 A3 B3 C3 D3 A3 B4 C1 D2 A3 B1 C2 D4 A3 B2 C4 D1
D1 D2 D3 D4 A4 B4 C4 D4 A4 B3 C2 D1 A4 B2 C1 D3 A4 B1 C3 D2
A1 A2 A3 A4 A1 B1 C1 D1 A1 B2 C4 D3 A1 B3 C2 D4 A1 B4 C3 D2
B1 B2 B3 B4 A2 B2 C2 D2 A2 B1 C3 D4 A2 B4 C1 D3 A2 B3 C4 D1
C1 C2 C3 C4 A3 B3 C3 D3 A3 B4 C2 D1 A3 B1 C4 D2 A3 B2 C1 D4
D1 D2 D3 D4 A4 B4 C4 D4 A4 B3 C1 D2 A4 B2 C3 D1 A4 B1 C2 D3
I leave you to verify this to your satisfaction. Happy checking!
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment