6 (8 pts). Buffalo Police is investigating an organized crime organization. Based on initial information, n suspects have been identified. But due to incomplete evidence, the suspects include both innocent people (good guys), and true criminals (bad guys). Detective Robert is assigned the task of determining all good and bad guys. The only technique available to him is: Interview suspects in pairs together, (say A and B), then ask (privately) A if B is good or bad; and ask (privately) B if A is good or bad. The answer from a bad guy cannot be trusted (sometimes they lie, sometimes they tell truth, you never know). Fortunately for Robert, we know that the good guys always tell the truth. Thus the four possible outcomes of an interview session are as follows: We assume the following Condition I holds: Condition I: More than n/2 suspects are good, (which means strictly bigger than n/2 suspects are good.) (For example, if n=1000, then 501 suspects are good. If n=999 then 500 suspects are good.) Under this assumption, solve the following two problems. (1) Describe an algorithm that will find a good guy among the n suspects. First, show that n/2 pairwise interview sessions are sufficient to reduce the problem to one of nearly half the size. Then show that a good guy can be identified by using at most n pairwise interviews. (2) Describe an algorithm that identifies all good and bad guys by using at most additional n pairwise interview sessions. Note: It can be shown that (not required), if the Condition I does not hold, this task is impossible in general. Hint: The algorithm proceeds in "rounds". In the first round, Roberts conducts a set of pairwise interviews. Depending on the outcomes, he determines a set of suspects to be interviewed in the next round. Continue this process, until a good guy is identified. Note that Condition I plays a critical role in the solution. You need carefully analyze the situation to make sure the Condition I holds for each round. It is particularly tricky when n is odd