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

It's the same problem as..

[bondagewoodelf.livejournal.com]

.. a sports competition, only the teams meet once, not twice,
.. people shaking hands at a party,
.. single gendered gay speed-dating.

Anyway, alexilian worked out an algorithm for this for any N (and a Java program that generates all meeting rounds)

I don't remember the specifics, but there are 3 classes of N:

- odd N, where you have the same solution as N+1, where you make a virtual person. Meeting that person means 'meet nobody'
- even numbered N, divisible by 4
- even numbered N, not divisible by 4

The total number of rounds (for even numbered N) is at least N-1 (because every person needs to meet everyone else). The algorithm proves that is also the maximum required amount of rounds.

If anyone is interested I can ask her to post the entire algorithm she worked out here. Anyway, the algorithm describes one way doing the rounds, it does not prove it is the only way to do it.

Re: It's the same problem as..

[ciphergoth.livejournal.com]

I'd be interested to see if her solution is the same as mine, certainly. Thanks!

Re: It's the same problem as..

[bondagewoodelf.livejournal.com]

Just phoned her, she'll have a look if she has time tonight to post it here. It's quite a lot of text, so brace yourself!