MathDB

(470) 4

Part of 1995 Tournament Of Towns

Problems(1)

TOT 470 1995 Autumn J A4 n questions to find person Z among n persons

Source:

7/9/2024
A journalist is looking for a person ZZ at a meeting of nn persons. He has been told that ZZ knows all the other people at the meeting but none of them knows ZZ. The journalist may ask any person about any other person: “Do you know that person?” One person can be questioned many times. All answers are truthful.
(a) Can the journalist always find ZZ by asking less than nn questions? (b) What is the minimal number of questions which are needed to find ZZ?
(G Galperin)
combinatorics