Yesterday, just after 2:00 am, almost falling asleep, I went through my twitter feed for a last time before making a move. It was not long before Steven Strogatz, an inspiring mathematician, writer, and Professor in Cornell (it is worth following him on twitter @stevenstrogatz), tweeted about his solution on the "Theater problem" also featured on this NYTimes blog article. The complete chapter "All About e" of his book "The Joy of x" has been released by the publisher "Houghton Mifflin Harcourt" (Richard Stallman would have said here, we support the authors not the publishers!).
Regardless of how you spell it*, the Theater or Theatre problem poses indeed an interesting problem, both from a theoretical point of view, as well as a computational! After reading his chapter, I was absolutely convinced there was no way to sleep before developing and running a simulation to see the results.
In short, imagine you have an amazing romantic movie showing in an initially empty theatre, and hundreds of couples are queued up outside the theater waiting to watch the movie. The couples get in and randomly start to occupy free seats. However, the couples want to cuddle while watching the movie, therefore, they will only allocate two spaces if they are adjacent. Otherwise, if there are no available adjacent seats then the theater stops selling tickets. Uh...and as you can imagine, the couples once they sit and cuddle, no one moves them! The question then is what percentage of seats will not be occupied owing to the random placement of the couples, and the inability to move them or split them to take full advantage of all the seats.
From the computational perspective, I developed in python a simulator that runs thousands of trials to verify the average vacant seats in the end when no available adjacent seats exist**. Additionally, I wanted to see a heatmap of how and where couples are distributed in the theater, and also study the effect of different size of group of people occupying the seats, e.g., friends of 3 or more. Below you can see a first run of a 20 x 20 theater, i.e., 400 seats, with couples (size of group = 2), for 1000 trials (click on the picture below for larger size). The colorbar shows how many times that seat has been occupied in the 1000 trials. I was happy to see that the calculated percentage of free seats is 0.148..., approximately close to the theoretical 1/e2 = 0.135... found in the chapter. Maybe with some optimizations and a bit of patience to run longer simulations, I will see better results.
The source code is available for anyone at https://bitbucket.org/gpierris/theaterproblem/src (requires numpy and pylab) or to clone the project
git clone This email address is being protected from spambots. You need JavaScript enabled to view it.:gpierris/theaterproblem.git
As you can tell from a random comment in the code below, I have not over-engineered it...
#Smart things can happen in the future. It is too late now and I am eager to get the results
If you find any bugs or ideas for improvement, feel free to contact me.
* Here is an amazing bonus tool for the thirsty reader regarding the convergence of "theater" and "theatre" in American English (Ngram)
** This problem reminds me of a really interesting problem to develop fast and optimal allocation strategies to maximize efficiency and reliability, e.g., finding free sectors in hard disks for Cloud Computing vendors.
