## Seating arrangements

Posted by Chris on November 24, 2010 – 4:47 am

Thirteen friends decide to go to the movies. In the theater there are rows of 13 seats. For 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.

How many different seating arrangements are possible?

November 24th, 2010 at 6:51 am

Is it 4096? i.e. 2 to the power of 12. Where ‘x’ is the given number of seats / people, the total number of arrangements is:

2 to the power of (x – 1)

November 24th, 2010 at 7:06 am

To those who believe it is 2^12 :

That means you (as I first did) thought that :

#2 could chose to be on the right or on the left

#3 could chose to be on the right or on the left

#4 could chose to be on the right or on the left

etc…

#13 could chose to be on the right or on the left

however, that means that we counted the possibility of everyone sitting on the left of the one before them. However there are 13 seats, and the #1 was in the middle…

November 24th, 2010 at 7:08 am

“could be in the middle” oops

November 24th, 2010 at 7:14 am

Oops again, I’m such a fool. 2^12 is correct because the first one choses wherever he sits… Sorry ^^’

November 24th, 2010 at 8:40 am

OVER 9000!!!!

November 24th, 2010 at 11:44 am

I agree with Karys answer, but disagree with the proof. It is too early to expose it myself, so I am still waiting for good arguments from the others

November 24th, 2010 at 12:07 pm

You’d need 15 seats to get over 9000 arrangements.

November 24th, 2010 at 1:27 pm

It is 2^12 = 4096, but prove it.

November 24th, 2010 at 1:51 pm

2*2=4

4*2=8

8*2=16

16*2=32

32*2=64

64*2=128

=256

=512

=1024

=2048

=4096

2^12 equals 4096.

November 24th, 2010 at 7:45 pm

chris, Spencer was referencing a Dragonball Z meme.

November 25th, 2010 at 2:36 am

Not that it necessarily proves it, but is a good example of Pascals triangle being put to use. Suppose there were 4 people and 4 seats. If person 1 sits in the far left seat, there is only one possible seating arrangement for all the other people. If person 1 sits in the next seat to the left, then there are 3 possibilities for the other 3 people. If person 1 sits in the next seat to the left, then again, there are 3 possibilities, and if he sits in the far right seat, there is only 1 possibility. The 1st 4 rows in Pascals triangle read:

1

11

121

1331

Just add up the numbers in the 4th row and you have 8, which is the same as 2 ^ (4-1). Sorry for using 4 as an example, but really couldn’t be asked to write out to the 13th row!

November 25th, 2010 at 4:21 pm

OK. This page has got too quiet.

There is a very painful way of doing this, and it might well involve Pascal’s triangle in a part of it. Then there’s a rather nice and easy way.

Do it all backwards, and unseat the friends. Starting with all 13 seats full, the last one to sit must have taken the leftmost or rightmost seat – that’s two possibilities. Get rid of him and we’re left with the original problem but for 12 friends. The next one must have taken the right or leftmost seat – again two possibilities. Get rid of him and we have the original problem but with 11 seats. Etc.

When it comes to the 13th friend, he has no choice (free-will doesn’t work backwards!)

So that gives 2*2*2*2*2*2…*2*1 (12 2’s) = 2^12 ways of unseating.

But unseating simply corresponds to seating in the opposite order (like watching a film of them doing it, but running it backwards).

So 2^12 = 4096 it is.

November 25th, 2010 at 6:08 pm

Hi Chris.Your explanation is pretty good. However, we still have to imagine the whole process backwards. It was a bit confusing for me at first as you say that the last guy must have taken the end seats, whereas, in our case the last person has only 1 seat to take. On the other hand, I have an easier way to explain i dare say.

I had begun solving by the traditional method……the first guy has 13 seats to choose from, then the next guy has two….

However this method fails as we have to subtract a lot of cases when one end of the row gets filled so that the remaining seats get occupied in sequence.

I hadn’t found the solution myself. And then you asserted that 2^12 was the answer. This meant that there was no “13″ term in the solution. So I racked my brains and found out how to get to the answer. An this is how I did it:

Lets just forget the seats for a minute….

Firmly grip the first guy. Hold him still.

Place the next person on either side of the first. So there are two possibilities….

Put the third on either side of the duo……and so on….

In the end we have total combinations of 2^12.

Once this is done, we have 13 people seating in a line.

Now carefully lift the array of people that we have obtained n place them in the 13 seats. And there you have it !!

November 25th, 2010 at 6:33 pm

