![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Поиск знаменитости
Mar. 8th, 2012 09:57 pmНазовем участника компании знаменитостью, если его знают все остальные в этой компании, а он не знает никого из остальных.
В компании 8 человек. Обратившись к любому из них, мы можем задать ему вопрос вида "Знаете ли Вы такого-то?" и получить ответ. Пользуясь такими вопросами, мы хотим выяснить, есть ли в этой компании знаменитость, и если да, то найти ее.
а) Докажите, что нам хватит 20 вопросов
б) Придумайте способ достичь той же цели за 18 вопросов
в)* Докажите, что 17 вопросов может не хватить.
В компании 8 человек. Обратившись к любому из них, мы можем задать ему вопрос вида "Знаете ли Вы такого-то?" и получить ответ. Пользуясь такими вопросами, мы хотим выяснить, есть ли в этой компании знаменитость, и если да, то найти ее.
а) Докажите, что нам хватит 20 вопросов
б) Придумайте способ достичь той же цели за 18 вопросов
в)* Докажите, что 17 вопросов может не хватить.
