Решение задачи 274

Условие:

В компании из n человек есть "шпион" - человек, который знает всех, но его не знает никто. Вы можете спросить любого человека из компании про любого другого человека, знает ли он его или нет, и получить честный ответ. За какое наименьшее число вопросов можно найти "шпиона" в этой компании?

Решение:

Оценка:

Заметим, что каждым вопросом мы можем исключить ровно одного человека из "кандидатов на шпиона". Действительно, если мы спросили у "человека A", знает ли он "человека B" и получили положительный ответ, то "человек B" точно не является "шпионом", поскольку "шпиона" не знает никто. Если мы получили отрицательный ответ, то "человек А" не является "шпионом", поскольку "шпион" знает всех. Таким образом нужно задать хотя бы n-1 вопрос.

Пример:

Занумеруем всех людей числами от 1 до n. Считаем, что до начала опроса в "кандидаты на шпиона" входят все люди. Дальше будем действовать следующим образом.

На первом шаге спрашиваем у первого, знает ли он второго. Если ответ положительный, то выкидываем второго из "кандидатов на шпиона".

Иначе выкидываем из "кандидатов на шпиона" первого.

После первого шага получаем новую группу "кандидатов": (1,3,4,...,n) либо (2,3,4,...,n). Перенумеруем их числами от 1 до n-1.

Далее повторяем вышеописанное действие ещё n-2 раза.

Таким образом, после последнего шага останется только один "кандидат", который и будет являться шпионом.

Ответ: n-1