Same-sex speed dating

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Random832
Posts: 2525
Joined: Wed Oct 10, 2007 4:38 pm UTC

Same-sex speed dating

Postby Random832 » Tue Jul 29, 2008 8:28 pm UTC

http://en.wikipedia.org/wiki/Wikipedia: ... d_dating...

I tried to work this out and couldn't come up with an answer.

The basic question is, given N people, how do you rotate them between tables such that each one meets each other person exactly once? (as opposed to 'ordinary' heterosexual speed dating, where you have two groups of people and ensure that each person in one group meets each person in the other group once)

The only solution I've managedFAILED HORRIBLY to come up with that doesn't require a "sitting out" position [i.e. one or two people each turn sitting alone at a table) only works for groups of size 4n+2 [i.e. 6, 10, 14, 18, 22, etc]
Last edited by Random832 on Tue Jul 29, 2008 9:17 pm UTC, edited 1 time in total.

Buttons
Posts: 858
Joined: Wed May 02, 2007 3:27 pm UTC
Location: Somerville

Re: Same-sex speed dating

Postby Buttons » Tue Jul 29, 2008 8:41 pm UTC

So it turns out if a topic gets moved while you're writing a reply, the reply gets lost.

I'm not about to write out the solutions again, but it's definitely possible for 4 and 8. I suspect you can do it for any even number. This is basically a specific case of BIBDs.

EDIT: Er, duh. Easy solution. (Spoilers I guess, since this is logic puzzles now?)
Spoiler:
Suppose you have a way to do it for n people. To do it for 2n people, break everyone off into n pairs, say (x1,y1) through (xn,yn). Use the scheme for those n pairs, but make the sessions twice as long. Whenever you would have i dating j, instead have 2 dates: xi with xj and yi with yj, then xi with yj and yi with xj. After all that's over, have each xi date yi. Since you knew how to do it for 2k for any odd number k, we can now do it for any even number.
Last edited by Buttons on Tue Jul 29, 2008 8:55 pm UTC, edited 4 times in total.

Random832
Posts: 2525
Joined: Wed Oct 10, 2007 4:38 pm UTC

Re: Same-sex speed dating

Postby Random832 » Tue Jul 29, 2008 8:50 pm UTC

Buttons wrote:So it turns out if a topic gets moved while you're writing a reply, the reply gets lost.

Sorry, I actually deleted and reposted; didn't know someone was replying.

Buttons
Posts: 858
Joined: Wed May 02, 2007 3:27 pm UTC
Location: Somerville

Re: Same-sex speed dating

Postby Buttons » Tue Jul 29, 2008 9:05 pm UTC

'sall good. Anyway, I got an inductive solution (see above), but it relies on there being a method for the 4n+2 case. How did your solution for those numbers work?

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Same-sex speed dating

Postby Cauchy » Tue Jul 29, 2008 9:10 pm UTC

Spoiler:
Of your 2k people, seat 2k-1 in a circle, and put the 2kth person in the middle. We number the people in the circle from 0 to 2k-2, and all arithmetic will be done modulo 2k-1.

There will be 2k-1 rounds of dating, numbered 0 to 2k-2. In round i:

Person i dates the person in the middle of the circle. Person i-1 dates person i+1, person i-2 dates person i+2, and so on, with person i-(k-1) dating i+(k-1). Then, the person in the center dates each other person once, and persons m and n date on round (m+n)/2 = (m+n)*k.

This also lets you determine how to minimize the number of rounds needed for an odd number of people: if you have 2k-1 people, k-1 dates can happen per round, and you need (2k-1)(2k-2)/2 = (k-1)(2k-1) dates in total, so at least 2k-1 rounds are needed; the above method does this in 2k-1 rounds by removing the person in the middle and instead having the person who would date the person in the middle simply sit out for the round.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

Random832
Posts: 2525
Joined: Wed Oct 10, 2007 4:38 pm UTC

Re: Same-sex speed dating

Postby Random832 » Tue Jul 29, 2008 9:15 pm UTC

Buttons wrote:'sall good. Anyway, I got an inductive solution (see above), but it relies on there being a method for the 4n+2 case. How did your solution for those numbers work?


