Problem 4

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

In the "airplane bomber" scenario, we are assuming that:

- There are 200 passengers total.
- At least 20 passengers must collude to make a bomb.
- At least 999 out of 1000 times, not a single passenger will have any bomb-making liquid.

With this in mind, we came up with the following randomized algorithm:

- Randomly choose n passengers to screen.
- If none of the n has any bomb liquid, let the plane fly.
- If
any oneof the n has any bomb liquid, check all 200 passengers.

Determine the number of passengers n that must be screened in order to ensure that the probability that the plane is successfully bombed is less than one in a million. Try to make n as small as possible. Show your work!