How to rotate n individuals at a dinner party so that every guest meets every other guests
$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.)
combinatorics
asked Apr 21 '11 at 16:50
DanielEliDanielEli
173117
$endgroup$
|
show 1 more comment
$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.)
combinatorics
asked Apr 21 '11 at 16:50
DanielEliDanielEli
173117
$endgroup$
$begingroup$
Man, this word problem seems more practical thantrain a leaves the station at 8pm.... Where were these in school?
$endgroup$
– Kevin Peno
Apr 21 '11 at 16:53
$begingroup$
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).
$endgroup$
– Alon Amit
Apr 21 '11 at 17:09
$begingroup$
You might want to check out en.wikipedia.org/wiki/Combinatorial_design
$endgroup$
– Fixee
Apr 21 '11 at 17:24
$begingroup$
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?
$endgroup$
– Qiaochu Yuan
Apr 21 '11 at 18:01
$begingroup$
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.
$endgroup$
– Aubrey da Cunha
Apr 21 '11 at 18:19
|
show 1 more comment
$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.)
combinatorics
asked Apr 21 '11 at 16:50
DanielEliDanielEli
173117
$endgroup$
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.)
combinatorics
combinatorics
asked Apr 21 '11 at 16:50
DanielEliDanielEli
173117
asked Apr 21 '11 at 16:50
DanielEliDanielEli
173117
edited Jun 29 '11 at 16:17
DanielEli
asked Apr 21 '11 at 16:50
DanielEliDanielEli
173117
asked Apr 21 '11 at 16:50
DanielEliDanielEli
173117
asked Apr 21 '11 at 16:50
DanielEliDanielEli
173117
173117
$begingroup$
Man, this word problem seems more practical thantrain a leaves the station at 8pm.... Where were these in school?
$endgroup$
– Kevin Peno
Apr 21 '11 at 16:53
$begingroup$
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).
$endgroup$
– Alon Amit
Apr 21 '11 at 17:09
$begingroup$
You might want to check out en.wikipedia.org/wiki/Combinatorial_design
$endgroup$
– Fixee
Apr 21 '11 at 17:24
$begingroup$
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?
$endgroup$
– Qiaochu Yuan
Apr 21 '11 at 18:01
$begingroup$
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.
$endgroup$
– Aubrey da Cunha
Apr 21 '11 at 18:19
|
show 1 more comment
$begingroup$
Man, this word problem seems more practical thantrain a leaves the station at 8pm.... Where were these in school?
$endgroup$
– Kevin Peno
Apr 21 '11 at 16:53
$begingroup$
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).
$endgroup$
– Alon Amit
Apr 21 '11 at 17:09
$begingroup$
You might want to check out en.wikipedia.org/wiki/Combinatorial_design
$endgroup$
– Fixee
Apr 21 '11 at 17:24
$begingroup$
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?
$endgroup$
– Qiaochu Yuan
Apr 21 '11 at 18:01
$begingroup$
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.
$endgroup$
– Aubrey da Cunha
Apr 21 '11 at 18:19
$begingroup$
Man, this word problem seems more practical than
train a leaves the station at 8pm.... Where were these in school?$endgroup$
– Kevin Peno
Apr 21 '11 at 16:53
$begingroup$
Man, this word problem seems more practical than
train a leaves the station at 8pm.... Where were these in school?$endgroup$
– Kevin Peno
Apr 21 '11 at 16:53
$begingroup$
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).
$endgroup$
– Alon Amit
Apr 21 '11 at 17:09
$begingroup$
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).
$endgroup$
– Alon Amit
Apr 21 '11 at 17:09
$begingroup$
You might want to check out en.wikipedia.org/wiki/Combinatorial_design
$endgroup$
– Fixee
Apr 21 '11 at 17:24
$begingroup$
You might want to check out en.wikipedia.org/wiki/Combinatorial_design
$endgroup$
– Fixee
Apr 21 '11 at 17:24
$begingroup$
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?
$endgroup$
– Qiaochu Yuan
Apr 21 '11 at 18:01
$begingroup$
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?
$endgroup$
– Qiaochu Yuan
Apr 21 '11 at 18:01
$begingroup$
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.
$endgroup$
– Aubrey da Cunha
Apr 21 '11 at 18:19
$begingroup$
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.
$endgroup$
– Aubrey da Cunha
Apr 21 '11 at 18:19
|
show 1 more comment
3 Answers
3
active
oldest
votes
$begingroup$
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.)
answered Apr 21 '11 at 17:48
futurebirdfuturebird
3,60412752
$endgroup$
1
$begingroup$
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.
$endgroup$
– Aubrey da Cunha
Apr 21 '11 at 18:16
$begingroup$
OK I see that now.
$endgroup$
– futurebird
Apr 21 '11 at 18:33
$begingroup$
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).
$endgroup$
– Barry Fruitman
Mar 18 '15 at 20:45
add a comment |
$begingroup$
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
edited Mar 3 '18 at 20:05
Community♦
1
answered Apr 21 '11 at 17:36
Jesse PhillipsJesse Phillips
1012
$endgroup$
$begingroup$
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.
$endgroup$
– Jesse Phillips
Apr 21 '11 at 17:53
3
$begingroup$
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.
$endgroup$
– Jonas Kibelbek
Apr 21 '11 at 20:07
$begingroup$
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!
$endgroup$
– Jonas Kibelbek
Apr 21 '11 at 20:26
$begingroup$
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.
$endgroup$
– ShreevatsaR
Jun 29 '11 at 16:34
add a comment |
$begingroup$
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.
answered Sep 23 '13 at 7:28
Empy2Empy2
33.6k12362
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f34328%2fhow-to-rotate-n-individuals-at-a-dinner-party-so-that-every-guest-meets-every-ot%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
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.)
answered Apr 21 '11 at 17:48
futurebirdfuturebird
3,60412752
$endgroup$
1
$begingroup$
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.
$endgroup$
– Aubrey da Cunha
Apr 21 '11 at 18:16
$begingroup$
OK I see that now.
$endgroup$
– futurebird
Apr 21 '11 at 18:33
$begingroup$
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).
$endgroup$
– Barry Fruitman
Mar 18 '15 at 20:45
add a comment |
$begingroup$
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.)
answered Apr 21 '11 at 17:48
futurebirdfuturebird
3,60412752
$endgroup$
1
$begingroup$
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.
$endgroup$
– Aubrey da Cunha
Apr 21 '11 at 18:16
$begingroup$
OK I see that now.
$endgroup$
– futurebird
Apr 21 '11 at 18:33
$begingroup$
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).
$endgroup$
– Barry Fruitman
Mar 18 '15 at 20:45
add a comment |
$begingroup$
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.)
answered Apr 21 '11 at 17:48
futurebirdfuturebird
3,60412752
$endgroup$
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.)
answered Apr 21 '11 at 17:48
futurebirdfuturebird
3,60412752
answered Apr 21 '11 at 17:48
futurebirdfuturebird
3,60412752
answered Apr 21 '11 at 17:48
futurebirdfuturebird
3,60412752
answered Apr 21 '11 at 17:48
futurebirdfuturebird
3,60412752
3,60412752
1
$begingroup$
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.
$endgroup$
– Aubrey da Cunha
Apr 21 '11 at 18:16
$begingroup$
OK I see that now.
$endgroup$
– futurebird
Apr 21 '11 at 18:33
$begingroup$
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).
$endgroup$
– Barry Fruitman
Mar 18 '15 at 20:45
add a comment |
1
$begingroup$
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.
$endgroup$
– Aubrey da Cunha
Apr 21 '11 at 18:16
$begingroup$
OK I see that now.
$endgroup$
– futurebird
Apr 21 '11 at 18:33
$begingroup$
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).
$endgroup$
– Barry Fruitman
Mar 18 '15 at 20:45
1
1
$begingroup$
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.
$endgroup$
– Aubrey da Cunha
Apr 21 '11 at 18:16
$begingroup$
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.
$endgroup$
– Aubrey da Cunha
Apr 21 '11 at 18:16
$begingroup$
OK I see that now.
$endgroup$
– futurebird
Apr 21 '11 at 18:33
$begingroup$
OK I see that now.
$endgroup$
– futurebird
Apr 21 '11 at 18:33
$begingroup$
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).
$endgroup$
– Barry Fruitman
Mar 18 '15 at 20:45
$begingroup$
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).
$endgroup$
– Barry Fruitman
Mar 18 '15 at 20:45
add a comment |
$begingroup$
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
edited Mar 3 '18 at 20:05
Community♦
1
answered Apr 21 '11 at 17:36
Jesse PhillipsJesse Phillips
1012
$endgroup$
$begingroup$
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.
$endgroup$
– Jesse Phillips
Apr 21 '11 at 17:53
3
$begingroup$
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.
$endgroup$
– Jonas Kibelbek
Apr 21 '11 at 20:07
$begingroup$
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!
$endgroup$
– Jonas Kibelbek
Apr 21 '11 at 20:26
$begingroup$
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.
$endgroup$
– ShreevatsaR
Jun 29 '11 at 16:34
add a comment |
$begingroup$
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
edited Mar 3 '18 at 20:05
Community♦
1
answered Apr 21 '11 at 17:36
Jesse PhillipsJesse Phillips
1012
$endgroup$
$begingroup$
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.
$endgroup$
– Jesse Phillips
Apr 21 '11 at 17:53
3
$begingroup$
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.
$endgroup$
– Jonas Kibelbek
Apr 21 '11 at 20:07
$begingroup$
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!
$endgroup$
– Jonas Kibelbek
Apr 21 '11 at 20:26
$begingroup$
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.
$endgroup$
– ShreevatsaR
Jun 29 '11 at 16:34
add a comment |
$begingroup$
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
edited Mar 3 '18 at 20:05
Community♦
1
answered Apr 21 '11 at 17:36
Jesse PhillipsJesse Phillips
1012
$endgroup$
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
edited Mar 3 '18 at 20:05
Community♦
1
answered Apr 21 '11 at 17:36
Jesse PhillipsJesse Phillips
1012
edited Mar 3 '18 at 20:05
Community♦
1
edited Mar 3 '18 at 20:05
Community♦
1
edited Mar 3 '18 at 20:05
Community♦
1
1
answered Apr 21 '11 at 17:36
Jesse PhillipsJesse Phillips
1012
answered Apr 21 '11 at 17:36
Jesse PhillipsJesse Phillips
1012
answered Apr 21 '11 at 17:36
Jesse PhillipsJesse Phillips
1012
1012
$begingroup$
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.
$endgroup$
– Jesse Phillips
Apr 21 '11 at 17:53
3
$begingroup$
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.
$endgroup$
– Jonas Kibelbek
Apr 21 '11 at 20:07
$begingroup$
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!
$endgroup$
– Jonas Kibelbek
Apr 21 '11 at 20:26
$begingroup$
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.
$endgroup$
– ShreevatsaR
Jun 29 '11 at 16:34
add a comment |
$begingroup$
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.
$endgroup$
– Jesse Phillips
Apr 21 '11 at 17:53
3
$begingroup$
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.
$endgroup$
– Jonas Kibelbek
Apr 21 '11 at 20:07
$begingroup$
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!
$endgroup$
– Jonas Kibelbek
Apr 21 '11 at 20:26
$begingroup$
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.
$endgroup$
– ShreevatsaR
Jun 29 '11 at 16:34
$begingroup$
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.
$endgroup$
– Jesse Phillips
Apr 21 '11 at 17:53
$begingroup$
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.
$endgroup$
– Jesse Phillips
Apr 21 '11 at 17:53
3
3
$begingroup$
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.
$endgroup$
– Jonas Kibelbek
Apr 21 '11 at 20:07
$begingroup$
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.
$endgroup$
– Jonas Kibelbek
Apr 21 '11 at 20:07
$begingroup$
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!
$endgroup$
– Jonas Kibelbek
Apr 21 '11 at 20:26
$begingroup$
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!
$endgroup$
– Jonas Kibelbek
Apr 21 '11 at 20:26
$begingroup$
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.
$endgroup$
– ShreevatsaR
Jun 29 '11 at 16:34
$begingroup$
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.
$endgroup$
– ShreevatsaR
Jun 29 '11 at 16:34
add a comment |
$begingroup$
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.
answered Sep 23 '13 at 7:28
Empy2Empy2
33.6k12362
$endgroup$
add a comment |
$begingroup$
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.
answered Sep 23 '13 at 7:28
Empy2Empy2
33.6k12362
$endgroup$
add a comment |
$begingroup$
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.
answered Sep 23 '13 at 7:28
Empy2Empy2
33.6k12362
$endgroup$
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.
answered Sep 23 '13 at 7:28
Empy2Empy2
33.6k12362
edited Sep 23 '13 at 7:56
answered Sep 23 '13 at 7:28
Empy2Empy2
33.6k12362
answered Sep 23 '13 at 7:28
Empy2Empy2
33.6k12362
answered Sep 23 '13 at 7:28
Empy2Empy2
33.6k12362
33.6k12362
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f34328%2fhow-to-rotate-n-individuals-at-a-dinner-party-so-that-every-guest-meets-every-ot%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Man, this word problem seems more practical than
train a leaves the station at 8pm.... Where were these in school?$endgroup$
– Kevin Peno
Apr 21 '11 at 16:53
$begingroup$
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).
$endgroup$
– Alon Amit
Apr 21 '11 at 17:09
$begingroup$
You might want to check out en.wikipedia.org/wiki/Combinatorial_design
$endgroup$
– Fixee
Apr 21 '11 at 17:24
$begingroup$
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?
$endgroup$
– Qiaochu Yuan
Apr 21 '11 at 18:01
$begingroup$
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.
$endgroup$
– Aubrey da Cunha
Apr 21 '11 at 18:19