Subscribe via feed.

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?


This post is under “MathsChallenge, Tom” and has 24 respond so far.
If you enjoy this article, make sure you subscribe to my RSS Feed.

24 Responds so far- Add one»

  1. 1. Dave Said:

    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)

  2. 2. Karys Said:

    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…

  3. 3. Karys Said:

    “could be in the middle” oops

  4. 4. Karys Said:

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

  5. 5. Spencer Said:

    OVER 9000!!!!

  6. 6. slavy Said:

    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 ;)

  7. 7. Chris Said:

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

  8. 8. Chris Said:

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

  9. 9. Spencer Said:

    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.

  10. 10. Jappa Said:

    chris, Spencer was referencing a Dragonball Z meme.

  11. 11. Dave Said:

    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!

  12. 12. Chris Said:

    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.

  13. 13. Rohan Said:

    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 !!

  14. 14. Chris Said:

    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.

  15. 15. slavy Said:

    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.

  16. 16. Rohan Said:

    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.

  17. 17. Chris Said:

    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.

  18. 18. slavy Said:

    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 :(

  19. 19. Chris Said:

    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.

  20. 20. azee Said:

    8192

  21. 21. slavy Said:

    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.

  22. 22. Chris Said:

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

  23. 23. lewis Said:

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

  24. 24. Chris Said:

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

Post a reply




PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0