Problem: Consider the challenge of determining whether a witness questioned by a law enforcement agency is telling the truth. An innovative questioning system pegs two individuals against each other. A reliable witness can determine whether the other individual is telling the truth. However, an unreliable witness's testimony is questionable. If we build a confusion matrix of all the possible outcomes from a given scenarios, we obtain the table in the attached image "Witness Reliability Confusion Matrix."
This pairwise approach could then be applied to a larger pool of witnesses. Answer the following:
1. Assume a pool of K witnesses, in which the reliable ones are eager to help solve a case, and the unreliable ones are equally eager to hide the truth. Prove that if more than half of the witnesses are unreliable, the approach outlined above cannot help identifying the reliable witnesses.
2. If at least half of the K witnesses are reliable, you are trying to identify one reliable witness. Prove that you can approximately half the size of the problem by conducting a number of floor(K/2) pairwise tests.
3. If at least half of the K witnesses are reliable, the number of pairwise tests needed is Θ(n). Show the recurrence relation that models the problem. Provide a solution using your favorite programming language, that solves the recurrence, using initial values entered by the user.