Author |
Topic: Musical Chairs (Read 829 times) |
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
 |
Musical Chairs
« on: May 6th, 2003, 11:51pm » |
 Quote  Modify
|
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?
|
| « Last Edit: May 6th, 2003, 11:53pm by ThudnBlunder » |
 IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
wowbagger
Uberpuzzler
 
Gender:
Posts: 727
|
|
Re: Musical Chairs
« Reply #1 on: May 7th, 2003, 2:09am » |
Quote Modify
|
My answer is 2N-1.
I arrived at it by constructing a recursion formula. And applying some algebra, as always.
Nice one. 
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Musical Chairs
« Reply #2 on: Jun 25th, 2009, 6:48am » |
Quote Modify
|
I have two doubts.
What do you exactly mean by "next to some person"? If 1st person is sitting on seat number 5, 2nd person can sit on either 4th or 6th. Or is it strictly next, i.e. only on 6th.
Second doubt is that, are you taking the row, circular. I mean, If 1st person is sitting on n-th seat. The 2nd person can sit on either 1st or (n-1)th seat or only on (n-1)th seat.
With my interpretation of the problem, (next means adjacent, either 4th or 6th AND the row is circular.) I got the answer 2N-1N.
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Musical Chairs
« Reply #3 on: Jun 25th, 2009, 7:35am » |
Quote Modify
|
How many movie theaters do you know that have circular rows?
An easy way to see the formula : suppose they line up first before filing into the theater.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Musical Chairs
« Reply #5 on: Jun 26th, 2009, 3:03pm » |
Quote Modify
|
on Jun 26th, 2009, 2:03pm, 1337b4k4 wrote:| I'm not sure I see Eigenray's easy way to see the formula |
|
Start at the back of the line.
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
   
Gender:
Posts: 2873
|
|
Re: Musical Chairs
« Reply #6 on: Jun 27th, 2009, 1:52pm » |
Quote Modify
|
on Jun 26th, 2009, 2:03pm, 1337b4k4 wrote:| I'm not sure I see Eigenray's easy way to see the formula |
|
| hidden: |
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 2n-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: SUMi=1 to n (n-1Ci-1) - the number of ways of choosing the children to sit to the right of the first... |
|
|
IP Logged |
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Musical Chairs
« Reply #7 on: Jun 28th, 2009, 1:31am » |
Quote Modify
|
on Jun 25th, 2009, 7:35am, 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 : suppose they line up first before filing into the theater. |
|
Couldn't extract the answers to my questions.
on Jun 26th, 2009, 3:03pm, towr wrote:
Start at the back of the line.
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.
|
|
Ok. That clears my doubts. The row is not considered circular. And "next" means, "adjacent".
Thank you towr.
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Musical Chairs
« Reply #8 on: Jun 28th, 2009, 4:07am » |
Quote Modify
|
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*2N-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.)
|
|
IP Logged |
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Musical Chairs
« Reply #9 on: Jun 28th, 2009, 4:14am » |
Quote Modify
|
on Jun 28th, 2009, 4:07am, 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*2N-2 ways, since the last person has no choice to make.
|
|
Yeah, right. Missed the last-person's-choices. Thanks.
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print