This is a pretty specific problem but I think it can help me understand better the whole concept of the subject.

A doctor in the hospital is in charge of 20 medical students. For every patient, the doctor consults with the students rather the patient has a problem. Each student can either say "yes", "no" or "Don't know".

The doctor builds a decision tree based on the answers of the students in period of two months. It is known that one of the students that answered the questions is an imposter, and all of his answers are based and opposite of another student the he picked. When the "real" student answered "yes", the imposter answered "no" and vice versa. When the "real" one answered "I don't know" so did the imposter. Also it is known that every real student is giving a decisive answer - "yes" or "no" for at least 60% of the cases.


  • Give an algorithm to find the imposter.

  • A tree was built again without the imposter's answers. Prove it is the same as the old tree.

I understand that the information gain of the imposter and the real student he based his answers on is the same. So the algorithm needs to find groups of students with the same information gain. Within those groups, find two students with answered all reversed. The one who is wrong more than 60% of the time will be the imposter.

Regarding the second task I'm not sure why it is true. Thinking of a case of a patient where all the students answered "I don't know" except for one student who answered "yes" and the imposter who answered "no". Isn't it possible that the new tree will classify this patient as "yes" instead of "no", now when the imposter is gone?


1 Answer 1


Maybe I'm not interpreting the scenario correctly, but task 1 seems impossible and task 2 easier than you've made it sound.

I'm reading it as a sample for each patient, with one feature for each student, possible values yes/no/dunno.

In that case, at any split of the decision tree the imposter and the chosen real student will split the data in the same fashion. If either of them is chosen as the split criteria, then it's random which of the two is used, but if we remove the imposter first, then the real student will be used; but there is not difference in the way the samples are split.

As for finding the imposter, all you can do AFAICT is look for pairs who give exactly opposite responses. But if there are multiple such pairs, I don't see how to pick one, and even when you have a pair of opposites, I don't see any way to determine which is real and which is imposter. The 60% figure seems to just indicate that nobody answers "I don't know" too often. I guess we can make an additional assumption that the students are better-than-random, so that the imposter is worse?

  • 1
    $\begingroup$ Yes, you are completely right about everything you said. I forgot to mention this required assumption for task 1, and I understand now how the tree remains the same. $\endgroup$
    – user39808
    Jan 29, 2019 at 9:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.