Question: 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.
Answer:
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