3
$\begingroup$

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} & \text{Goblin B says} & \text{Conclusion} \\\hline \text{B is a truth-teller} & \text{A is a truth-teller} & \text{both are truth-tellers or both are deceivers} \\ \text{B is a truth-teller} & \text{A is a deceiver} & \text{at least one is a deceiver} \\ \text{B is a deceiver} & \text{A is a truth-teller} & \text{at least one is a deceiver} \\ \text{B is a deceiver} & \text{A is a deceiver} & \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.
$\endgroup$
  • $\begingroup$ I am telling the truth. $\endgroup$ – Andrej Bauer Nov 11 '13 at 8:06
  • $\begingroup$ I am telling the lie. $\endgroup$ – avi Nov 11 '13 at 15:55
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.