|
|
 |
Условие
В компанию из 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
