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

[azekeil.livejournal.com]

It's a pyramid isn't it? The answer is 2ⁿ-1 meetings.. but I don't think the meetings need to happen in pyramid form necessarily. You don't want me to work that out as well do you?

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.

[reddragdiva]

It's posts like this that make me feel less than superintelligent.

(Mathematics beyond first-year university is a very weak spot.)

[jinxremoving.livejournal.com]

but ... if it was poly bi speed dating, then perhaps pairs needn't be the default?

but, i'm a bit pickled and not very good at maths problems, so what do i know?

[valkyriekaren.livejournal.com]

GEEK!

[atommickbrane.livejournal.com]

The answer is that we are BRITISH and don't do 'dating', foo'.

[adjectivemarcus.livejournal.com]

I must admit I'd thought of having a speed dating workshop at BiCon before the logistics side of my brain started dangling a shiny thing in my field of vision. And I wasn't thinking of everytone meets everyone - what if some people aren't looking for either gender?

[tisme.livejournal.com]

Can't we just all let them loose in a room and let them get on with it?

[xxxlibris.livejournal.com]

Ooh - was having very similar discussions about this last week; namely on the (relatively simple) problem of gay speed dating: whether to ensure that each person has their three minutes with every other person, or whether they are split into two groups and treated like yer standard hetero groups. If the former, would some form of double circle/mobius loop thing work, with a crossover point? (This works in my head but is very hard to explain).

NB. This discussion took place in a bar where the upstairs had been given over to speed dating, and the downstairs to a Cafe Scientifique talk on whether giant robots would take over the world. Occasionally the two would meet; a group of bejumpered folk would wander upstairs to buy beer, or a couple of glammed and glossed ladies would head downstairs to the bathrooms.

[prettygothboy.livejournal.com]

Statistics, Statistics, I hated it at school, at 6th form at univercity, and i still hate it now.