Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
@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. –  Michael Smith Oct 3 '12 at 23:50
    
I looked up Maximal independent set here en.wikipedia.org/wiki/Maximal_independent_set but it doesn't seem to capture the same idea –  Michael Smith Oct 3 '12 at 23:52
    
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. –  Gerry Myerson Oct 4 '12 at 7:44
add comment

marked as duplicate by Ross Millikan, tomasz, Norbert, draks ..., J. M. Oct 10 '12 at 17:06

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2 Answers

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.

share|improve this answer
add comment

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

share|improve this answer
    
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 theory –  Michael Smith Oct 3 '12 at 23:56
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.