Gay Speed Dating Problem

Here's an interesting problem that I came up with the other night.

With straight speed dating, (assuming the number of men and women are equal) the number of iterations that need to be made before every man has chatted with every woman is N/2, where N is the total number of people.

Gay speed dating is much more complex. The traditional model obviously won't work. Assuming in straight speed dating, the men stay at their tables, the "sitting" men in gay speed dating won't meet one another (nor will the "standing" men).

Counting combinations in gay speed dating manually, I see the following numbers:

f(2) = 1
f(3) = 3
f(4) = 3
f(5) = 5
f(6) = 5

These numbers suggest that gay speed dating can be done with N or N-1 iterations (albeit in a much more chaotic pattern).

Anyone have any ideas? Also, if it is N iterations, would there be a pattern that could be followed? I.e.: could the gentlemen circle a rectangular table in a clockwise fashion, then rearrange themselves and continue in another fashion such that given any number of men, every man would be paired with every other man in the smallest number of iterations and without pairing two men together twice.

Solution 1:

For an odd number, it is easy. Imagine a long table with a seat at one end and $\frac{N-1}{2}$ seats along each long side. Each person has a date with the person across. After each round, each person moves one seat clockwise. You should be able to convince yourself that each person meets each other after N rounds, but you can't do better as each person needs to meet N-1 others and has to sit out once.

Fixed even case, now optimal: If N is even, use the same table. Somebody sits at the head. The other N-1 rotate around as above. Each talks to the one directly across. This gets us N-1 rounds in the even case, which is optimal. Sorry to the pair that has to shout the long way.

The bridge players call this a Howell movement.

Solution 2:

I run gay speed dating events and have the seating charts for 12 participants up to 22. It's a little complex, but essentially you split the room into 2 parts, and then have 1/2 the room meet the other 1/2. Then you basically do the same thing for just the 1/2's all the way until everyone has met each other.