...nevermind - it seemed to work intuitively, but in drawing a set of diagrams to explain the method; I proved myself wrong (same basic flaw as Cauchy's) - I'm so embarassed.

Cauchy wrote:
Spoiler:
Of your 2k people, seat 2k-1 in a circle, and put the 2kth person in the middle. We number the people in the circle from 0 to 2k-2, and all arithmetic will be done modulo 2k-1.

There will be 2k-1 rounds of dating, numbered 0 to 2k-2. In round i:

Person i dates the person in the middle of the circle. Person i-1 dates person i+1, person i-2 dates person i+2, and so on, with person i-(k-1) dating i+(k-1). Then, the person in the center dates each other person once, and persons m and n date on round (m+n)/2 = (m+n)*k.

This also lets you determine how to minimize the number of rounds needed for an odd number of people: if you have 2k-1 people, k-1 dates can happen per round, and you need (2k-1)(2k-2)/2 = (k-1)(2k-1) dates in total, so at least 2k-1 rounds are needed; the above method does this in 2k-1 rounds by removing the person in the middle and instead having the person who would date the person in the middle simply sit out for the round.


Spoiler:
Dammit - I actually had a solution (will write up later, once I'm sure it'll actually WORK unlike the one I thought I had before) for odd numbers that this would work for (yours doesn't, by the way; e.g. 2 and 5 will never be i-n and i+n for any integers i and n, so person 2 and 5 never meet), but didn't consider having someone sitting still to meet the "odd person out", so didn't think it could be turned into a solution for even numbers

crzftx
Posts: 371
Joined: Tue Jul 29, 2008 4:49 am UTC
Location: Rockford, IL

Re: Same-sex speed dating

Postby crzftx » Wed Jul 30, 2008 3:21 am UTC

How many dates are necessary: Person 1 dates all of the other people, 2 through N, which is a total of N-1 dates. person 2 (who's already met person 1) meets person 3 through N, totaling N-2 dates. So every person X has N-X dates. Adding person 1's dates with person N's, you get N-1 + N-N, or N-1. Adding person 2's dates with person N-1's, you get N-2 + N-(N-1), again N-1. Every combination of person X with person N-X will equal N-1. This procedure works up to N/2, where X begins to come into the range of the people already counted in the N-X of the previous people. So there are N/2 groups of N-1, or N/2 * (N-1), simplified to (N^2-N)/2

Oops, I see the problem. I thought it looked really simple... I'm actually supposed to find table arrangements. How many people to a table? Can't we all just sit at one big round table and everybody meets everybody? What about this one which works for all odd numbers:

Spoiler:
This only woks for odd numbers. Assign every person a number. Draw a perfect circle with each number on the circle in order an equal distance from either number next to it. Then draw a line from 1 to N, from 2 to N-1, etc. After all of the people with lines drawn between them meet, rotate the lines clockwise. Continue to do this until everybody has met. There are (N-1)/2 meetings each time, and the circle is turned N times, meaning I did it correctly.


I see Cauchy had a solution. He said something about (2k-1)(k-1) dates necessary, using 2k = N, that would not be enough dates for everybody to meet. Take k=7, for example. (2(7)-1)(7-1) = 78, when in reality (14^2-14)/2 = 91 dates are necessary. There would be 7 dates per round, so that would be 91 dates in 13 rounds. I may have read his solution wrong, or he incorrectly figured (2k-1)(k-1).
Last edited by crzftx on Wed Jul 30, 2008 4:02 am UTC, edited 2 times in total.

Buttons
Posts: 858
Joined: Wed May 02, 2007 3:27 pm UTC
Location: Somerville

Re: Same-sex speed dating

Postby Buttons » Wed Jul 30, 2008 3:33 am UTC

Random832 wrote:
Spoiler:
Dammit - I actually had a solution (will write up later, once I'm sure it'll actually WORK unlike the one I thought I had before) for odd numbers that this would work for (yours doesn't, by the way; e.g. 2 and 5 will never be i-n and i+n for any integers i and n, so person 2 and 5 never meet), but didn't consider having someone sitting still to meet the "odd person out", so didn't think it could be turned into a solution for even numbers
Uh, I'm not sure you read Cauchy's solution correctly.
Spoiler:
Modular arithmetic, dude. All arithmetic is all taken mod 2k-1. So, for instance, if 2k-1 = 7, then 2 =7 0-5 and 5 =7 0+5.

Random832
Posts: 2525
Joined: Wed Oct 10, 2007 4:38 pm UTC

Re: Same-sex speed dating

Postby Random832 » Wed Jul 30, 2008 3:53 am UTC

Spoiler:
I was wrong - Cauchy's solution works - the main rotation being an odd number is the important bit; it actually ensures it doesn't repeat halfway through the way I thought having it be 4n+2 ensured it and it didn't.

Diagram of Cauchy's solution - which actually is basically the same as the one I was considering for odd numbers, if D is omitted:

Code: Select all

ABC D
EFG H

BCH D
AEF G

CHG D
BAE F

HGF D
CBA E

GFE D
HCB A

FEA D
GHC B

EAB D
FGH C


Now, the question remains - is there a way to do it while having everyone move the same way?

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Same-sex speed dating

Postby Cauchy » Wed Jul 30, 2008 4:22 am UTC

crzftx wrote:I see Cauchy had a solution. He said something about (2k-1)(k-1) dates necessary, using 2k = N, that would not be enough dates for everybody to meet. Take k=7, for example. (2(7)-1)(7-1) = 78, when in reality (14^2-14)/2 = 91 dates are necessary. There would be 7 dates per round, so that would be 91 dates in 13 rounds. I may have read his solution wrong, or he incorrectly figured (2k-1)(k-1).


The (2k-1)(k-1) dates are for 2k-1 people, which was the number of people I was talking about in that last paragraph.
(∫|p|2)(∫|q|2) ≥ (∫|pq|)2
Thanks, skeptical scientist, for knowing symbols and giving them to me.

Buttons
Posts: 858
Joined: Wed May 02, 2007 3:27 pm UTC
Location: Somerville

Re: Same-sex speed dating

Postby Buttons » Wed Jul 30, 2008 4:46 am UTC

Haven't you people been paying attention? Cauchy doesn't make errors.
Random832 wrote:Now, the question remains - is there a way to do it while having everyone move the same way?

Basically you're asking, is there some permutation [imath]\pi \in S_{2k}[/imath] so that some 2k-1 powers of [imath]\pi[/imath], acting on the set of people, represent an appropriate set of seating arrangements (yes: see Cauchy's), and so that all 2k people are in the same cycle?*

Well, no. If they're all in the same cycle, then you can straighten it out so they're moving around a circle. You could represent such a scheme as k pairs of chords between 2k evenly spaced points on a circle, which you then rotate a bunch of times to get the different seating arrangements. At least one of these chords must be a diameter, or else people across from each other never date. But there are only k distinct diameters spanning these 2k points, so you can't have 2k-1 different rotations of this diagram.

Unless, of course, 2k-1=k. That's the trivial case where two people date each other, and nobody moves at all.

*EDIT: The notation of this paragraph is obviously begging for a slick algebraic proof, but the method I was trying (okay, so pi has order 2k, and 2k-1 of its powers comprise the complete set....) kept getting bogged down in special cases, which is why I gave up and appealed to geometry. Anyone got an elegant algebraic solution?

crzftx
Posts: 371
Joined: Tue Jul 29, 2008 4:49 am UTC
Location: Rockford, IL

Re: Same-sex speed dating

Postby crzftx » Wed Jul 30, 2008 5:27 am UTC

Cauchy wrote:
crzftx wrote:I see Cauchy had a solution. He said something about (2k-1)(k-1) dates necessary, using 2k = N, that would not be enough dates for everybody to meet. Take k=7, for example. (2(7)-1)(7-1) = 78, when in reality (14^2-14)/2 = 91 dates are necessary. There would be 7 dates per round, so that would be 91 dates in 13 rounds. I may have read his solution wrong, or he incorrectly figured (2k-1)(k-1).


The (2k-1)(k-1) dates are for 2k-1 people, which was the number of people I was talking about in that last paragraph.


Thanks for clearing that up for me. "I may have read his solution wrong" obviously applied. I thought the solution was for 2k people. 2k-1 solves the discrepancy.

Random832
Posts: 2525
Joined: Wed Oct 10, 2007 4:38 pm UTC

Re: Same-sex speed dating

Postby Random832 » Wed Jul 30, 2008 1:08 pm UTC

As it happens, Cauchy's solution is equivalent to the scheduling algorithm from this wikipedia article.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 9 guests