18
$\begingroup$

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.

  • 3
    I'm not sure exactly what you mean by "counting combinations." Also, you need to keep cultural considerations in mind: probably not everyone who reads this will know what speed dating is. Try to phrase the problem in a more mathematical way.2011-08-03
  • 5
    Are there lesbians in this problem or is this the "Gay male speed dating problem"? Then again, I figure if *everyone* in the dating schematic is gay, the two-gender case reduces to a maximum of the separate one-gender cases, so it's not really a problem mathematically...2011-08-03
  • 0
    @Qiaochu Yuan: I think he means counting the number of maximal sets of disjoint edges in a complete graph on $n$ vertices. I think I encountered something like this problem (including the proper terminology) in a graph theory textbook once, but I don't have easy access to it at the moment.2011-08-03
  • 2
    I think the question can be rephrased more formally as: Given a set $S$ of $n$ elements, what is the shortest sequence $C_i$ of sets of unordered pairs in $S$ such that each unordered pair occurs in exactly one $C_i$ and no pairs in a given $C_i$ "overlap"?2011-08-03
  • 1
    To me the question seems to just be: "how do I schedule a [round-robin tournament](http://en.wikipedia.org/w/index.php?title=Round-robin_tournament&oldid=441709674#Scheduling_algorithm)?" (And there's an answer at that link.)2011-08-05

3 Answers 3

15

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.

  • 2
    It’s worth pointing out explicitly that if $N=2^m(2k+1)$, this procedure requires a total of $2k+\sum_{i=0}^{m-1}2^i(2k+1)=2k+(2k+1)(2^m-1)=2^m(2k+1)-1=N-1$ rounds.2011-08-03
  • 0
    I don't quite see this as optimal. With 3 people, you need 3 rounds (because everyone has to sit out a round), not 2. With 6 people with your method, you seem to require $3+3=6$ rounds, but it is possible with 5 rounds, as the OP says. Perhaps I have misunderstood.2011-08-03
  • 0
    @Henry: In fact it can’t work as claimed: with $2k+1$ people there are $\binom{2k+1}{2}=k(2k+1)$ pairs, and each round accommodates only $k$ pairs, so $2k+1$ rounds are required. Making the corresponding adjustment to my previous comment, it seems that this method always requires $N$ rounds.2011-08-03
  • 0
    @Henry: I realized this as I was walking back to the office. I have updated the answer and am thinking more about the even case. I think with solutions for 4 and 6 we can make N-1 for all evens.2011-08-03
  • 0
    @Henry: it's much simpler than I thought at first. Fixed.2011-08-03
  • 0
    @Ross: +1 I'm happy now2011-08-03
  • 0
    @Brian: Are you talking about the OP's claim f(6) = 5 is incorrect?2011-08-03
  • 1
    @Mark: no, I agree with f(6)=5, and give a construction. I claim f(N)=N for N odd, f(N)=N-1 for N even, which agrees with OP's values2011-08-03
  • 0
    @Mark: In my second comment? No. I was pointing out that Ross’s original claim about the odd case couldn’t possibly be right and noting that when it was corrected, his original (flawed) solution boiled down to $f(N)=N$ in all cases.2011-08-03
  • 2
    The technical term for what Ross has done (in the even case) is finding a 1-factorization of the complete graph on $2n$ vertices - see, e.g., http://en.wikipedia.org/wiki/Graph_factorization The odd case is the same as http://math.stackexchange.com/questions/54846/handshaking-with-no-crossovers-in-minimum-number-of-rounds-has-this-problem-been/54852#548522011-08-04
  • 0
    "Sorry to the pair that has to shout." Cute. +12011-08-04
  • 2
    This is also known as a [round-robin tournament](http://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm).2011-08-05
3

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.

  • 0
    This is the solution I started with, but for an even number it leads to N rounds instead of N-1.2011-08-05
  • 1
    @Ross, indeed. I once took part in a chess tournament where 6 players were supposed to play a round-robin but the tournament director followed Craig's method and the tournament had to go 6 rounds with two players getting byes in each of the last three rounds.2011-08-05
  • 8
    I would have put the odds that a gay-speed-dating event-coordinator would be reading this forum on this day as less than 1 in a million.2011-08-05
2

It works the same as a round robin tournament. This website does it all for you: tournamentscheduler.net You just enter the names for the teams, and the table numbers for the locations.

  • 2
    +1. It will probably be much easier to find information on this problem by searching for "round robin tournament" than "gay speed dating".2013-02-21