wu :: forums - Print Page


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

        riddles >> easy >> Musical Chairs
        
(Message started by: THUDandBLUNDER on May 6^th, 2003, 11:51pm)

Title: Musical Chairs
Post by THUDandBLUNDER on May 6^th, 2003, 11:51pm

N children wait to take their seats in the same row in a movie theatre. There are exactly N seats in the row.
They decided that after the first person sits down, the next person has to sit next to the first. The third sits
next to one of the first two, and so on until all N are seated. The first person can choose any of the N seats.

In how many different ways can this be accomplished?

Title: Re: Musical Chairs
Post by wowbagger on May 7^th, 2003, 2:09am

My answer is [hide]2^N-1[/hide].

I arrived at it by constructing a recursion formula. And applying some algebra, as always.

Nice one. :)

Title: Re: Musical Chairs
Post by R on Jun 25^th, 2009, 6:48am

I have two doubts.
What do you exactly mean by "next to some person"? If 1^st person is sitting on seat number 5, 2nd person can sit on either 4^th or 6^th. Or is it strictly next, i.e. only on 6^th.
Second doubt is that, are you taking the row, circular. I mean, If 1^st person is sitting on n-th seat. The 2nd person can sit on either 1^st or (n-1)^th seat or only on (n-1)^th seat.

With my interpretation of the problem, (next means adjacent, either 4^th or 6^th AND the row is circular.) I got the answer [hide]2^N-1N[/hide].

Title: Re: Musical Chairs
Post by Eigenray on Jun 25^th, 2009, 7:35am

How many movie theaters do you know that have circular rows?

An easy way to see the formula : [hide]suppose they line up first before filing into the theater[/hide].

Title: Re: Musical Chairs
Post by 1337b4k4 on Jun 26^th, 2009, 2:03pm

This reminds me of
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1222196222;start=5#5

I'm not sure I see Eigenray's easy way to see the formula

Title: Re: Musical Chairs
Post by towr on Jun 26^th, 2009, 3:03pm

on 06/26/09 at 14:03:37, 1337b4k4 wrote:

I'm not sure I see Eigenray's easy way to see the formula

[hide]Start at the back of the line.[/hide]

[hide]The last person can only end up at either end of the row. Remove that seat, and the same consideration applies to the second last. And so on.[/hide]

Title: Re: Musical Chairs
Post by rmsgrey on Jun 27^th, 2009, 1:52pm

on 06/26/09 at 14:03:37, 1337b4k4 wrote:

I'm not sure I see Eigenray's easy way to see the formula

[hideb]
Before entering the theatre, line up by taking the first child to start the line, then adding each child in turn to one end or the other of the line. Each possible way of lining up like this corresponds to exactly one way of sitting in the theatre, and each way of sitting in the theatre corresponds to exactly one way of lining up outside.

Since lining up outside avoids having to worry about the ends of the row of seats, it's easy to see that the n-1 independent choices of which end to add the next child give 2^n-1 possible orders

In the original problem, the number of seats each child could sit in depended on where the previous children had sat - giving you a sum of combinatorials: SUM_{i=1 to n} (_n-1C^i-1) - the number of ways of choosing the children to sit to the right of the first...[/hideb]

Title: Re: Musical Chairs
Post by R on Jun 28^th, 2009, 1:31am

on 06/25/09 at 07:35:16, Eigenray wrote:

How many movie theaters do you know that have circular rows?

The row are not actually circular. I think I've explained what I meant by circular row. It is the way they sit. If 1st person is sitting on the n-th seat, can 2nd one sit on 1st/(n-1)th seat or just on (n-1)th seat not on the 1st seat.
In case, if 2nd person cannot consider the row circular, he will not have 1st seat as an option and will have to sit on (n-1)th seat. The choices will be less for others too, and number of ways they all can sit will be lesser.

Quote:

An easy way to see the formula : [hide]suppose they line up first before filing into the theater[/hide].

Couldn't extract the answers to my questions.

on 06/26/09 at 15:03:08, towr wrote:

[hide]Start at the back of the line.[/hide]

[hide]The last person can only end up at either end of the row. Remove that seat, and the same consideration applies to the second last. And so on.[/hide]

Ok. That clears my doubts. The row is not considered circular. And "next" means, "adjacent".
Thank you towr.

Title: Re: Musical Chairs
Post by Eigenray on Jun 28^th, 2009, 4:07am

I think there is only one reasonable interpretation of the problem: There are N seats in a row, and next to means next to.

There is no order given on the seats, so "the next" seat does not make sense. But even if it did, that interpretation would make the problem completely trivial.

Anyway, if the seats (N>1) were arranged in a circle, there would be N*2^N-2 ways, since the last person has no choice to make.

(When the seats are arranged in a row, we are counting the number of unimodal permutations : a permutation with exactly one local maximum (or minimum, in this case). This is determined by picking which subset will be to the left of the first person, with the rest on the right.)

Title: Re: Musical Chairs
Post by R on Jun 28^th, 2009, 4:14am

on 06/28/09 at 04:07:34, Eigenray wrote:

There is no order given on the seats, so "the next" seat does not make sense.

In a theater, seats are numbered.

Quote:

Anyway, if the seats (N>1) were arranged in a circle, there would be N*2^N-2 ways, since the last person has no choice to make.

Yeah, right. Missed the last-person's-choices. Thanks.