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?

[azekeil.livejournal.com]

Eeek, or maybe 2^n-1... um...

[diffrentcolours]

Meetings in pyramid form are all very well until somebody falls over.

[ciphergoth.livejournal.com]

You need 2^n -1 meetings of n people if you want to have a different meeting for every possible non-empty subset of the people. But all we want is the pairs; there are n(n-1)/2 pairs. Since n/2 pairs can meet at once, the aim is to get everyone met up in n-1 sessions.

Here's a solution for six people to give you the idea:

1: A-B, C-D, E-F
2: A-C, B-E, D-F
3: A-D, B-F, C-E
4: A-E, B-D, C-F
5: A-F, B-C, D-E

Every possible pair is there, no-one is double booked or twiddling their thumbs in a given session, and everyone meets everyone else exactly once.

Can you do it for eight people?

[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!

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!

[reddragdiva]

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

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

[flickgc.livejournal.com]

They just make me feel stoopid...

[reddragdiva]

"Red D. Diva. Sooopergenius."

[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?

[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.

[tisme.livejournal.com]

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

[reddragdiva]

Yes, but then they'll argue over the beer.

[tisme.livejournal.com]

and the expensive condomns

[ciphergoth.livejournal.com]

BiCon generally has lots of free condoms though!

[tisme.livejournal.com]

There is a slight possibility that I may be bitter about my (now ex) SO's insistence on the really expensive type of condomns from Durex, and no other would do. It was either that or a cold shower.

[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.

[ciphergoth.livejournal.com]

...actually this is combinatorics.

I like statistics too though.