Couples going to the movies
From the book and hyperlink, the puzzle:
Imagine there’ s a very popular new movie showing at the local theater.It’ s a romantic comedy, and hundreds of couples (many more than the theater can accommodate) are lined up at the box office, desperate to get in.Once a lucky couple get their tickets, they scramble inside and choose two seats right next to each other.To keep things simple, let’ s suppose they choose these seats at random, wherever there’ s room.In other words, they don’ t care whether they sit close to the screen or far away, on the aisle or in the middle of a row.As long as they’ re together, side by side, they’ re happy.Also, let’ s assume no couple will ever slide over to make room for another.Once a couple sits down, that’ s it.No courtesy whatsoever.Knowing this, the box office stops selling tickets as soon as there are only single seats left.Otherwise brawls would ensue.At first, when the theater is pretty empty, there’ s no problem.Every couple can find two adjacent seats.But after a while, the only seats left are singles\[LongDash]solitary, uninhabitable dead spaces that a couple can’ t use.In real life, people often create these buffers deliberately, either for their coats or to avoid sharing an armrest with a repulsive stranger.In this model, however, these dead spaces just happen by chance.The question is : When there’ s no room left for any more couples, what fraction[or approximate fraction, if you' re estimating] of the theater’ s seats are unoccupied?
The solution (fraction of empty seats) approaches as number of seats approaches infinity. I found the solution at this site instructive. Utilizing generating functions to solve recurrence relations for expected number of empty seats the author derives the expected number of empty seats (for equivalent fat people on a bar stool puzzle):
, so fraction of empty seats approaches as .
I have tried to simulate this problem. I get similar expectations (using 100, 1000, 10000) but they are consistently lower than expected from the relation above and consequently the fraction. I am still contemplating why.
In the meantime I append a visualization of 40 seats in a row filled by a rainbow of people (couples) ’at random’ using my simulation. Black represents empty seats. The animation holds for 4 seconds for the last seating.