Finding one special person among a hundred seems to require many checks. But a good question does more than give information: it also eliminates candidates.
The Invisible Celebrity
Riddle statement
At a party there are 100 people, and it is known that there is a celebrity with this property:
- everyone knows the celebrity;
- the celebrity knows no one.
You may ask questions of the form “A, do you know B?”
How can you identify the celebrity using only 99 questions?
Show solution
Solution
Yes, you can find a candidate with 99 questions.
Start with two people, A and B.
Ask:
“A, do you know B?”
If A says yes, then A cannot be the celebrity, because the celebrity knows no one. In that case, keep B as the possible celebrity.
If A says no, then B cannot be the celebrity, because everyone should know the celebrity. In that case, keep A as the possible celebrity.
With one question, you have eliminated one person.
Now compare the remaining candidate with a third person. One more question eliminates one of the two.
Repeat this process through all 100 people.
After 99 questions, only one possible candidate remains.
Since the statement guarantees that the celebrity exists, that candidate must be the celebrity.
Answer: yes. 99 questions are enough, eliminating one person with each question.