The mathematics of perfect speed dating

A friend recently went to a speed-dating event with about a hundred people. The organizers seated ten people at each table: five men and five women. Everyone gave a one-minute introduction; then the men moved as a group clockwise to the next table. It does what it promises: every man eventually meets every woman.

But my friend pointed out a small cruelty in the design: each pack of five women travels together. Every woman hears the same four introductions again. And again. And again. The men have the same problem.

An interactive exploration

Here is a scaled-down version with 8 men and 8 women at four tables. Each table seats 2 of each. Compare the original rotation with the improved schedule, then select anyone to trace their evening.

Both schedules cover every possible man-woman pairing. The difference is what happens along the way.

1. In the original rotation, the men remain at fixed tables and each pair of women moves together. Every woman meets all eight men, but hears the same woman’s introduction four times.
2. In perfect mixing, everyone moves. Every person still meets all eight potential dates, but now also meets four different people of their own gender thus avoiding any repeated introduction.

The full mathematical design has a fifth round. It would place the men at two all-male tables and the women at two all-female tables, so the dating version simply drops it. The rest of this post is about the mathematics of designing such a schedule.

Problem Simplification: Drop gender

Let us first make the problem more demanding and, paradoxically, easier to understand. Suppose there are \(N\) people. In every round they split into tables of \(m\) people each. Can we arrange the rounds so that every pair of people shares a table once and only once?

Combinatorialists call this a resolvable Steiner \(2\)-design, or a resolvable block design. In our case, each round partitions the room, and the full evening covers every pair exactly once. Think of this as speed socializing.

The unavoidable constraints

Before searching for a schedule, we can rule out most values of \(N\) and \(m\) with two simple observations.

For tables of four, the possible room sizes begin \(N=4,16,28,40,\ldots\). For instance, twenty people cannot work: one person would need \(19/3\) rounds.

Passing the test does not guarantee a schedule

This is the first delightful trap: the conditions are necessary, but they are not sufficient. For example, \((m,N)=(6,36)\) passes both tests, yet no schedule exists (see for instance [Beth–Jungnickel–Lenz]). Some parts of the existence story are completely understood:

Interestingly, for every fixed \(m\), all sufficiently large \(N\) that pass the divisibility test do work [Ray-Chaudhuri–Wilson]. What remains difficult is the finite territory before “sufficiently large.” There is no known one-line classification for arbitrary \(m\).

Simple construction for specific parameters

The cleanest construction occurs when \(m=q\) is a prime power and \(N=q^2\). Imagine labeling people by the \(q^2\) points of a \(q\times q\) grid but doing arithmetic in the finite field \(\mathbb F_q\). Each round is characterized by a line of a given slope.

• One round uses the vertical lines.
• The other \(q\) rounds use the lines of slope \(a\): \(y=ax+b,\ \mathrm{where}\ a,b\in\mathbb F_q\).

Lines of one slope partition the grid, so they form a round. Any two points determine one and only one line, so any two people meet exactly once. For prime-power \(q\), finite fields give this construction immediately. This is what is used in the interactive schedule above (\(q=4\)).

For a general candidate \((m,N)\), there is still a universal search method: encode every possible table as a binary choice and require every participant to appear once per round and every pair once overall. This is an exact-cover or integer-programming problem. It can decide modest instances, but it is not a proof that all arithmetically admissible inputs work. At scale, design theory uses recursive constructions—group-divisible designs, frames, and difference families [Beth–Jungnickel–Lenz].

Add Gender back into the picture

Now color every participant one of two types—say women and men (suppose there are \(c\) women and \(N-c\) men). A table of size \(m\) can contain \(0,1,\ldots,m\) women. Let

