5
$\begingroup$

My question is derived from real life but I think it's a classic mathematical problem.

My uncle wants to organize a group activity with 12 people and wants to start by pairing each person with each other person so they can meet shortly. Everyone has to see every other person, but only once. His initial question was if there could be an easy rotation system to organize this (like putting everyone in two rows or a circle or something like that), which I couldn't find. But now I'm even struggling just to find a way that it can organized at all, by just writing down one example of each of the 11 'meeting rounds' with the numbers of the persons that have to meet in each round.

However I'm sure this is a standard mathematical question that has been discussed often before - can someone give me a solution? A not too complicated rotation system would be great, a way to write down the order in which it can be organized would be nice as well. Thanks!

$\endgroup$
  • $\begingroup$ I don't think this has anything to do with symmetric groups, removing tag, adding discrete math. $\endgroup$ – Thomas Andrews Mar 27 '13 at 14:31
  • $\begingroup$ Presumably, you mean, each "round" six pairs meet, and you want to have every possible pair to have met exactly once at the end of $n$ rounds? $\endgroup$ – Thomas Andrews Mar 27 '13 at 14:33
  • $\begingroup$ Yes, that's the point: six pairs per round, after 11 rounds everyone has met everyone exactly once. $\endgroup$ – freudje Mar 27 '13 at 14:36
  • 1
    $\begingroup$ @caveman: To put it differently: only six pairs meet simultaneaouly, so divisibility by $6$ suffices here. $\endgroup$ – Marc van Leeuwen Mar 27 '13 at 14:51
  • $\begingroup$ @MarcvanLeeuwen, thanks you're right $\endgroup$ – user58512 Mar 27 '13 at 14:52
6
$\begingroup$

There is an easy general scheduling algorithm for round-robin tournaments, indicated under the link.

To wit, have $6$ tables with a pair of opposite seats in a line. The first person at the first table stays seated all the time, the remaining seats are linked into a cycle of length $11$ by going along the remaining $5$ seats on the same end, and then in the oppositite order along the other end of the tables back, ending with the seat oppositie the fixed person before linking back to the second table. Now for each round just cycle the persons along those $11$ seats every time, for $11$ rounds in all. It is easy to see every other person is oppositie the fixed person once, and meets every other non-fixed person either while on one side of the table, or while on the other side of the tables, depending on parity.

0 1 2 3 4 5
B A 9 8 7 6

0 B 1 2 3 4
A 9 8 7 6 5

0 A B 1 2 3
9 8 7 6 5 4

0 9 A B 1 2
8 7 6 5 4 3

0 8 9 A B 1
7 6 5 4 3 2

0 7 8 9 A B
6 5 4 3 2 1

0 6 7 8 9 A
5 4 3 2 1 B

0 5 6 7 8 9
4 3 2 1 B A

0 4 5 6 7 8
3 2 1 B A 9

0 3 4 5 6 7
2 1 B A 9 8

0 2 3 4 5 6
1 B A 9 8 7

0 1 2 3 4 5
B A 9 8 7 6

0 B 1 2 3 4
A 9 8 7 6 5
$\endgroup$
2
$\begingroup$

You could look at the question Gay Speed Dating problem. The bridge players call it a Howell movement

$\endgroup$
  • $\begingroup$ Thank you, I knew it had to be a classic but couldn't find anything about it - this helps a lot! $\endgroup$ – freudje Mar 27 '13 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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