Problem

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:

Goblin A says B is a truth-teller, Goblin B says A is a truth-teller => both are truth tellers, or both are deceivers

Goblin A says B is a truth-teller, Goblin B says A is a deceiver => at least one is a deceiver

Goblin A says B is a deceiver, Goblin B says A is a truth-teller => at least one is a deceiver

Goblin A says B is a deceiver, Goblin B says A is a deceiver => at least one is a deceiver

1. 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.
2. Consider the problem of identifying 1 truth-teller goblin. Show that if we assume that at least 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.
3. Use a recurrence equation to show that if at least half of the goblins are truth-tellers then truth-tellers can all be identified within O(n) goblin comparisons.

Solution

1. The problem states that n is the number of total goblins. Let t be the number of truth tellers, and the number of deceivers be d = n - t. From this assumption we can create 2 sets, each of size of t; let the set of truth-tellers be T and the set of deceivers be D. Now assume that the goblins in set D will always answer "T is a deceiver" and "D is a truth-teller" (lie in both cases), and the goblins in set T will always tell the truth. As you can tell by this assumption, T will always answer "truth-teller" when paired with another T, and answer "deceiver" when paired with a D. Therefore, the goblins will mirror answers and make it difficult to figure out what goblin is a deceiver or truth teller.
2. The algorithm is as follows: Pair the goblins, and ask them the question. If both answers aren't "Goblin X is a truth-teller" then eliminate the pair; the remaining (n-2) goblins still have a majority of true goblins. Now you are left with pairs in which you know for a fact that they are both truth tellers, or both deceivers. Remove 1 goblin from each pair, as they have have the same nature. Repeat the algorithm (recursively) until only 1 or 2 goblins remain, which are all truth tellers.
3. Let T(n) be the comparisons needed in n goblins. The algorithm results in the recurrence of T(n/2)+n/2 as you split the problem in half every time, and then have to compare all the goblins in groups of 2. Solving the recurrence gives T(n) = O(n). Now to know which goblins are truth tellers just grab the goblin(s) that you for sure know are truth tellers, and walk through all the goblins asking that truth goblin what the other goblin is. Walking through all the goblins give a runtime of O(n). total runtime => O(n) + O(n) = O(2n) = O(n)