Problem 2 with variablesDue: January 26
In the "airplane bomber" scenario, assume that:
- There are \(q\) passengers total.
- At least \(r\) passengers must collude to make a bomb.
- With probability at least \(p\), not a single passenger will have any bomb-making liquid.
So \(q,r\) are integers with \(1 \le r \le q\), and \(p\) is a real number with \(0 \le p \le 1\).
Now our randomized algorithm is, given some very carefully-chosen constant \(n\):
- Randomly choose \(n\) passengers to screen.
- If none of the \(n\) has any bomb liquid, let the plane fly.
- If any one of the \(n\) has any bomb liquid, check all \(q\) passengers.
Determine a formula for \(n\) based on \(q\), \(r\), and \(p\), that is simple to compute AND which guarantees that the probability that the plane is successfully bombed is less than one in a million. Use your formula to come up with a big-O bound on \(n\) in terms of \(q\), \(r\), and \(p\). Choose your formula so that the big-O bound is as small as possible.