Speed dating issues

I would like to think that my dating days aren't over, but just in a perpetually suspended state. However, I was at a speed-matching event yesterday which attempted to have a bunch of people meet everybody else one-on-one in a space of an hour.



First, there were only fifteen ppl and it was apparent that at every round someone would have to sit out. Then another guy showed up and we were sixteen. Since that was an even number no one would have to sit out. The person in charge did the obvious thing - he made two concentric rings of chairs splitting ppl two groups - 'inners' and 'outers'. The 'outers' rotated around the inner ring. After the first rotation, everybody had met half of the people in the group, except the ppl in their own ring. Then he did the next obvious thing, made another two concentric circles of the rings themselves and repeated the process. After the second rotation, everybody had met 3/4th of the ppl. For the next round, these rings needed to be split further into similar rings. As you can see, this process stops when each of the two concentric rings have exactly one person.

Of course, since we had the fourth power of 2, i.e. 16 ppl, this scheme works beautifully. Since, I was part architect of the idea, I wondered if this arrangement would work for other even numbers, leaving the rather odd case of odd numbers aside for now. Very quickly, you can see that this scheme breaks down for 6 people.

Round I            Round II
A D             A-B       D-E
B E             C (sits out)       F (sits out)
C F

After the first rotation, you have Ring I meet everyone in Ring II. Proceeding as before, you end up with 3 ppl (an odd number) in each new sub-ring. Now every subsequent iteration will have one person in each group simply sitting one session out. As you can see from the example, we can form a pair with C and F in Round II, but they have already met each other in Round I. So, every subsequent period, one person will be sitting out and wasting his time. This would require 6 time periods.

Thus, the concentric circles thing is inefficient for all non 2ⁿ even numbers. I tried to come up with a pairing scheme for n=6. Since ⁶C₂ = 15 total pairs, and we have 3 pairs at each stage, we should need at a minimum five rounds. With the schedule below no one sits out and we achieve efficiency.

Table for 6 ppl

Station	1	2	3	4	5
S1	AD	AE	AB	AF	AC
S2	BE	BF	CE	BC	BD
S3	CF	CD	DF	DE	EF

The movement of people is non-intuitive and the schedule is complicated. You would need to hand people a schedule map: A would not move at all. B would move to stations: S2-S2-S1-S2-S2. I was certain that there was a solution to this problem, floating in graph theory or combinatoric literature. And indeed there is! But, this is no simple can of worms as I was to discover.

Famously, in 1850 Reverend Thomas Kirkman sent a query to the readers of a popular math magazine, Lady's and Gentleman's Diary:

Fifteen young ladies in a school walk out 3 abreast for seven days in succession: it is required to arrange them daily, so that no two will walk twice abreast.

1 of 7 possible solutions

The more general case of problem is called the Social Golfer Problem: Determine the maximum number of days 'w' that 'n' golfers can play in groups of 'r' each without meeting each other. This is still an UNSOLVED mathematical problem!!! If you are interested in reading more see: Social Golfer Problem

My original question of dividing 'n' ppl in pairs has been solved at least up to n=200. Round-robin scheduling is a wonderful site for those scheduling matches, or speed-dating style events. There is no simple movement order that can be prescribed. You have to pretty much follow the schedule blindly. Some schedules are unique, in other cases there are over 1000 solution, usually when 2ⁿ numbers are involved.

Yeah! Even speed-dating has issues!