Олимпиадный вопрос по математике Задача №5.
На станции за южным полярным кругом было 8 исследователей, но одного из них подменил пришелец из космоса. Каждый человек знает, кто пришелец, но слишком напуган чтобы говорить правду. Инспектор, который прибыл на станцию чтобы выявить опасного инопланетянина, может выделить любую группу людей (не меньше двух) и тайно опросить всю группу, то есть спросить у каждого из них, есть ли среди них пришелец. Люди на этот вопрос ответят правду, а пришелец может ответить правду, а может солгать. За какое наименьшее количество опросов инспектор может гарантированно определить пришельца?
Варианты ответа:
(A) 2
(Б) 3
(B) 4 (Γ) 5
(Д) 8
Олимпиадный вопрос по математике Задача №5.
На станции за южным полярным кругом было 8 исследователей, но одного из них подменил пришелец из космоса. Каждый человек знает, кто пришелец, но слишком напуган чтобы говорить правду. Инспектор, который прибыл на станцию чтобы выявить опасного инопланетянина, может выделить любую группу людей (не меньше двух) и тайно опросить всю группу, то есть спросить у каждого из них, есть ли среди них пришелец. Люди на этот вопрос ответят правду, а пришелец может ответить правду, а может солгать. За какое наименьшее количество опросов инспектор может гарантированно определить пришельца?
Варианты ответа:
(A) 2
(Б) 3
(B) 4 (Γ) 5
(Д) 8
На станции за южным полярным кругом было 8 исследователей, но одного из них подменил пришелец из космоса. Каждый человек знает, кто пришелец, но слишком напуган чтобы говорить правду. Инспектор, который прибыл на станцию чтобы выявить опасного инопланетянина, может выделить любую группу людей (не меньше двух) и тайно опросить всю группу, то есть спросить у каждого из них, есть ли среди них пришелец. Люди на этот вопрос ответят правду, а пришелец может ответить правду, а может солгать. За какое наименьшее количество опросов инспектор может гарантированно определить пришельца?
Варианты ответа:
(A) 2
(Б) 3
(B) 4 (Γ) 5
(Д) 8
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Проблема состоит в том, что инспектор должен идентифицировать пришельца среди 8 исследователей, которые, хоть и знают, кто пришелец, не могут говорить правду. Нам нужно понять, сколько наименьших опросов нужно, чтобы определить пришельца.
Рассмотрим, что если инспектор проведет опрос группы людей, то каждый из исследователей, который не является пришельцем, будет говорить правду. Однако пришелец может как подтвердить, что он пришелец, так и солгать, что затрудняет задачу.
Стратегия, которую можно использовать, включает в себя разделение группы на подгруппы и опрос их.
Первый опрос: Инспектор может разделить исследователей на две группы по 4 человека. Предположим, первая группа - это исследователи 1, 2, 3, 4, а вторая - 5, 6, 7, 8. Инспектор спрашивает первую группу, есть ли среди них пришелец. Если все отвечают "нет", пришелец находится во второй группе. Если кто-то отвечает "да", пришелец в первой группе.
Второй опрос: После этого инспектор знает, в какой из групп находится пришелец. Теперь он может разделить эту группу на 2 подгруппы по 2 человека и спросить их, есть ли среди них пришелец.
Третий опрос: Инспектор получит аналогичные ответы, позволяя ему далее сузить круг поиска. Так, если он проверит 1 и 2, и один из них отвечает "да", то пришелец среди них, в противном случае - пришелец в 3 и 4.
После этих шагов инспектор должен провести минимум 3 опроса, чтобы гарантированно выделить пришельца.
Таким образом, наименьшее количество опросов, после которых инспектор может гарантированно определить пришельца, равно 3.
Ответ: Б (3).