1
$\begingroup$

Imagine you are hosting a double dating party for straight men and women. There are $2n$ straight men and $2n$ straight women, and you want to pair them into $n$ double dates of 2 men and 2 women each. Then, in the next round, you regroup them such that no 2 people of the same sex see each other again (lest they feel like they're competing) and no 2 people of the opposite sex see each other again (to minimize the number of rounds needed to expose all opposite-sex pairs).

For what values of $n$, if any, can we hold a series of rounds until everyone has seen everyone of the opposite sex once and no one of the same sex more than once? Is there an algorithm to generate the groups?

How much is solution set expanded by allowing people to see members of the opposite sex more than once (but still never seeing people of the same sex twice)?

For $n$ where there is no ideal grouping, how many rounds can you do before needing to repeat a pairing?


My thoughts so far.

The optimal number of rounds should always be $n$, since an individual would see 2 new individuals of the opposite sex per round and thus see all of them in $2n / 2=n$ rounds.

Avoiding duplicating a same-sex pairing, you cannot have more than 2n-1 rounds, by the pigeonhole principle.

The problem is trivial for $n=1$. Men A and B are paired with women 1 and 2 and we are done in one round.

It is not possible for $n=2$: in round 2, without loss of generality, we pair men A and C. Then there is no pair of two women that A and C have both not yet met.

However, if we allow duplicate opposite sex pairings, we can generate expose all male/female pairs in $k=3$ rounds without duplicate same sex pairings:

Round 1:

$$\begin{bmatrix}A & B \\ 1 & 2\end{bmatrix},\,\begin{bmatrix}C & D \\ 3 & 4\end{bmatrix}$$

Round 2: $$\begin{bmatrix}A & C \\ 1 & 3\end{bmatrix},\,\begin{bmatrix}B & D \\ 2 & 4\end{bmatrix}$$

Round 3: $$\begin{bmatrix}A & D \\ 1 & 4\end{bmatrix},\,\begin{bmatrix}B & C \\ 2 & 3\end{bmatrix}$$

$\endgroup$

1 Answer 1

0
$\begingroup$

When $n$ is a power of $2$, one of two things happens: either there is an $n$-round solution (with no duplicate pairings of any kind), or there is an $(n+1)$-round solution avoiding same-sex duplicate pairings. Which of these happens depends on details of finite fields I'm not sure about.

To do this, let $q = 2n$ be the number of people of each sex; label each man, and separately each woman, with the elements of the finite field $\mathbb F_q$.

In this field, there are $q$ elements, and it has characteristic $2$: $a+a = 0$ for all $a \in \mathbb F_q$. There is a multiplication which acts as you'd expect. We can find a primitive element $x$ such that the set $\{1, x, x^2, \dots, x^{q-2}\}$ gives us all the nonzero elements of $\mathbb F_q$ with no repetition. (Actually, there are many possible choices of $x$, in general.)

Assign the double date groups for the first $n-1$ rounds as follows:

  • On round $1$, for each $a \in \mathbb F_q$, have men $a$ and $a + x + x^2$ go on a double date with women $a + x$ and $a + x^2$.
  • On round $2$, for each $a \in \mathbb F_q$, have men $a$ and $a + x^3 + x^4$ go on a double date with women $a + x^3$ and $a + x^4$.
  • On round $i$, $i \le n-1$, for each $a \in \mathbb F_q$, have men $a$ and $a + x^{2i-1} + x^{2i}$ go on a double date with women $a + x^{2i-1}$ and $a + x^{2i}$.

Note that because $\mathbb F_q$ has characteristic $2$, as $a$ ranges over all $2n$ elements of $\mathbb F_q$, we get $2n$ different double dates for each round, but actually this describes each of $n$ double dates twice. In round $1$, for example, the double date of $\{a, a+x+x^2\}$ with $\{a+x, a+x^2\}$ is the same as the double date of $\{b, b+x+x+^2\}$ with $\{b+x, b+x^2\}$ for $b = a+x+x^2$. Also, we'd get the same double dates if we described them from the point of view of the women.

After the first $n-1$ rounds, person $a$ of either sex has been on a double date with everyone of the opposite sex except $a$ and $a+1$ (because they've been on a date with $a+x, a+x^2, \dots, a+x^{q-2}$), and with roughly half of the people of the same sex.

Now, there are two possibilities. If $1 \ne x^{2i-1} + x^{2i}$ for any $i \le n-1$ (if person $a$ has never been on a date with person $a+1$ of the same sex) then we can finish things off in one more round:

  • On round $n$, for each $a \in \mathbb F_q$, have men $a$ and $a+1$ go on a double date with women $a$ and $a+1$.

If this does not work out, then we can finish the problem in two more rounds. Let $y,z \in \mathbb F_q$ be two distinct elements not among $\{x + x^2, x^3 + x^4, \dots, x^{2n-3} + x^{2n-2}\}$. Then

  • On round $n$, for each $a \in \mathbb F_q$, have men $a$ and $a+y$ go on a double date with women $a$ and $a+y$.
  • On round $n+1$, for each $a \in \mathbb F_q$, have men $a$ and $a+z$ go on a double date with women $a+1$ and $a+z+1$.
$\endgroup$

You must log in to answer this question.

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