ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 98278
Темы:    [ Математическая логика (прочее) ]
[ Теория алгоритмов ]
[ Ориентированные графы ]
Сложность: 4-
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

В компанию из n человек пришёл журналист. Ему известно, что в этой компании есть человек Z, который знает всех остальных членов компании, но его не знает никто. Журналист может к каждому члену компании обратиться с вопросом: "Знаете ли вы такого-то?"
  а) Может ли журналист установить, кто из компании есть Z, задав менее n вопросов?
  б) Найдите наименьшее количество вопросов, достаточное для того, чтобы наверняка найти Z, и докажите, что меньшим числом вопросов обойтись нельзя.
(Все отвечают на вопросы правдиво. Одному человеку можно задавать несколько вопросов.)


Решение

  а) Вот пример стратегии, приводящей к цели. Сначала журналист выбирает произвольных членов компании А и B. Человеку А он задаёт вопрос: "Знаете ли вы B?" Из ответа "да" следует, что B не Z. Из ответа "нет" следует, что А не Z. Итак, один вопрос задан и один человек отброшен – в дальнейшем не нужно задавать вопросы ни ему, ни о нём. Продолжая в том же духе, мы отбросим  n – 1  человека, задав  n – 1  вопрос. Остаётся один человек. Он и есть Z.

  б) Докажем, что необходимо задать не менее  n – 1  вопроса.
  Пусть на некотором шаге опроса человека А спросили, знает ли он B. В случае ответа "да" будем считать B отмеченным, в случае ответа "нет" будем считать А отмеченным. Про отмеченного мы уже знаем, что он не Z, так как либо он кого-то не знает, либо его кто-то знает. После того как заданы все вопросы (их не больше, чем  n – 2),  неотмеченных людей будет не меньше двух.
  Пусть X – один из тех, кто остался неотмеченным. В результате заданных вопросов мы уже обладаем некоторыми сведениями о том, кто кого знает. Изменим систему знакомств так, чтобы все имеющиеся сведения сохранились и при этом X стал Z. Для этого сделаем так, что X знает всех, а в остальных случаях (кроме тех, которые выяснились в результате заданных вопросов) установим, что никто никого не знает.
  Итак, для любого из неотмеченных (X был взят среди них произвольно) можно изменить систему знакомств так, что именно он будет Z. А это и означает, что заданных вопросов недостаточно для выяснения того, кто есть Z.


Ответ

а) Может.  б)  n – 1.

Замечания

Баллы: 3 + 3

Источники и прецеденты использования

web-сайт
задача
журнал
Название "Квант"
год
Год 1996
выпуск
Номер 2
Задача
Номер М1540
олимпиада
Название Турнир городов
Турнир
Дата 1995/1996
Номер 17
вариант
Вариант осенний тур, основной вариант, 8-9 класс
Задача
Номер 4

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .