(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 sucient 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 identied with (n) pairwise tests. Give and solve the recurrence (as always, in O or notation) that describes the number of tests.

3. (30 pts total) The Dementors have captured n prisoners, of dubious morals and dubious reliability. The Ministry of Magic needs your help to identify which prisoners can be relied on to tell the truth, and which cannot. To this end, they have developed a spell that can be cast on a pair of prisoners at a time. When the spell is cast, the two prisoners each say whether the other prisoner is truthful or a liar. A truthful prisoner always gives the coTrect answer -that is, correctly identifies whether the other prisoner is truthful or a liar -but anything one of the lying prisoners says cannot be trusted That is, lying prisoners can lie whenever they want, but they don't necessarily always make false statements. Furthermore, the spell has the useful property that if it is cast on the same two prisoners repeatedly, they will always give the same answers they gave initially (hence why a spell is needed) You quickly notice that there are four possible outcomes to the spell, when cast on prisoner 1 says przsoner says "j is a liar" "j is a liar" is truthful"->at least one is a liar "j is truthful"'i is a liar"at least one is a liar "j is truthful""i is truthful"> both truthful, or both liars "i is a liar"at least one is a liar (a) (10 points) Prove that if n/2 or more prisoners are liars, the Ministry cannot necessarily determine which prisoners are truthful using any strategy based on this kind of pairwise test. Assume a worst-case scenario in which the lying prisoners contain a psychic link that they can use to collectively conspire to fool the Ministry