Lower bound for number of passengersDue: January 19
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.