Intermission

Python 3.3:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

from random import random
from time import time
rows = 25
def ten_got_up(seats):
    got_up = 0
    customers = seats * rows
    for row in range(rows):
        for seat in range(seats, 0, -1):
            if random() < 0.01:
                got_up += seat
                break
    return got_up/customers > 0.1
def satisfied(seats):
    goals = 0
    trials = 0
    end = time() + 1
    while time() < end:
        if not ten_got_up(seats):
            goals += 1
        trials += 1
    return goals/trials >= 0.5
seats = 1
# simulate smallest seat cases and add more seats
# until customers are unsatisfied
while satisfied(seats):
    seats += 1
seats -= 1
print("Answer:", seats)

This problem has no closed form solution that I have yet discovered - if someone else finds one, please do post!

There is no shortcut to the answer here. One might be tempted to reduce the problem to a single row and find the answer there, but it turns out this doesn't work, since the distribution of how many people get up in a single row is not uniform. For instance, if we change the problem to be for $15$ rows, the answer becomes $22$ instead of $21$ , and if we go up to $50$ rows, the answer shrinks down to $20$ !

We need to figure out, for a given number of seats per row, the probability that more than 10% of customers will be required to stand up, given the parameters of the problem. Then, we need to find the maximum parameter for this function that yields a probability < 50%. The problem statement implies that this function is monotonically increasing, which makes our job easier, and we'll see this as we ferret out our solution. (Though, unfortunately, I don't have a proof for this... proofs welcome!)

We'll use dynamic programming to compute the probability for arbitrary $c$ , the number of columns of seats, or seats per row, in the theatre. First, we observe that the number of people that get up in any one row is independent of all the other rows. Let $p$ , the probability that an arbitrary individual is a 'given', be $\frac{1}{100}$ , and let $P(x)$ be the probability that, in an arbitrary row, exactly $x$ people need to get up (that is, they are 'givens', or 'forced'). Thus:

$P(0) = (1-p)^c$

$P(1) = (1-p)^{c-1} * p$

$P(2) = (1-p)^{c-2} * p$

$...$

$P(c-2) = (1-p)^2 * p$

$P(c-1) = (1-p)^1 * p$

$P(c) = (1-p)^0 * p$

$P(c)$ is thus trivially computable. Now, let's recurse: Define $f(r,c,m)$ to be the probability that, in a theater of $r$ rows and $c$ columns, at most $m$ customers are forced to stand at intermission. The following python-sketch-code computes f:

def f(r,c,m):
  if r == 0:
    # No rows left, nothing to compute
    return 1
  sum = 0
  for n in [0, min(c,m)]:
    # For each possible number (n) of people that
    # got up in this row, take the probability of
    # such an event, and multiply it by the
    # probability that (m-n) people get up in
    # subsequent rows.  This covers all possible
    # eventualities without double-counting.
    sum += P(n) * f(r-1, c, m-n)
  return sum

By using $(r, c, m)$ as a unique key, we can cache the results of $f(r,c,m)$ to turn this into a dynamic programming solution, which does $O(C)$ computations for each of $O(mR)$ dynamic states, where $R$ is the number of rows, $25$ in this case. For a given fixed $c$ , and uninitialized cache, this yields $O(c * m * R)$ computations, which is on the order of thousands, or tens of thousands, for $c$ at $10$ or $20$ . Less efficient solutions will likely spawn far less tractible numbers.

The probability that more than 10% of customers will have to get up in a theater with $c$ seats per row is thus $1 - f(25, c, \left\lfloor \frac{25c}{10} \right\rfloor)$ . It suffices to compute this function from $c = 1$ upwards, until we observe the probability cross the 50% threshold.

$1- f(25, 21, \left\lfloor \frac{25*21}{10} \right\rfloor) = 0.4924951$

$1 - f(25, 22, \left\lfloor \frac{25*22}{10} \right\rfloor) = 0.5200529$

So, we answer 21 .

A really slow python program:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

PEOPLE_PER_ROW = 22
NB_ROWS = 25

TOTAL_SEATS = NB_ROWS * PEOPLE_PER_ROW

MAX_STANDING = int(0.1 * TOTAL_SEATS)

def fact(n):
        if n < 2:
                return 1
        return reduce(lambda x,y:x*y, xrange(1,n+1))

FNB = fact(NB_ROWS)

def tabToDict(t):
        d = {}
        last = None
        for v in t:
                if v == last:
                        d[v] += 1
                else:
                        d[v] = 1 
                        last = v 
        return d

def getParts(total):
        parts = [p for p in getParts_0(total, PEOPLE_PER_ROW) if len(p) <= NB_ROWS]
        return map(tabToDict, parts)

def getParts_0(total, maxNb):
        if total == 0:
                return [ [] ]
        if total == 1:
                return [ [1] ]
        parts = []
        for first in xrange(1, min(maxNb, total) + 1): 
                for subparts in getParts_0(total - first, first):
                        parts += [ [first] + subparts ]

        return parts


percent = 0 

# p people who have to stay,
for p in xrange(0, MAX_STANDING + 1): 
        for parts in getParts(p):
                nbParts = sum(parts.values())
                percent += FNB / fact(NB_ROWS - nbParts) / reduce(lambda x,y:x*y, map(fact, parts.values()), 1) * 0.01**nbParts * 0.99**(TOTAL_SEATS - p)

print PEOPLE_PER_ROW, ":", percent