Question: b 12 points suppose the ministry knows that strictly more...
(b) (12 points) Suppose the Ministry knows that strictly more
than n/2 of the prisoners are truthful, but not which ones. Prove
that bn/2c pairwise tests are suﬃcient to reduce the problem to one
of nearly half the size.
(c) (8 points) Now, under the same assumptions as part (3b), prove that all of the truthful prisoners can be identiﬁed with Θ(n) pairwise tests. Give and solve the recurrence (as always, in O or Θ notation) that describes the number of tests.