Problem 5

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

Lower bound for number of passengers

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.

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.