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
    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

0

You can use the scheduling algorithm for a round-robin tournament. The algorithm is explained in this wiki page.

http://en.wikipedia.org/wiki/Round-robin_tournament

  • 0
    Thanks that is useful link and solve all the parts except minimizing how far the people have to move to swap partners and what this problem is called in graph theory2012-10-03
0

Here is a site where a large number of bridge movements have been collected. At this site, there is some discussion of desiderata. Typing $\rm bridge\ movements$ into the internets will turn up many more sites of possible interest.