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