wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Sitting guests around a table
        
(Message started by: Pietro K.C. on Sep 23^rd, 2007, 1:49am)

Title: Sitting guests around a table
Post by Pietro K.C. on Sep 23^rd, 2007, 1:49am

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.

Title: Re: Sitting guests around a table
Post by Grimbal on Sep 23^rd, 2007, 5:40am

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

[hide]But I believe it doesn't have to be a round table.[/hide]

Title: Re: Sitting guests around a table
Post by ThudanBlunder on Sep 23^rd, 2007, 6:13am

Don't we have [hide]u_n+1 = Ceiling(n/2)u_n [/hide]?

Title: Re: Sitting guests around a table
Post by Eigenray on Sep 23^rd, 2007, 7:04am

They [hide]invite Uncle Pete[/hide] [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_whathappened;action=display;num=1061392480]:D[/link]

Title: Re: Sitting guests around a table
Post by Grimbal on Sep 23^rd, 2007, 7:50am

on 09/23/07 at 06:13:57, ThudanBlunder wrote:

Don't we have [hide]u_n+1 = Ceiling(n/2)u_n [/hide]?

It could be, if you defined what u_n stands for.

Title: Re: Sitting guests around a table
Post by ThudanBlunder on Sep 23^rd, 2007, 10:53am

on 09/23/07 at 06:13:57, ThudanBlunder wrote:

Don't we have [hide]u_n+1 = Ceiling(n/2)u_n [/hide]?

Nope, that's not it. Misunderstood the question. (Wrong answer, anyway.)

Title: Re: Sitting guests around a table
Post by Barukh on Sep 23^rd, 2007, 11:28pm

Shlafli?

Title: Re: Sitting guests around a table
Post by Pietro K.C. on Sep 24^th, 2007, 11:34am

Quote:

Shlafli

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.

Title: Re: Sitting guests around a table
Post by Grimbal on Sep 24^th, 2007, 2:35pm

I have not the slightest idea what Schlafli* has to do with that.

Here is how I see it for 52 people:
[hide]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.[/hide]

* a is a-umlaut
** a is a-grave

Title: Re: Sitting guests around a table
Post by Eigenray on Sep 24^th, 2007, 3:05pm

on 09/24/07 at 14:35:29, 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 [hide]a prime number of people[/hide]. But we can always [hide]add one more ~~horse~~ person, solve it, and then just ignore the 53rd person -- which has the effect of unfolding the table[/hide]. 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.

Title: Re: Sitting guests around a table
Post by Grimbal on Sep 24^th, 2007, 3:21pm

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

Title: Re: Sitting guests around a table
Post by Aryabhatta on Sep 24^th, 2007, 3:40pm

Isn't this fact useful (probably what Grimbal was hinting at): [hide] Every complete graph K_2n can be decomposed into edge disjoint hamiltonian paths[/hide]

Title: Re: Sitting guests around a table
Post by Grimbal on Sep 25^th, 2007, 12:56am

Sorry to disappoint you, but I don't know what you are talking about. :-/

Title: Re: Sitting guests around a table
Post by Barukh on Sep 25^th, 2007, 6:38am

on 09/24/07 at 15:05:38, Eigenray wrote:

My idea was to solve it first for [hide]a prime number of people[/hide].

Same for me.

Quote:

What does Schlafli have to do with it?

Have you heard about Schlafli symbol for regular star polygons (http://en.wikipedia.org/wiki/Star_polygon#Regular_star_polygons)?

Title: Re: Sitting guests around a table
Post by Grimbal on Sep 25^th, 2007, 7:02am

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.

Title: Re: Sitting guests around a table
Post by Aryabhatta on Sep 25^th, 2007, 11:33am

on 09/25/07 at 00:56:37, Grimbal wrote:

Sorry to disappoint you, but I don't know what you are talking about. :-/

No you haven't disappointed me ;D

I think you have in fact proved what I was talking about earlier in this thread...

Title: Re: Sitting guests around a table
Post by Grimbal on Sep 25^th, 2007, 3:23pm

I think I see now. But when you say "every complete graph K_2n ..." isn't it 2k+1? And isn't there in fact only one?

Title: Re: Sitting guests around a table
Post by Aryabhatta on Sep 25^th, 2007, 4:04pm

on 09/25/07 at 15:23:16, Grimbal wrote:

I think I see now. But when you say "every complete graph K_2n ..." 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, K_2n 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...)

Title: Re: Sitting guests around a table
Post by Grimbal on Sep 26^th, 2007, 12:47am

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.

Title: Re: Sitting guests around a table
Post by Pietro K.C. on Sep 26^th, 2007, 10:02pm

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!