3
$\begingroup$

I have 4N players ( N = 4 or N = 5 suffices) and want to set up three rounds of play. In each round, there will be N games played (four players per game). I want to set up the groupings so that no two players appear together more than once, regardless of whether they are teammates or not.
Is there a reasonably simple non-exhaustive search algorithm that will set up these rounds for me?
The first round, of course is easy:
(16 players, each row is the players in one game)
1,2,3,4
5,6,7,8
9,10,11,12
13,14,15,16
To clarify: in a given round, every player is in one of the foursomes. All games (foursomes) are played simultaneously in a given round.

So in the second round, player 1 must not be in the same game as any of 2,3,4 ;and so on. I can't tell whether the Hungarian or Round Robin algos can't do this or just that the "AI" software can't do it correctly.

Another thought Based on an external suggestion; not sure this holds in all cases.
First divide the players into two equal sets. It's relatively easy to create unique pairs for the rounds in each of these "brackets." Then any combination of pairs from BracketA with pairs from BracketB will yield the groups of four that I'm looking for. Is this valid?

$\endgroup$
2
  • $\begingroup$ Isn't it like Euler's 36 officers or Kirkman's schoolgirls problems? en.wikipedia.org/wiki/Kirkman%27s_schoolgirl_problem $\endgroup$ Commented Apr 10, 2023 at 17:08
  • $\begingroup$ @HassBoyouk yes - thanks! This is Kirkman if I have 4N school girls in groups of 4 but only for 3 days. Looks like an ugly problem (Steiner) in general $\endgroup$ Commented Apr 10, 2023 at 17:53

1 Answer 1

3
$\begingroup$

For $N=5$ and more generally $N$ relatively prime to $6$, it is easy to make $N$ rounds.

Name the players $(i,j)$ for $0 \leq i \leq 3$ and $0 \leq j \leq N-1$. In the $a$-th round, take the elements of the $b$-th quadruple to be $\{ (0,b \bmod N), (1,a+b \bmod N), (2, 2a+b \bmod N), (3, 3a+b \bmod N) \}$.

Suppose, to the contrary that $(i_1, j_1)$ and $(i_2, j_2)$ play together in both rounds $a$ and $a'$. Since $(i,j_1)$ and $(i,j_2)$ never play in the same round, we must have $i_1 \neq i_2$. Then the equation that $i_1$ and $i_2$ play together in round $a$ says that $j_1 - a i_1 \equiv j_2 - a i_2 \equiv N$ and, likewise, $j_1 - a' i_1 \equiv j_2 - a' i_2 \bmod N$. So $(a-a') (i_1 - i_2) \equiv 0 \bmod N$. But $i_1 - i_2 \in \{ \pm 1, \pm 2, \pm 3 \}$ and $\text{GCD}(N,6)=1$, so this implies that $a=a'$. $\square$


A more pictorial description. I'll use bridge instead of tennis, because the 4-sides of a table make for good nomenclature. Arrange $N$ bridge tables in a cricle. At each of $N$ tables, let one player sit at north, one at east, one at south and one at north.

After the first set of games, the north players stay put, the east players move on one table, the south players move on two tables and the west players move on three table, each staying in their same position (north, east, west or south). Repeat this $N$ times.

$\endgroup$
9
  • $\begingroup$ I'm not sure this is the same problem? I want three 'rounds' , such that in each round everyone is playing in one of the 4-tuples. My "N" represents the number of 4-tuples playing in each of 3 rounds. (maybe generalize to M rounds of play later?) $\endgroup$ Commented Apr 10, 2023 at 17:50
  • $\begingroup$ So take the first three of these rounds. As I understand it, the conditions are that (1) all $4N$ players play each round and (2) no two players play together in two different rounds. If you can solve that for $M$ rounds, than you automatically get a solution for any smaller number of rounds. $\endgroup$ Commented Apr 10, 2023 at 18:29
  • $\begingroup$ close, but no 2 players on the court, partners OR opponents, in multiple rounds. My intent is to have as mixed-as-possible "social tennis" set up. $\endgroup$ Commented Apr 10, 2023 at 21:10
  • 1
    $\begingroup$ Right. No two players are in any quadruple more than once. $\endgroup$ Commented Apr 10, 2023 at 21:37
  • $\begingroup$ I'm sorry for being fogged here, but what is the meaning of the first element in each pair of your b-th quadruple? Don't you need to adjust those values 0:3 for each of the N rounds? if b ==1, then I see the second elements as 1,2,3,4 . I have players 0 <= i <= 15 , for example. $\endgroup$ Commented Apr 10, 2023 at 22:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .