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]

Whoa! I think you've slipped terms, from 2n people to just n people turning up! *grin*

If we have 2n people turning up (as originally stated), the number of possible distinct pairs is (2n(2n-1))/2, i.e. n(2n-1), or even 2n^2 - n if you prefer. We can have n pairs meeting at any one time, and we can work through every possible meeting in 2n-1 sessions.

Can you do it for eight people?

Yes, in seven sessions. :-)

It's going to be a bit of a logistical nightmare, I suspect, unless you can fix numbers in advance and have the 2n itineraries printed ready. (The itinerary also needs to specify a table to meet at - we'll need n of 'em.) The organisation needs to be good and clear to every participant or you'll waste shedloads of time faffing about. At a Bicon, perish the thought!

I've just realised I've wittered on about the organisation of the session instead of solving the puzzle as set ...

[drdoug.livejournal.com]

... and true to habits, have hunted down other people's attempts rather than solving it myself. Easier and more complete.

It seems there are (at least) two ways of doing it - the hard way (hunting for unmatched pairs each round, which is how I started solving it before giving up) and the easy way (rotating). See this page for a good discussion of the problem and solutions (including code!).

The discussion there is in terms of teams playing sport in a Round Robin against each other, but applies to our context. Pasted from one of the links there:

Say there are 6 teams:
1 2 3
6 5 4
On the next round, one team stays fixed (say 6* in this example), and the others rotate:
2 3 4
6* 1 5
On the next round it would be:
3 4 5
6* 2 1
and so on, for the 5 steps it takes for everyone to get back to where they started.


This rotating method seems very straightforward and intuitively correct. It's also very easy to implement in a real room with real people. You don't need numbers arranged in advance, a pre-prepared schedule or printed itineraries - or indeed any computational assistance. You just get people (apart from one!) to move round one seat each time. If you have an odd number, you just make the fixed seat a dummy - perhaps a fluffy toy.

I like this solution - I can imagine it working in real life!

[ciphergoth.livejournal.com]

This is *much* simpler than my solution. Superb, thanks!