Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm throwing an event where every individual is suppose to meet every other individual so I'm trying figure out how to rotate them. My friends say its easy but they have yet to come up with an answer and our event looms closer and closer.

We are shooting for n = 20 but my gut says n has to be a power of 2 for this to work. The first half is easy, you just have the odds stay in their seats and rotate evens. Then take the 10 odds, renumber them, repeat. Then split to 5... oops. you've got an odd number. but thats ok, you've got 4 groups with 5 each so create 2 pairs and you've got 5 sets of 2 pairs.

At this point, my head hurts and it's taking more time to tell my guests who to meet than they spend meeting them.

Is there a simpler answer for n=20?

(edit: lots of questions about the table setup and who they are suppose to meet. Assume whatever table arrangement works, we have a variety. Regardless, i think the long narrow solution below works.)

share|improve this question
    
Man, this word problem seems more practical than train a leaves the station at 8pm.... Where were these in school? –  Kevin Peno Apr 21 '11 at 16:53
    
Can you clarify the requirements you'd like to impose exactly? Are guests seated around one large round table? Does "meet" mean being seated next to a person? Are you trying to minimize the overall number of "shuffles", or something about the magnitude of the shuffles as well (e.g. you may worry less about two people swapping seats than about half the people getting up and moving elsewhere). –  Alon Amit Apr 21 '11 at 17:09
    
You might want to check out en.wikipedia.org/wiki/Combinatorial_design –  Fixee Apr 21 '11 at 17:24
    
A lot hinges on what you mean by "meet." Do you mean one-on-one conversation for a certain amount of time or would it be enough for, say, four people to introduce themselves to each other and do a quick activity? –  Qiaochu Yuan Apr 21 '11 at 18:01
    
Assuming meet means one-on-one, how familiar are your guests with binary? If they are pretty familiar, you can group them by successively longer prefixes of their number in binary. Within each group, the ones whose bit after the prefix is 0 are evens and the others odds. Although, the best way is still to work everything out in advance, write it down on cards and have everyone take a card on arrival. –  Aubrey da Cunha Apr 21 '11 at 18:19
show 1 more comment

3 Answers

up vote 1 down vote accepted

Seat your guests at a long banquet table, but don't seat anyone at the heads of the table. So like this:

A B C D E F
L K J I H G

then have them rotate:

L A B C D E 
K J I H G F


K L A B C D 
J I H G F E

And so on.

Done!

(Only you will have 10 on each side.)

share|improve this answer
1  
In your example, A meets L,J,H,F,D,B, and then back to L. So this is equivalent to fixing the odds and rotating the evens. –  Aubrey da Cunha Apr 21 '11 at 18:16
    
OK I see that now. –  a little don Apr 21 '11 at 18:33
add comment

I think the answer is:
Make one person stationary, rotate all the folks. This actually works.

Example with N=6. 1 is stationary. (Each person in the top row "meets" the corresponding person just below in the bottom row.)

1) (#1:4 #2:5 #3:6 #4:1 #5:2 #6:3)

1 2 3
4 5 6

2) (#1:4,5 #2:5,3 #3:6,2 #4:1,6 #5:2,1 #6:3,4)

1 4 2
5 6 3

3) (#1:4,5,6 #2:5,3,2 #3:6,2,5 #4:1,6,2 #5:2,1,3 #6:3,4,1)

1 5 4
6 3 2

4) (#1: 4,5,6,3)(#2:5,3,2,6)(#3:6,2,5,1)(4:1,6,2,5)(5:2,1,3,4)(6:3,4,1,2)

1 6 5
3 2 4

5) (#1: 4,5,6,3,2)(#2:5,3,2,6,5)(#3:6,2,5,1,4)(4:1,6,2,5,4)(5:2,1,3,4,6)(6:3,4,1,2,5)

1 3 6
2 4 5
share|improve this answer
    
I tried to show the stages above. Hard to do w/out a diagram. Draw it out: 1) draw six circles (a network graph), then draw a line w/ 1,2,3 on one side, 4,5,6 on the other. Make a box around 1, it is stationary. For each couplet (sitting across the line), make a line on the graph connecting them. in round 1, you connect, 1-4, 2-5, 3-6. Round 2, rotate all the numbers around the line, except 1 (it's in a box). You'll see that it just works out. I don't know why. –  Jesse Phillips Apr 21 '11 at 17:53
3  
This is an elegant and simple answer-- it is actually less confusing to follow than the "speed date" plan of successively dividing groups in half. For any group of 2n people, there will be 2n-1 rounds, with everyone meeting everyone else once. If you have an odd number of people, just add an imaginary person to the mix, with the result that each person has one round off from meeting anyone. Jesse Phillips suggests seating everyone at a long banquet table and rotating as in a little don's answer, but one person sitting at a corner remains fixed, while the other 2n-1 people rotate cyclically. –  Jonas Kibelbek Apr 21 '11 at 20:07
    
Label the stationary person (in one corner) by $p_0$ and the people in the cycle in order counter-clockwise by $p_i$ for $1 \leq i \leq 2n-1$, with $p_1$ opposite $p_0$ . Clearly, $p_0$ meets everyone once and the other $p_i$ are symmetric; so it suffices to check that $p_1$ meets everyone. Here is the list of partners for $p_1$, as everyone but $p_0$ moves counterclockwise each round: $p_0, p_{2n-2}, p_{2n-4}, \ldots, p_4, p_2, p_{2n-1}, p_{2n-3}, p_{2n-5}, \dots , p_5, p_3$. Very nice solution! –  Jonas Kibelbek Apr 21 '11 at 20:26
    
I changed the formatting in the answer from "vertical" (which wasn't working) to "horizontal", but feel free to revert. BTW, this solution which you independently found is also present on Wikipedia. –  ShreevatsaR Jun 29 '11 at 16:34
add comment

For sixteen people, sort them into four groups of four: A,B,C,D. Then seat them at two tables of eight:
ABAB CDCD
ABAB CDCD
then
ACAC BDBD
ACAC BDBD
then
ADAD BCBC
ADAD BCBC

Rotate the people within A, and those within B, etc, so they meet everyone within their own group.
Then, counting neighbours as next-to, opposite, and opposite's next-to, some people can meet all 15 others, but everyone else meets only 11 others.

--

For twelve people, number the chairs 1 to 6 on one side of the table, and 7 to 12 on the other side, so 1 faces 7, 2 faces 8 and so on. Everyone moves from seat $n$ to seat $3n (\mod 13)$ after each course.
ABCDEF
GHIJKL
then
IEAJFB
KGCLHD
then
CFILBE
HKADGJ
In this arrangement, everyone meets everyone else (next-to, opposite or opposite's next-to) except for BK, EH and FG.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.