TOT 470 1995 Autumn J A4 n questions to find person Z among n persons
Source:
July 9, 2024
combinatorics
Problem Statement
A journalist is looking for a person at a meeting of persons. He has been told that knows all the other people at the meeting but none of them knows . 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 by asking less than questions?
(b) What is the minimal number of questions which are needed to find ? (G Galperin)