Intermission, the Sequel

Computer Science Level 5

You! You're the one who helped me build my previous theater addition, right? I hope you still have all that analysis mumbo jumbo you worked on because I'm building another theater and I need your help to size it again.

Little has changed since the last time, but I'll give recap of the facts you need to know anyway. Just a few things the PR people are making me brush up on... ugh. Can't stand those "fair-trade this", "fair-wages that" - you can give me numbers... I love numbers!

  • At each intermission in my theater, every theater-goer has a 1% chance of needing to get up for something. These people will all stand up in their densely-packed rows of seats.
  • Every one of these 1%-ers, which we'll call the 'givens', will need to get to the aisle. Unlike last time, though, we're going to have 2 aisles in this theater instead of 1, one aisle on each end of all the rows!
  • To get to the aisle, other customers will need to get up to let them out. We call these the 'forced'. Now, since each 'given' could choose to go to one of two aisles, the 'forced' aren't immediately obvious when the givens stand up. However, it turns out that all of my customers are really smart. The givens will direct themselves in such a way so that the smallest possible number of people in the row are 'forced'. For example, in a row of 4 people, if the person in the 2nd seat from the left has to get up (and no one else), he will go to his left, making for only 1 'forced', instead of to his right, which would make 2 customers 'forced'.
  • Corporate has changed the customer-happiness requirements. We're now considered 'doing well' if at most 10% of our customers are unhappy at intermissions - that is, if they are 'forced'. We're no longer counting givens towards this statistic.
  • So, I want to ensure, that at any given intermission, the probability that more than 10% of our customers are unhappy is, at most, 50%.

I have 25 rows to make in this new theater. I want to make these rows as many seats long as possible, whilst still obeying the customer happiness requirements set out by corporate above. How many seats long can I make all of these rows, and still obey the requirements?


  • It is highly reccommended you solve, or at least understand the solution to, the previous problem before trying to tackle this one.
  • All rows must be the same size.
  • Assume all seats are always filled. Don't worry about empty seats.
  • When computing 10% of customers, round down. So, for 5 columns of seats in the theater, we need to consider the probability that at most 12, not 13 customers are unhappy.

Image Credit:

Problem Loading...

Note Loading...

Set Loading...