Hi Rohan. That’s a pretty good way of doing it too. Perhaps it’s not quite so obvious (to me) that it’s valid as my way is, but I can see it’s right as all possible cases must have been covered. I agree that going forwards is neater.

I probably took a couple of day cracking that the first time I came across it.

November 26th, 2010 at 2:33 am

Hi Rohan. As I said before – you solution is not correct, because it leads to the conclusion that no matter where the first guy sits, there are always the same number of different admissible permutations for the group (which is clearly not the case – take the first one to sit at the end of the row). The trick is that one should use recursion and express the possible permutations for n people by the corresponding number for n-1, as Chris did. His solution is correct but indeed a little bit difficult to follow.

The way I solved the problem is the following: We don’t care what happens after the first one takes his seat, but wait until the second one does so, too. Then we just “glue” the two guys and there seats and consider them as only one person/seat (this we can do, because they are neighbors). We see that we are back to the case of 12 people, where only the first one took his seat. This seat can be arbitrary, so from now on we have as many different outcomes as for 12 people, instead of 13. However, this double seat can be occupied in two different ways: either the first guy sits to the left of the second one, or vice verse. Thus, we conclude that the number of different permutations for 13 people is just twice the number of different permutations for 12 people. Now we continue the recursion downwards until we reach 1 person, where there is only one way for him to sit, and conclude by induction that for 13 people we have 2^12 combinations. This is similar to Chris’ solution but there are some slight differences.

November 26th, 2010 at 11:13 am

Hi slavy. In my model, i dont know where my first person will be seated. That gets decided only when all the 13 friends take their positions in the line. I think even in your method, one cannot tell where the 1st person is seated,in the beginning itself, amongst the friends glued together.

In my method, getting the first guy at an extreme end is a rare case as i can have 11 guys placed on the right side of the previous person. However, the last person too needs to take the seat on extreme right. That’s the only case when i have the 1st person on extreme left and the others sitting in a sequence.

If the last guy chooses to sit on the left, the 1st person will take the second seat.

In most cases, the 1st person will be somewhere in the middle.

I think my model to be similar to yours. Instead of taking a group of 12 people n the last guy as you did, bring him too into the group so that we have a group of 13 people glued together.

November 26th, 2010 at 2:35 pm

Hi slavy. I like your gluing idea too.

But I have to side with Rohan. Because he has necessarily covered every permutation, he has inherently covered the fact that the first bloke could have sat anywhere. I accept that Rohan didn’t explicitly comment on that aspect of his solution. That you explicitly dealt with that aspect of the solution seems to be the only real difference.

I like my solution best as it sneakily sidesteps the problem of the original sitter.

November 26th, 2010 at 3:44 pm

Hi Rohan and Chris. I agree that Rohan has the idea, but the wording in the exposition is what bothers me and I can tell you that on an exam or mathematical olympiad it will cost him half of the points on the problem

November 26th, 2010 at 5:46 pm

Hi slavy, I realise that I’m being unusually generous and I also agree that in an exam that Rohan would have been heavily penalised. My solution also failed to explicitly address that the first one to seat was properly dealt with.

Just to be mean, I notice that you don’t seem to have dealt with the case of what happens when there is no left (or right) seat remaining. After that there is only one choice of where to sit for the remaining people and the recursion has been broken. I had read your solution too quickly when I last commmented on it.

November 26th, 2010 at 7:22 pm

8192

November 27th, 2010 at 2:57 am

Hi Chris. This is the beauty of the recursive argument. I don’t care where exactly the first two people sit and exactly to how many different solutions their particular positions lead. I just show that there is a one to one correspondence between a couple of permutations for 13 people with a single permutation for 12 people, i.e., I built a 2 to 1 function from the bigger space (13 people) to the smaller one (12 people) which guarantees the answer. In the case when the “glued” couple is at the end of the raw, there is only one case for the reduced problem with 12 people as well, so the recursion deals nicely with it. And this is exactly the moment where Rohan’s solution seams vague and incomplete, because he just talks about “most cases” and “usually” which are not good words in mathematics.

November 27th, 2010 at 8:34 am

Hi slavy. I agree that your solution is good and doesn’t have the “fault” that I thought it had.

November 28th, 2010 at 10:54 am

4096 is not the ancer u forgot the 1st one has 13 seats to chose from its 4,109 or its eather 53,248

November 28th, 2010 at 12:18 pm

Hi lewis. We didn’t forget anything, 4096 is the correct answer as has been shown (and not merely asserted) by three people (on this page).