4
$\begingroup$

We have a tournament in which 13 players participate, and matches are played in groups of 4 players (i.e. it's a 4-player game).

There are 13 rounds in total, each player skips one round, and the other 12 are divided into three matches of 4 competitors.

So, for example, if we denote players by 1-13: in round 1, player 1 skips that round, 2-3-4-5 is one match, 6-7-8-9 the other one, and 10-11-12-13 the last one.

In the end, every player would play in 12 (out of 13) rounds.

Is it possible to make a bracket so that every player plays every opponent exactly three times in total across the duration of 13 rounds?

(In the example above, in Round 1, player 2 played once against players 3, 4 and 5, and zero times against all of the others.)

$\endgroup$

1 Answer 1

4
$\begingroup$

How about this:

Round $1$: $(2, 3, 4, 5), (6, 7, 8, 9), (10, 11, 12, 13)$
Round $2$: $(1, 4, 5, 7), (3, 9, 12, 13), (6, 8, 10, 11)$
Round $3$: $(1, 5, 6, 11), (2, 9, 10, 13), (4, 7, 8, 12)$
Round $4$: $(1, 3, 8, 12), (2, 7, 11, 13), (5, 6, 9, 10)$
Round $5$: $(1, 2, 4, 9), (3, 7, 10, 11), (6, 8, 12, 13)$
Round $6$: $(1, 3, 9, 11), (2, 7, 10, 12), (4, 5, 8, 13)$
Round $7$: $(1, 2, 6, 12), (3, 5, 8, 10), (4, 9, 11, 13)$
Round $8$: $(1, 7, 9, 10), (2, 5, 6, 13), (3, 4, 11, 12)$
Round $9$: $(1, 7, 8, 13), (2, 5, 11, 12), (3, 4, 6, 10)$
Round $10$: $(1, 2, 8, 11), (3, 5, 7, 13), (4, 6, 9, 12)$
Round $11$: $(1, 3, 6, 13), (2, 4, 8, 10), (5, 7, 9, 12)$
Round $12$: $(1, 4, 10, 13), (2, 3, 6, 7), (5, 8, 9, 11)$
Round $13$: $(1, 5, 10, 12), (2, 3, 8, 9), (4, 6, 7, 11)$

Edit #1:

To see how to come up with this solution, consider the image below:

enter image description here

This image depicts the first round: The white node labelled "1" skips the first round while the three teams are made up of the blue nodes $2,3,4,5$, the green nodes $6,7,8,9$ and the red ones $10,11,12,13$.

In the second round, all quadrilaterals are rotated clockwise by $1/13$ turn (or, equivalently, the node labels are rotated counter-clockwise), so that node "2" gets to skip the round. The new blue team will then consist of nodes $11$, $6$, $8$, and $10$ and so on.

The reason why this construction works is that the $3\cdot {4\choose2}=18$ distances of players of the same team are evenly distributed among the numbers $1$ through $6$:
The 3 node pairs $(6,7)$, $(11,12)$ as well as $(12,13)$ each have distance $1$, the 3 node pairs $(4,5)$, $(7,8)$ and $(11,13)$ have distance $2$ etc - each distance is obtained exactly three times, so each pair of nodes will be included in a team in exactly three rotations.

Edit #2:

I just noticed that an equivalent scenario (even distribution of the distances of pairs of team members) can be achieved in a more symmetric way:

enter image description here

$\endgroup$
10
  • $\begingroup$ Was your answer computer generated, or is there an elegant algorithm that you applied, perhaps somehow involving modular congruencies? Personally, I tried the modular congruency approach and struck out. $\endgroup$ Commented Feb 9, 2021 at 17:18
  • $\begingroup$ @user2661923: I added a picture I used to construct the solution (re-numbered the vertices in order to start with $(2,3,4,5)$ etc.) $\endgroup$
    – jpvee
    Commented Feb 9, 2021 at 19:27
  • $\begingroup$ Seems like you've really come up with an elegant approach, which might even allow generalization to similar problems. Unfortunately, I can't decipher how the rotations should occur to specify the pairings in each round. Could you be more specific? Also, (if possible) could you also include analysis that is as elegant as possible, that demonstrates that your methodology+algorithm will satisfy the constraints? $\endgroup$ Commented Feb 9, 2021 at 20:07
  • $\begingroup$ @user2661923: I made the explanation a bit more detailed - hope that makes things clearer. $\endgroup$
    – jpvee
    Commented Feb 9, 2021 at 20:35
  • $\begingroup$ +1 : Thanks very much, your explanation certainly helps. $\endgroup$ Commented Feb 9, 2021 at 20:47

You must log in to answer this question.