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 3

Lower bound for number of passengers

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.

Prove that any deterministic algorithm that screens at most 180 passengers (even in a single case) may result in 1/1000 planes being blown up.