SUS Pokemon

You are a pokemon trainer and have just ordered a fresh batch of $n$ pokemon to help you

with various daily tasks. However, you know that some pokemon are liars. Your first task is

to figure out which of your $n$ pokemon are honest $($never lie$),$ and which are SUS $($may

sometimes lie$).$ Fortunately, the pokemon themselves know who are SUS, and thus you have

the following tool available to you: You may combine any two pokemon and have them

state whether the other pokemon is honest or SUS. An honest pokemon will always report

correctly what the other pokemon is$,$ but SUS pokemon may or may not tell the truth. Thus,

for any pair of pokemon $x$ and $Y$ that you test, you may conclude the following:

If $x$ and $Y$ each say the other is honest, then either both are honest, or both are SUS.

If $x$ says $Y$ is honest, but $Y$ says $x$ is SUS $($or vice$-$versa$),$ then at least one is SUS.

If $x$ and $Y$ each say the other is SUS, then at least one is SUS.

Show that if half or more of the pokemon are SUS, it is impossible to determine who the

honest pokemon are.

Assume that more than half of the pokemon are honest. Now consider the problem of

finding one single honest pokemon from the given $n$ pokemon. Design a way to reduce

this problem to at most half the size by applying roughly $\frac{n}{2}$ pokemon comparisons.

Apply the above technique to design a divide$-$and$-$conquer algorithm for identifying all

the honest pokemon in $O(n)$ pokemon comparisons. To analyze your run time, state and

solve a recurrence equation describing the maximum number of comparisons made by

your algorithm.