This is the archived website of SI 486H from the Spring 2016 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Problem 2

How many passengers to screen?

Due: January 19
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!