Boys and Girls


Eleven boys and girls wait to take their seats in the same row in a movie theater. There are exactly 11 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 eleven are seated. In other words, no person can take a seat that separates him/her from at least one other person. How many different ways can this be accomplished? Note that the first person can choose any of the 11 seats.

For Solution SCROLL DOWN...


There are 1024 different ways.

This is the type of Brain Teaser that can be solved using the method of induction. If there is just a one person and one seat, that person has only one option. If there are two persons and two seats, it can be accomplished in 2 different ways. If there are three persons and three seats, it can be accomplished in 4 different ways. Remember that no person can take a seat that separates him/her from at least one other person. Similarly, four persons and four seats produce 8 different ways. And five persons with five seats produce 16 different ways. It can be seen that with each additional person and seat, the different ways increase by the power of two. For six persons with six seats, there are 32 different ways. For any number N, the different possible ways are 2(N-1)

Thus, for 11 persons and 11 seats, total different ways are 210 i.e. 1024


John Emmanuel Chiramel said...

2 ways only if they start from the edge / 1024 ways to do it.
(sitting order is considered)

Jayant said...

P(1) = 1
P(n) = 2*P(n-1), n > 1

If a new member is added, then he can either sit on the extreme left of the already seated group, or to the extreme right...

Anonymous said...

Amiable dispatch and this post helped me alot in my college assignement. Thanks you seeking your information.

Anonymous said...

It is a shame that you have 'proven' this with a method sometimes referred to as the Engineers Induction (it holds for P(2), it holds for P(3), so it holds for P(n) with n > 1). Jayant indeed provides an informal but nonetheless true proof to this problem: Since there are no open spaces between the boys and girls, each of the possible permutations of n persons would be situated either at the left side of the n + 1 theatre leaving a place at the extreme right or vice versa for the new person to sit down. So each of the permutations of n would provide two permutations at n + 1.

In no way disrespect was meant though, I love puzzles like this!

vageesha jajur said...

guys i couldm' understand this 2(n-1) means how it 210 come and how its 1024 comes..
5 persons 5 seats how it is 16..

Can you please explain me..

TechnoPrabhu said...

hey Vageesha,
its 2^10 [2 raised to the power of 10].