Hacker Challenge: Prune and Search

In this lesson, we will employ the prune and search technique to solve a knights and knaves problem.

The “Hacker Challenge” lessons throughout the course are optional and can be skipped. However, they would help strengthen the respective concepts.

Knights and knaves

On a faraway island, there are a total of $100$ tribesmen. Every tribesman on this island is either a knave (Faker) or a knight (Trustworthy). We need to figure out who is a Faker and who is a Trustworthy person. We can ask each of the tribesmen questions about who is Trustworthy and who isn’t. Moreover, we can ask as many questions as we want. The only information known is that the number of knights is greater than the number of knaves.

Directions to look at the challenge

We need to find at least one Trustworthy person whom we can ask " who is a knight (Trustworthy) or knave (Faker)?" One way to find a Trustworthy person would be to take one out and ask everyone, “Is he the Trustworthy one?” If the majority say “yes”, then we have found the Trustworthy person, and we may ask him about everyone. But the issue is we could be unlucky. In that case, we might have to choose the 2nd person and repeat, which would be a terrible solution. It will work, but we might select $49$ bad choices of Fakers in this case. And for each Faker, we have asked $100$ questions. Therefore, this technique may require us to ask $4900$ questions in the worst-case scenario. Too many questions! Can we solve it with fewer of questions?

Now the idea is to make pairs of 2, each (resulting in $50$ pairs, i.e., $N/2$ pairs) and ask those pairs about each other. Using these pairs, we can find the possible answers (F for Faker, T for Trustworthy).

Case 1	Case 2	Case 3
F	T	T
F	F	T

In all those $50$ pairs where Cases 1 and 2 arise, we reject those pairs. In Case 3, we choose one representative and ask the other person in the pair to sit down.

We have pruned more than half of the people with this process. Now we repeat the same process of shrinking, and in the worst case, the number of questions will look like the following series $100 + 50 + 25 + … + 1$ and that will always be less than $200$ questions. Hence we have found one Trustworthy person in around 200 questions.

Be careful with this procedure. It may be possible that there is an odd number of people remaining on a particular step. What should we do in that case? We have to think about that. The hint is in incorporating that issue. We might have to perform some extra steps, which might take the number of questions close to $300$.

Solution

First of all, we’ll pair them as guided above and ignore those pairs where either of the partners has accused the other of being a Faker, as losing them will not affect the fact that there are more Trustworthy people than Fakers. Case 3 can lead to two possibilities – both are Fakers, or both are Trustworthy people. Hence, we cannot take risk of losing by skipping Case 3.

In the first iteration, 100 questions will be asked from each tribesman and as a result, we can have a max of $25$ Case 3 pairs. For the next step, we’ll pick $1$ person from each pair such that the number of Trustworthy people will still be greater. We’ll repeat this process until there is only 1 person left in the final step who will be Trustworthy.

Suppose there is an odd number of tribesmen. In that case, the person who cannot be tagged in either pair will be presented before the rest of the tribesmen in that step so that we can take their verdict regarding his trustworthiness. If the majority says he is a knight, we have found what we were looking for.

Therefore, for this case, the number of questions asked will be twice of those who are in pairs.

Hence, we solved the problem using the prune and search technique. The number of questions asked will be: $\space 100+50+24+24+12+6+2+2 \approx 300$

---

Geometric Series

The geometric series is one of the essential topics in mathematics and exists in abundance in nature and also in computational related problems in computer science. An example of the this series could be: $1+2+4+8+16+...+ \frac{N}{4} + \frac{N}{2} + N$ also written as $N + \frac{N}{2} + \frac{N}{4} + \frac{N}{8} + … + 16 + 8 + 4 + 2 + 1$. The sum of geometric series $N+\frac{N}{2}+\frac{N}{4}+...+1$ is always bounded by $2N$. Here’s the visual proof of this claim.

Using the prune and search technique, we have tried to design an algorithm in which the pruning process yields a reduced search space geometrically. Hence the overall cost of searching is bounded by just the constant multiple of the first pruning step (like in the above example of searching a knight, the pruning process was half, and it yielded the total cost bounded by twice the cost of the first pruning step).