Author |
Topic: Sitting guests around a table (Read 1139 times) |
|
Pietro K.C.
Full Member
 
Gender: 
Posts: 213
|
 |
Sitting guests around a table
« on: Sep 23rd, 2007, 1:49am » |
 Quote  Modify
|
I've looked and looked for a similar thread but haven't found one.
Suppose that 52 people will have dinner together, around a round table. When they are all accommodated, each person can only talk to their two immediate neighbors. But everyone wants to talk to everyone else.
So they do the following. Many times over dinner, all 52 guests will rise and change seats in some preordained fashion. That is, before dinner starts, they get together and plan out a sequence of seats for each person, and at (say) ten-minute intervals, everyone rises and each person goes to their next assigned seat.
What is the least number of different seating arrangements (or, 1 + number of times the guests rise and switch) necessary to get everyone talking to everyone else?
I promise you that this has the most lovely solution.
|
|
 IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Sitting guests around a table
« Reply #1 on: Sep 23rd, 2007, 5:40am » |
Quote Modify
|
If it is a lovely solution, it must be optimal. Nobody loves suboptimal solution. So the number of sessions (i.e. being seated) should be 51/2 rounded up = 26.
I'll leave it to you guys as an exercise to work out how. 
But I believe it doesn't have to be a round table.
|
| « Last Edit: Sep 23rd, 2007, 5:45am by Grimbal » |
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Sitting guests around a table
« Reply #2 on: Sep 23rd, 2007, 6:13am » |
Quote Modify
|
Don't we have un+1 = Ceiling(n/2)un ?
|
| « Last Edit: Sep 23rd, 2007, 7:47am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Sitting guests around a table
« Reply #3 on: Sep 23rd, 2007, 7:04am » |
Quote Modify
|
They invite Uncle Pete 
|
| « Last Edit: Sep 23rd, 2007, 8:28am by Eigenray » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Sitting guests around a table
« Reply #4 on: Sep 23rd, 2007, 7:50am » |
Quote Modify
|
on Sep 23rd, 2007, 6:13am, ThudanBlunder wrote:| Don't we have un+1 = Ceiling(n/2)un ? |
|
It could be, if you defined what un stands for.
|
| « Last Edit: Sep 23rd, 2007, 7:51am by Grimbal » |
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Sitting guests around a table
« Reply #5 on: Sep 23rd, 2007, 10:53am » |
Quote Modify
|
on Sep 23rd, 2007, 6:13am, ThudanBlunder wrote:| Don't we have un+1 = Ceiling(n/2)un ? |
|
Nope, that's not it. Misunderstood the question. (Wrong answer, anyway.)
|
| « Last Edit: Sep 23rd, 2007, 11:05am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Sitting guests around a table
« Reply #6 on: Sep 23rd, 2007, 11:28pm » |
Quote Modify
|
Shlafli?
|
| « Last Edit: Sep 23rd, 2007, 11:30pm by Barukh » |
IP Logged |
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: Sitting guests around a table
« Reply #7 on: Sep 24th, 2007, 11:34am » |
Quote Modify
|
Quote:
Not the way I did it, but thanks so much for the enormously interesting reference!
A note: it is actually spelled Schlafli, but Google is clever enough anyway.
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Sitting guests around a table
« Reply #8 on: Sep 24th, 2007, 2:35pm » |
Quote Modify
|
I have not the slightest idea what Schlafli* has to do with that.
Here is how I see it for 52 people:
Number the seats 1 to 52. When a switch is due, ask people at even seats to move +2, and people on odd seats to move -2. At the edges, do 3->1->2->4 and 50->52->51->49. Voila**! After 26 periods everybody had a chance to talk to everybody else.
I think the generalization is trivial.
* a is a-umlaut
** a is a-grave
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Sitting guests around a table
« Reply #9 on: Sep 24th, 2007, 3:05pm » |
Quote Modify
|
on Sep 24th, 2007, 2:35pm, Grimbal wrote:| Here is how I see it for 52 people: |
|
I don't understand. Can you give an example?
My idea was to solve it first for a prime number of people. But we can always add one more horse person, solve it, and then just ignore the 53rd person -- which has the effect of unfolding the table. So I thought it was the same as Grimbal's.
What does Schlafli have to do with it? Besides "Schlafli shuffle" being a good potential name.
|
| « Last Edit: Sep 24th, 2007, 3:11pm by Eigenray » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Sitting guests around a table
« Reply #10 on: Sep 24th, 2007, 3:21pm » |
Quote Modify
|
Let's show it with 10 people.
A J B I C H D G E F
J I A H B G C F D E
I H J G A F B E C D
H G I F J E A D B C
G F H E I D J C A B
|
| « Last Edit: Sep 25th, 2007, 12:55am by Grimbal » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Sitting guests around a table
« Reply #11 on: Sep 24th, 2007, 3:40pm » |
Quote Modify
|
Isn't this fact useful (probably what Grimbal was hinting at): Every complete graph K2n can be decomposed into edge disjoint hamiltonian paths
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Sitting guests around a table
« Reply #12 on: Sep 25th, 2007, 12:56am » |
Quote Modify
|
Sorry to disappoint you, but I don't know what you are talking about. 
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Sitting guests around a table
« Reply #13 on: Sep 25th, 2007, 6:38am » |
Quote Modify
|
on Sep 24th, 2007, 3:05pm, Eigenray wrote:| My idea was to solve it first for a prime number of people. |
|
Same for me.
Quote:| What does Schlafli have to do with it? |
|
Have you heard about Schlafli symbol for regular star polygons?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Sitting guests around a table
« Reply #14 on: Sep 25th, 2007, 7:02am » |
Quote Modify
|
I knew the notation, I didn't know the name of the notation.
I searched in that direction but with 52 people, so it didn't work out well. Then I remembered the idea of of how to make a group of people shake hands, while making sure every person shakes hands with everybody else: Make a flat loop with all the people, everybody shakes hands with the person opposite, and they proceed moving left, shaking hands as they pass.
Now I also can add a 53rd person by folding the line around the table and adding a non-moving person, maybe the King, in the gap.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Sitting guests around a table
« Reply #15 on: Sep 25th, 2007, 11:33am » |
Quote Modify
|
on Sep 25th, 2007, 12:56am, Grimbal wrote:| Sorry to disappoint you, but I don't know what you are talking about. |
|
No you haven't disappointed me 
I think you have in fact proved what I was talking about earlier in this thread...
|
| « Last Edit: Sep 25th, 2007, 11:33am by Aryabhatta » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Sitting guests around a table
« Reply #16 on: Sep 25th, 2007, 3:23pm » |
Quote Modify
|
I think I see now. But when you say "every complete graph K2n ..." isn't it 2k+1? And isn't there in fact only one?
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Sitting guests around a table
« Reply #17 on: Sep 25th, 2007, 4:04pm » |
Quote Modify
|
on Sep 25th, 2007, 3:23pm, Grimbal wrote:I think I see now. But when you say "every complete graph K2n ..." isn't it 2k+1? And isn't there in fact only one?
|
|
That statement is true for every n. (that is what every meant..).
If 2k+1 then hamiltonian path can be replaced by hamiltonian cycle. The statement you made (need not be a round table) is closer to hamiltonian path. Besides, K2n cannot be decomposed into edge disjoint hamiltonian cycles, only hamiltonian paths.
Your proof was valid for n=26 I think. (Sorry, if what I said came across as a proof for every n...)
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Sitting guests around a table
« Reply #18 on: Sep 26th, 2007, 12:47am » |
Quote Modify
|
Indeed, I am mixing up cycles and paths.
I said the table doesn't have to be round because I already had in mind the solution that I gave later.
|
| « Last Edit: Sep 26th, 2007, 12:49am by Grimbal » |
IP Logged |
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: Sitting guests around a table
« Reply #19 on: Sep 26th, 2007, 10:02pm » |
Quote Modify
|
My solution was the same as Eigenray et al's, and perhaps the thought processes were similar. I've devoted enough time to number theory that the nice cyclic properties of prime numbers are practically second nature to me.
What I found adorable was how the introduction of a totally foreign element (intuitively making the problem harder) reduced it to an easy form. This is very reminiscent of the story about the sultan who died and left 1/2, 1/3 and 1/9 of his **17** camels to his eldest, middle and youngest sons, respectively. Then, as they scratched their heads, along came a stranger on his own camel, and solved the problem!
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print