How can I tell who is a truth teller and who is a liar? This is a problem that I was given for my data structures and algorithms class. I am not sure how to tackle this problem. Can I get some assistance?


  At Hogwarts a new shipment of $n$ goblins has arrived.  To be of any use, a goblin must be completely truthful (never lies).  Unfortunately, not all of the $n$ goblins in the shipment are truth tellers.  Only some are truth-tellers, and some are deceivers.  It is your task to design an algorithm to separate the truth-teller goblins from the deceiver goblins.  To do this, you have one tool available:  You may combine any two goblins and have them state whether the other goblin is a truth-teller or a deceiver.  A truth-teller will always say correctly what the other goblin is, but a deceiver may lie (but also may sometimes tell the truth to REALLY confuse you).  For any two goblins that you test, the following can be concluded from the goblin responses:
  
  $$
\begin{array}{ccc}
\text{Goblin A says} &amp;
\text{Goblin B says} &amp;
\text{Conclusion} \\\hline
\text{B is a truth-teller} &amp;
\text{A is a truth-teller} &amp;
\text{both are truth-tellers or both are deceivers} \\
\text{B is a truth-teller} &amp;
\text{A is a deceiver} &amp;
\text{at least one is a deceiver} \\
\text{B is a deceiver} &amp;
\text{A is a truth-teller} &amp;
\text{at least one is a deceiver} \\
\text{B is a deceiver} &amp;
\text{A is a deceiver} &amp;
\text{at least one is a deceiver}
\end{array}
$$
  
  
  Show that if more than $n/2$ goblins are deceivers, it is impossible to determine which goblins are the truth-tellers using only the pairwise testing strategy.
  Consider the problem of identifying $1$ truth-teller goblin.  Show that if we assume that more than $n/2$ of the goblins are truth-tellers, then the problem of finding a single truth-teller from $n$ goblins can be reduced to a problem of about half the size using $n/2$ goblin comparisons.
  Use a recurrence equation to show that if more than half of the goblins are truth-tellers, then the truth-tellers can all be identified within $O(n)$ goblin comparisons.
Here are some hints to get you started. Admittedly, this question isn't that easy.

Part (a): Suppose that there are exactly $n/2$ truth-tellers and $n/2$ deceivers. Show that the deceivers have a strategy in which what a goblin A says about a goblin B depends only on whether they both have the same nature. Draw the conclusions.

Part (b): Pair the goblins up. Show that for some pairwise responses, it is safe to get rid of both goblins. Explain why it is useful to have a majority of truth-tellers.

Part (c): This part should be clear enough.