Probability challenge: At the Movies?

If we call r_i the number of empty seats in the i-th row, so that r1 is the number of empty seats in the first row, r2 the number of empty seats in the second row, ...., r10 the number of empty seats in the last row, then we can find a formula for

..............................i=10

P[ r1, r2, ..., r10 ] = ∏ C(10, r_i) / C(100,25)

...............................i=1

( with C(n,k) = n!/((n-k)!k!) notation for combinations)

The problem is that there are 44,289,256 possibilities for the r_i so that they sum up to 25. So, we cannot treat this manually on paper but a computer program can calculate them in 1 second execution time.

This is not the end of the story however. Once we have calculated the odds for the 44 M possibilities, we must calculate the odds for 3 adjacent seats in each case. Note that we need to have at least 3 seats free in a row of course in order to be a candidate for adjacent seats. When we have at least 8 seats free in a row, the row is guaranteed to have 3 adjacent seats. The intermediate cases of 3, 4, 5, 6 or 7 free seats need to be treated and are not so difficult. When we have 3 free seats then the odds that the row has 3 adjacent free seats are

8 C(7,7) / C(10,3). When we have 4 free seats, then the odds are (7 C(6,5) + 7)/ C(10,4) and so on ...

The odds that a configuration (r1,r2,...,r10) yields 3 adjacent free seats are then

1 - (1-p1)(1-p2)....(1-p10)

with p_i = P[ row i yields 3 adjacent free seats ].

I ran the program in C and the odds should be 0.65391.

So there is 65.391 % chance to find 3 adjacent seats.

Here is the program listing :

#include<stdio.h>

double nrgood[11];

int min(int n, int m)

{

if (m<n) return m; else return n;

}

double fac(int n)

{

double res = 1.0;

int i;

for(i=1;i<=n;i++) res *= (double) i;

return res;

}

double C(int n, int k)

{

return fac(n)/(fac(n-k)*fac(k));

}

int init_p_adjacent()

{

int i,nrfree,three_adjacent;

int c[10];

for(i=0;i<=10;i++) nrgood[i] = 0.0;

for(c[0]=0;c[0]<=1;c[0]++)

for(c[1]=0;c[1]<=1;c[1]++)

for(c[2]=0;c[2]<=1;c[2]++)

for(c[3]=0;c[3]<=1;c[3]++)

for(c[4]=0;c[4]<=1;c[4]++)

for(c[5]=0;c[5]<=1;c[5]++)

for(c[6]=0;c[6]<=1;c[6]++)

for(c[7]=0;c[7]<=1;c[7]++)

for(c[8]=0;c[8]<=1;c[8]++)

for(c[9]=0;c[9]<=1;c[9]++)

{

nrfree = 0;

for(i=0;i<=9;i++) nrfree += c[i];

three_adjacent = 0;

for(i=0;i<=7;i++)

{

if ((c[i]==1) && (c[i+1]==1) && (c[i+2]==1)) three_adjacent = 1;

}

nrgood[nrfree]+= (double) three_adjacent;

}

return(1);

}

int main(void)

{

int r[10];

int i;

double cc,p,p2,totp=0.0;

double c2[11];

init_p_adjacent();

cc = C(100,25);

for(i=0;i<=10;i++) c2[i] = C(10,i);

for(r[0]=0;r[0]<=10;r[0]++)

for(r[1]=0;r[1]<=10;r[1]++)

for(r[2]=0;r[2]<=min(10,25-r[0]-r[1]);r[2]++)

for(r[3]=0;r[3]<=min(10,25-r[0]-r[1]-r[2]);r[3]++)

for(r[4]=0;r[4]<=min(10,25-r[0]-r[1]-r[2]-r[3]);r[4]++)

for(r[5]=0;r[5]<=min(10,25-r[0]-r[1]-r[2]-r[3]-r[4]);r[5]++)

for(r[6]=0;r[6]<=min(10,25-r[0]-r[1]-r[2]-r[3]-r[4]-r[5]);r[6]++)

for(r[7]=0;r[7]<=min(10,25-r[0]-r[1]-r[2]-r[3]-r[4]-r[5]-r[6]);r[7]++)

for(r[8]=0;r[8]<=min(10,25-r[0]-r[1]-r[2]-r[3]-r[4]-r[5]-r[6]-r[7]);r[8]++)

{

r[9] = 25-r[0]-r[1]-r[2]-r[3]-r[4]-r[5]-r[6]-r[7]-r[8];

if ((r[9]>=0) && (r[9]<=10))

{

p = 1.0;

for(i=0;i<=9;i++) p *= c2[r[i]];

p /= cc;

p2 = 1.0;

for(i=0;i<=9;i++) p2 *= (1.0 - nrgood[r[i]]/c2[r[i]]);

p2 = 1.0 - p2;

p *= p2;

totp += p;

}

}

printf("P = %5.5f\n", totp);

return 0;

}

I also wrote a Monte Carlo simulation with random numbers generation and the results confirmed the theoretical result. I ran 100 million (100 M) test cases and 65,394,453 of them had 3 adjacent free seats. This took 1 minute execution time so the theoretical case is faster and completely exact.