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.

How many passengers to screen?

Due: January 11
Points: 2

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:

  1. Randomly choose n passengers to screen.
  2. If none of the n has any bomb liquid, let the plane fly.
  3. If any one of 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!