1
$\begingroup$

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.

$\endgroup$
3
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.