procedure to pair all people with all others in a group

Question

I am looking for an easy method to ensure that all people in a group get to meet all others. The "speed dating" method is to have two rows of people facing each other, and then rotate one of the rows. This works for half of the pairings. How do I get the remaining pairings to happen properly in a simple way?

Answer 1

In baseball if a team wants to congratulate itself (not the other team). The team lines up. The first person turns around and walks down the line shaking everyone's hand, and then heads to the showers. Person 2 follows person 1, shaking all the later hands in the line and so on.

Answer 2

When $n$ is odd, label each person with elements of $\mathbb Z_{n}$ and, each round of introductions is also labeled from elements in $\mathbb Z_n$. Then in round $k$, person $a$ is introduced to person $b$, if $a+b=k$, with the unique person $i$ so that $2i=k$ not introduced to anybody. This yields $n$ rounds of $\frac{n-1}{2}$ pairs, the best you can do.

So persons $a$ and $b$ meet in round $a+b$, and person $a$ is left out of the introductions in round $2a$.

When $n$ is even, pick a single individual $X$ out of the set. Then apply the odd case to the $n-1$ other people, but introduce $X$ to the person left out each round. So person $X$ meets person $a$ in round $2a\pmod{n-1}$. This yields $\frac n2$ introductions in $n-1$ rounds, again the best you can do.

So, when $n=6$ we label the people $\{X,0,1,2,3,4\}$, and we get:

Round 0: X0 14 23
Round 1: X3 01 24 
Round 2: X1 02 34
Round 3: X4 03 12
Round 4: X2 04 13

If you absolutely must start with the speed dating approach, with $n_1$ men and $n_2$ women, then after those first $\max(n_1,n_2)$ rounds of speed dating introductions, the rest of the rounds might as well just follow my approach for introducing the $n_1$ men to each other and the $n_2$ women to each other. You can't do better.

Starting with speed dating would then require $$\max\left(n_1+2\left\lfloor\frac{n_1-1}{2}\right\rfloor+1,n_2+2\left\lfloor\frac{n_2-1}{2}\right\rfloor+1\right)$$ rounds of introductions.

There is a subtle reason that it is easier when $n$ is odd rather than when $n$ is even.

When $n$ is even, we need a binary operation $\star$ on $\{1,2,3,\dots,n\}$ which maps $(i,j)$ to the round number where $i,j$ meet, or $n$ when $i=j$. We obviously need $a\star b=b\star a$ for all $a,b$, and $a\star b=a\star c$ implies $b=c$. There is no good simple arithmetic commutative binary operation on $\mathbb Z_n$ such that $a\star a$ is independent of $a$. (If $n=2^k$, however, we can use the vector space of dimension $k$ over $\mathbb Z_2$ and define $a\star b=a+b$, since $a+a=0$ for all $a\in \mathbb Z_2^k$.)

On the other hand, if $n$ is odd, we have a binary commutative operation on $\mathbb Z_n$ in which $a\star b$ is the round when $a$ and $b$ are introduced, and $a\star a$ is the round when $a$ is left out. If we label the rounds so that $a$ is left out in round $a$, then this means:

$$a\star a = a\\a\star b=b\star a\\a\star b=a\star c\implies b=c$$

Then in any ring in which $2=1+1$ is a unit, this is easily defined as $a\star b=\frac{a+b}{2}$.

Answer 3

This is what I was looking for, as mentioned in the comment by paw88789: Round Robin from Wikipedia. Put glue on the first seat and then have the two rows rotate around in a cycle. If there is an odd number, then I as the presenter can sit in to make an even number, or else whoever is on the end that round takes a "bye". Perfect, thank you! Now I can tell my mentor that there is an easy solution.