16
$\begingroup$

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

  • 0
    Man, this word problem seems more practical than `train a leaves the station at 8pm...`. Where were these in school?2011-04-21
  • 0
    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).2011-04-21
  • 0
    You might want to check out http://en.wikipedia.org/wiki/Combinatorial_design2011-04-21
  • 0
    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?2011-04-21
  • 0
    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.2011-04-21
  • 0
    "Keep one person stationary and rotate the rest" (Jesse Phillips's answer) is the right solution. See also Wikipedia's article on [Round-robin tournament](http://en.wikipedia.org/w/index.php?title=Round-robin_tournament&oldid=432980993#Scheduling_algorithm) for an illustration. This is *exactly* what you want.2011-06-29

3 Answers 3

0

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.

10

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,4) (#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,4,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,4,6,1) (#3:6,2,5,1,4) (4:1,6,2,5,3) (5:2,1,3,4,6) (6:3,4,1,2,5)

1 3 6 2 4 5 
  • 0
    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.2011-04-21
  • 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.2011-04-21
  • 0
    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!2011-04-21
  • 0
    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](http://en.wikipedia.org/w/index.php?title=Round-robin_tournament&oldid=432980993#Scheduling_algorithm).2011-06-29
1

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

  • 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.2011-04-21
  • 0
    OK I see that now.2011-04-21
  • 0
    With this solution, every person will only meet half the other people (like speed-dating). By keeping one person fixed (see below), everyone will meet everyone else (like speed-networking).2015-03-18