The bisexual speed dating problem

[ciphergoth]

I had great fun at the Laputa party - good to meet everyone!

Here's a puzzle for math geeks, which could have applications to BiCon ice-breaking sessions: The bisexual speed dating problem.

Heterosexual speed dating: n men and n women meet up. In n sessions, each man talks to each woman in turn. This is easy to arrange: number the men 1-n and the women 1-n. In Session 1, man 1 talks to woman 1, 2-2 and so forth. In Session 2, man 1 talks to woman 2, 2 to 3, and n to 1. And so on, in a circle.

However, arranging things for bisexual speed dating is harder. 2n people turn up (has to be even, or you can't arrange them into pairs at all). You want to pair them off 2n-1 times in different pairing arrangements so that at the end, everyone has talked to everyone else. How do you do it? Can you do it no matter what n is?

You can do it if 2n = 4 thus. Supposing the four people are A, B, C, D, then you pair them off as follows:

Session 1: A-B, C-D
Session 2: A-C, B-D
Session 3: A-D, B-C

What about 6, 8, ...? Is there an algorithm that works for any even number of people?

In math geek terms: a pairing is a subgraph of a graph such that every node is incident to exactly one edge. Find an algorithm which partitions the edges of a complete graph on 2n nodes such that each equivalence class is a pairing. Equivalently, find a set of self-inverse permutations without fixed points on a set S of 2n elements such that for any distinct x, y in S, there exists exactly one permutation in the set mapping x to y.

I'm pretty sure I know the answer, but it's fun to throw it open first...

Comments

[drdoug.livejournal.com]

And I wasn't thinking of everytone meets everyone - what if some people aren't looking for either gender?

Oh blimey - that would get complicated to work out!

I'd been thinking of it as a speed getting-to-know-you session rather than speed dating - that way it doesn't matter.

[adjectivemarcus.livejournal.com]

Yes, speedmeeting, not speeddating.

[ciphergoth.livejournal.com]

I'd thought of it that way too.