0
$\begingroup$

Possible Duplicate:
Gay Speed Dating Problem

There are n (even) people at a dance and they dance in pairs. They do not care about gender (it is a very liberal disco). The goal is for each person to dance with every other person exactly once. (And no one is left without a dance partner at any step).

I have solved this for n = 4 and n = 6 by hand. I am imagining that there is some theorem in graph theory on graphs with 2-point subgraphs but I don't know the terminology used to find it. I have also search permutation problems in Math Stack Exchange with no luck (the problems I found used gender to restrict dance partners and did not seem to care about the condition that everyone has a partner at each step). Any suggestions?

A related problem is if the people are in two lines and we want to minimize the total amount of movement required to achieve everyone dancing with everyone else exactly once. A better analogy than a dance here would be a business speed dating event where every one needs to talk with everyone else exactly once. I have played with the lines rotating to the left by one person and the ends rotating to the other line, but could not get that to work quiet right.

(This problem occurred to me at a real life workshop where all the people had to partner with every other person exactly once)

And just in case it helps here is the solution for n = 4 with 3 dance steps:

(1,3) (2,4)

(1,2) (3,4)

(1,4) (2,3)

here (n,m) means person n is partnered with person m

  • 0
    @Ross - that does seem to solve the first part and the rotating lines part. It does not address what this is called in graph theory (Qiaochu Yuan commented: I think he means counting the number of maximal sets of disjoint edges in a complete graph on n vertices but did not give a reference at the time). And it also does not address how we minimize the amount of movement required by the people.2012-10-03
  • 0
    I looked up Maximal independent set here http://en.wikipedia.org/wiki/Maximal_independent_set but it doesn't seem to capture the same idea2012-10-03
  • 0
    The people who put together bridge tournaments have to solve this kind of problem. Each partnership has to play each other partnership, and the less moving around, the better. So I'd look at the bridge tournament scheduling literature.2012-10-04

2 Answers 2