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?