On a mountain, there are honest monkeys and unreliable monkeys. The honest monkeys always tell the truth while the unreliable monkeys may lie or may tell the truth. The monkeys themselves can tell who is honest and who is unreliable, but an outsider can’t tell the difference. Suppose that there are n monkeys on the mountain, and there are strictly more than n/2 honest monkeys. Could you give an algorithm to find out all honest monkeys by asking them whether others are honest?
I have considered the problem for some time and tried some search engines but still got no idea.
I was stimulated by comment! I can asked other monkeys whether the first monkey is reliable. If honest >n/2,it must be honest. If unreliable >n/2,it must be unreliable. When I find the first honest monkey, I can ask it whether others are honest. But this method will reach O(n^2) when I continuously find out unreliable monkeys. Is there an algorithm that can reach O(n)?