Where do I sit? ...
Thirteen friends decide to go to the movies. In the theater, there are rows of 13 seats. For fun (or some stupid reason) they decide that the first person to enter the row may sit wherever he chooses. The second person must sit on either side of him with no empty seat between. The third person may sit on either side of the first two as long as no empty seat is between them. This procedure continues until all are seated.
Remembering that the first person may choose any of the seats, how many different seating arrangements are possible?
Remembering that the first person may choose any of the seats, how many different seating arrangements are possible?
posted by Zaux at
6:48 PM
17 Comments:
Should be 2^12 = 5096 arrangements :)
Hi Anonymous ... you got it ... except 2¹² = 4096 ... :-)
Zaux...come on...you let anonymous off the hook...i would have said "try again" and made him/her work for it :]
Knightmare, I was feeling generous :-)
I'll be. I just tried that by trial and error. Stopped at 5 seats case. Sure does look like 2^(n-1) where n is the number of seats (even true for n = 1).
I've been trying to knock up fiendishly elaborate combinatorial proofs, and I hadn't thought to try simulating by hand, until I saw the result.
Anonymous, how did you do it?
How would you go about figuring out that it was 2^12?
I realize that in most situations most of the remaining 12 people have 2 seats to choose from. But I don't understand how it adds up with all the times people have just one seat to choose from.
This post has been removed by the author.
I confirmed the answer by trying it on a piece of paper and
checking the hard way for up to 5 seats. I then put my faith
in the formula. To save space I'll do it for up to 5 seats.
1; 12,21; 123,213,312,321
1234,2134,3124,4123,3214,4213,4312,4321
12345,21345,51234,31245,41235,43125,53124,54123,
52134,42135,32145,54312,54213,53214,43215,54321
This post has been removed by the author.
I haven't really come up with a good algrebraic way of doing it.
If you think about flipping a coin, then with 13 throws, you'd expect 2^13 possible sequences. That's because each toss is allowed to be heads or tails. Here though you don't have two choices afer a while, and that obviously is going to have a large negative impact on 2^13. But, the first friend can initiate 13 different ways of doing the counting, and that altogether has cost us a factor of 2 against the coins.
Working backwards. Just for this I'll consider a 5 seat system. use 0 for empty, 1 for in use.
The problem always ends at 11111. The previous state must have
been 01111 or 11110 (that's 2 possibilities). Either way, we effectively have 1111. For next move could be 0111 or 1110 (that's 2 ways) to get to 111. 2 more ways to get to 11, 2 more to get to 1, and then only one choice left.
So, for the first n-1 seats, we get 2 choices. That gives us 2^(n-1) possible ways to (un)fill the seats.
Good one Zaux.
That's really spooky. Trying to do it forwards seems fraught with difficulty. I'd even invented a notation to try to solve it. Yet unfilling the seats (which is exactly the same problem in combinatorics) is an absolute doddle.
I've had a look using a decision tree. But seem to end up drilling to the bottom, and then all the way up again. Very much messier looking than the above. But I made some pretty pictures ☺
I had a different logic on this and did a "brute force", very short routine, and got 4096 also.
S = "A"
For c = 66 To 77
J = Rnd()
If J < 0.5 Then
S = S & Chr(c)
Else
S = Chr(c) & S
End If
Next c
I had the routine add the string to a table where the string had to be unique. Result: 4096 cases
If first person (call him "A") sits in the first seat how many combinations then?
What if he sits the the second seat?
How many for each of the 13 seats?
Pos A...Combinations
1...... 1
2...... 12
3...... 66
4...... 220
5...... 495
6...... 792
7...... 924
8...... 792
9...... 495
10..... 220
11......66
12......12
13......1
a good ploblem to demonstrate Double Counting
as Ragknot showed.
when 1-th person sits at n-th seat
you can select any n-1 people from the rest 12 people
to sit on the,assumingly, left side and
each selection can be permuted only one way.
and the right side is automatically fixed.
that's C(12,n-1) , where n can be 1-13.
sum up , it's gonna be
C(12,0) + C(12,1) + ... + C(12,12) = 2^12
(big help from Binomial Theorem)
or you can working backwards , like Chris,
and get 2^12 without any calculation or cases division.
Post a Comment
Links to this post:
Create a Link
<< Home