# Round-robin pairings: Everybody need to meet everybody

I have the following problem, I have a class of N people and I want them to do stuff by pair, but I want them to do this with everybody but as fast as possible.

For N = 4 I got this:

A-B C-D
A-C B-D
A-D B-C


so in three turns it's finished.

I need to find an algorithm (simple to explain if possible) to solve this problem for any N.

As Federico Poloni pointed out, your request is essentially to schedule a round-robin tournament. If the number of participants is $N$, then there are $N(N-1)/2$ pairs who must meet. Thus the "as fast as possible" condition requires:

• If $N$ is even, $N-1$ rounds are necessary, with $N/2$ pairs meeting in each.

• If $N$ is odd, $N$ rounds are necessary, with $(N-1)/2$ pairs meeting in each.

An explicit formula can be given for the round in which each pair of participants (numbered $1$ to $N$) is to meet, but we will naturally treat the cases $N$ even and odd separately.

N is even

Consider an $N\times N$ table which tells the round in which a pair $(r,c)$ designated by the row $r$ and column $c$ is supposed to meet. Since we are concerned with scheduling of unordered pairs, this table should be symmetric in the sense that the entry $(r,c)$ agrees with the entry $(c,r)$.

Since we do not need any participant to "meet" themselves, the diagonal entries $(r,r)$ will not designate any actual round, but otherwise the table entries must be distinct in each row and distinct in each column (since a participant can only meet with one other person in any given round). In this respect we can make the table a symmetric latin square by placing the value $N$ along the diagonal and filling the off-diagonal entries with rounds $1$ through $N-1$ as scheduled for $r\neq c$.

Here is an algorithm to fill the $(r,c)$ entry with a value $f(r,c)$ between $1$ and $N$:

• If $r=c$, then $f(r,c) = N$. (diagonal entries)
• If $r\gt c$, then $f(r,c) = f(c,r)$. (entries below diagonal, by symmetry)
• If $c = N$, then $f(r,N) = r$. (entries in last column)
• Otherwise $r \lt c \lt N$. Then:
• If $r+c$ is even, $f(r,c) = \frac{r+c}{2}$.
• Otherwise $r+c$ is odd, and we take: $$f(r,c) = 1+ \left[ \left(\frac{r+c+N-1}{2} - 1 \right) \bmod (N-1)\right]$$

The final formula's complexity is occasioned by our need to coerce a value $f(r,c)$ between $1$ and $N-1$ for these off-diagonal entries.

This algorithm implements the method of constructing a schedule reported by Édouard Lucas of primality testing fame based on a "clock face" with positions $1$ to $N-1$ around the circumference and number $N$ at the center, a method "simple and ingenious" that he attributed to Felix Walecki:

Lucas, Edouard (1883). "Les jeux de demoiselles". Récréations Mathématiques (in French). Paris: Gauthier-Villars. pp. 161–197.

N is odd

Again we consider an $N\times N$ table whose entries $(r,c)$ tell the round in which participants $r$ and $c$ should meet. Again the table will be a symmetric latin square, but the significance of the diagonal entries is different. As only $N-1$ (an even number) of participants can meet in a round, the diagonal entry for $(r,r)$ will here tell us in which round participant $r$ is to be the "bystander".

Fill the entry $(r,c)$ with a value between $1$ and $N$ according to:

$$f(r,c) = 1 + [ (r+c-1) \bmod N ]$$

Again the formula is a bit fancy so that we get a number between $1$ and $N$, and could here be simplified if the rounds were to be "zero indexed".

Indeed the zero-indexing of participants as well as rounds would allow us to identify this symmetric latin square with the addition table modulo $N$.