\[ h_j=\#\{\text{tables containing exactly }j\text{ women}\}. \]

The vector \(h=(h_0,h_1,\ldots,h_m)\) is a histogram of the entire event. It lets us ask questions the ungendered version of the problem cannot ask:

• Can we make \(h_0=h_m=0\), so no table is all men or all women?
• If \(m\) is even, can most tables sit near the balanced value \(j=m/2\)?
• Which histograms are numerically plausible but geometrically impossible?

The first one would be interesting from a dating point of view where you would like to avoid tables of all men or all women. The second is just a stronger version of that, which states can be avoided. Highly biased table where all but one are men, or all but one are women. The third one is just the full mathematical complexity of this problem. The first three moments of these are fixed based on the parameters but there is interesting geometry past these. In mathematical language, asking for \(h_0=h_m=0\) is asking for a weak two-coloring or a two-sided blocking set. This connects our scheduling puzzle to block-design colorings [Rosa–Colbourn], asymptotic weak colorability [Horsley–Pike], and blocking sets in affine planes [Jamison], [Brouwer–Schrijver].

These equations are necessary, but they forget how tables overlap. That missing geometry is where the interesting questions live.

The complete \(m=4,N=16\) experiment

With 8 women and 8 men, there are \(\binom{16}{8}=12{,}870\) ways to assign the two types to the schedule. This is because we can fix the table arrangements and only permute the gender across the sixteen participants. Exhaustive enumeration produces exactly seven histograms:

The two bold rows are the ones that I found interesting. The first has no single-gender table anywhere. The second has sixteen perfectly balanced tables and four single-gender tables. The interactive figure uses the latter construction and drops its four single-gender tables. What remains is unusually clean: sixteen mixed tables over four rounds, every one split \(2+2\), and every possible man–woman pair covered exactly once. That right there is the perfect speed dating schedule!

Explore the full five-round design

Here is the original construction explorer. Unlike the dating view above, it keeps the fifth round because the full design is trying to make every pair meet exactly once. Switch between the two histograms at the top, choose any person, and click a round—or click someone in the tracker to jump directly to the round in which the pair meets.

The questions I was left with

While there are some obvious mathematical questions, some of which are still open in the academic literature, here’s a short list that opens up:

• Schedule existence. For which \((m,N)\) does a perfect pairwise-meeting schedule exist?
• Balanced events. When can a schedule be colored with equal-sized types and no monochromatic table?
• Histogram spectrum. Which vectors \(h\) satisfying the counting equations actually come from a schedule?
• Practical variants. What changes if we care only about cross-type meetings, allow uneven tables, or permit a small number of repeats?

Like many puzzles, I love that something that sounds almost petty (having to hear the same introduction four times) and opens into large bodies of mathematics. Here’s to improved speed dating!

References

1. D. K. Ray-Chaudhuri and R. M. Wilson, “Solution of Kirkman’s schoolgirl problem,” Proceedings of Symposia in Pure Mathematics 19 (1971), 187–203.
2. H. Hanani, D. K. Ray-Chaudhuri, and R. M. Wilson, “On resolvable designs,” Discrete Mathematics 3 (1972), 343–357. doi:10.1016/0012-365X(72)90091-X.
3. D. K. Ray-Chaudhuri and R. M. Wilson, “The existence of resolvable block designs,” in A Survey of Combinatorial Theory (1973), 361–375. doi:10.1016/B978-0-7204-2262-7.50035-1.
4. T. Beth, D. Jungnickel, and H. Lenz, Design Theory, 2nd ed., 2 vols., Cambridge University Press, 1999. Publisher preview.
5. N. S. Mendelsohn, “Intersection numbers of \(t\)-designs,” in L. Mirsky, ed., Studies in Pure Mathematics (Presented to Richard Rado), Academic Press, 1971, 145–150.
6. T. van Trung, Q.-R. Wu, and D. M. Mesner, “High order intersection numbers of \(t\)-designs,” Journal of Statistical Planning and Inference 56 (1996), 257–268. doi:10.1016/S0378-3758(96)00022-5.
7. A. Rosa and C. J. Colbourn, “Colorings of block designs,” in J. H. Dinitz and D. R. Stinson, eds., Contemporary Design Theory: A Collection of Surveys, Wiley, 1992, 401–430. Publisher page.
8. D. Horsley and D. A. Pike, “On balanced incomplete block designs with specified weak chromatic number,” Journal of Combinatorial Theory, Series A 123 (2014), 123–153. doi:10.1016/j.jcta.2013.12.004.
9. R. E. Jamison, “Covering finite fields with cosets of subspaces,” Journal of Combinatorial Theory, Series A 22 (1977), 253–266. doi:10.1016/0097-3165(77)90001-2.
10. A. E. Brouwer and A. Schrijver, “The blocking number of an affine space,” Journal of Combinatorial Theory, Series A 24 (1978), 251–253. doi:10.1016/0097-3165(78)90013-4.