Разделы 
Дополнительно
Задача по математике - 1406
2018-12-13 
В компании из $n$ человек есть «шпион» - человек, который знает каждого члена этой компании, но его не знает никто из них. Вы можете спросить любого из членов компании про любого другого человека, знает он его или нет, и получить честный ответ. Сможете ли вы выявить «шпиона», задав $(n - 1)$ вопрос?
Решение:
Первый способ. Выберем произвольным образом двух человек и спросим у одного из них про другого. В случае положительного ответа, тот, о ком спрашивали - не «шпион», в случае отрицательного - тот, кого спрашивали - не «шпион». Значит, одного человека можно исключить из числа «подозреваемых» и их останется $(n - 1)$. Повторяя эту операцию, мы на каждом «шаге» будем уменьшать количество «подозреваемых» на одного. Таким образом, после того, как будет задано $(n - 1)$ вопросов, останется один «подозреваемый», который и является «шпионом».
Метод, использованный при доказательстве, называется «методом спуска».
Второй способ. Докажем утверждение методом математической индукции, присвоив членам компании номера от 1 до $n$. Для $n = 2$ утверждение очевидно. Пусть утверждение верно для компании, в которой $(n - 1)$ человек. Спросим первого человека, знает ли он человека с номером $n$. Если знает, то человек с номером $n$ - не «шпион». Тогда, по предположению индукции, мы сумеем найти «шпиона» среди людей с номерами от 1 до $n -1$, задав $(n - 2)$ вопроса. Если же первый не знает $n$-го, то первый - не «шпион», значит, задав $(n - 2)$ вопроса, мы сумеем найти «шпиона» среди людей с номерами от 2 до $n$. Таким образом, задав $(n - 1)$ вопрос, можно выявить «шпиона».
Отметим, что меньшим количеством вопросов выявить «шпиона» невозможно. Доказать это можно, например, так. За любой вопрос мы сможем получить следующую информацию: не более, чем про одного человека узнать, что он не «шпионь и увеличить количество людей, которых знает второй человек, не более, чем на 1. «Шпион» будет найден в одном из двух случаев: 1) если мы выяснили, что количество людей, которых знает какой-то человек, равно $(n - 1)$; 2) если мы выяснили, что $(n - 1)$ человек не являются «шпионами». За один вопрос каждый из этих параметров увеличивается не более, чем на 1, поэтому, и вопросов потребуется не менее, чем $(n - 1)$.
Ответ: да.
В компании из $n$ человек есть «шпион» - человек, который знает каждого члена этой компании, но его не знает никто из них. Вы можете спросить любого из членов компании про любого другого человека, знает он его или нет, и получить честный ответ. Сможете ли вы выявить «шпиона», задав $(n - 1)$ вопрос?
Решение:
Первый способ. Выберем произвольным образом двух человек и спросим у одного из них про другого. В случае положительного ответа, тот, о ком спрашивали - не «шпион», в случае отрицательного - тот, кого спрашивали - не «шпион». Значит, одного человека можно исключить из числа «подозреваемых» и их останется $(n - 1)$. Повторяя эту операцию, мы на каждом «шаге» будем уменьшать количество «подозреваемых» на одного. Таким образом, после того, как будет задано $(n - 1)$ вопросов, останется один «подозреваемый», который и является «шпионом».
Метод, использованный при доказательстве, называется «методом спуска».
Второй способ. Докажем утверждение методом математической индукции, присвоив членам компании номера от 1 до $n$. Для $n = 2$ утверждение очевидно. Пусть утверждение верно для компании, в которой $(n - 1)$ человек. Спросим первого человека, знает ли он человека с номером $n$. Если знает, то человек с номером $n$ - не «шпион». Тогда, по предположению индукции, мы сумеем найти «шпиона» среди людей с номерами от 1 до $n -1$, задав $(n - 2)$ вопроса. Если же первый не знает $n$-го, то первый - не «шпион», значит, задав $(n - 2)$ вопроса, мы сумеем найти «шпиона» среди людей с номерами от 2 до $n$. Таким образом, задав $(n - 1)$ вопрос, можно выявить «шпиона».
Отметим, что меньшим количеством вопросов выявить «шпиона» невозможно. Доказать это можно, например, так. За любой вопрос мы сможем получить следующую информацию: не более, чем про одного человека узнать, что он не «шпионь и увеличить количество людей, которых знает второй человек, не более, чем на 1. «Шпион» будет найден в одном из двух случаев: 1) если мы выяснили, что количество людей, которых знает какой-то человек, равно $(n - 1)$; 2) если мы выяснили, что $(n - 1)$ человек не являются «шпионами». За один вопрос каждый из этих параметров увеличивается не более, чем на 1, поэтому, и вопросов потребуется не менее, чем $(n - 1)$.
Ответ: да.
