Классическая логическая задача о трёх неизвестных, где один всегда говорит правду, другой всегда лжёт, а третий может говорить и так, и сяк, — одна из самых популярных на математических олимпиадах и собеседованиях. Ниже подробно разберёмся, как методично «вычислить» аборигенов и пришельцев, если перед вами стоят именно три человека, каждый из которых может быть либо аборигеном (всегда правдив), либо пришельцем (всегда лжёт).
Формулировка задачи
Перед судом стоят три человека: А, Б и В.
Судья точно знает:
- Аборигены всегда отвечают на любые вопросы правдиво.
- Пришельцы всегда лгут.
- Кто из троих кем является — пока неизвестно.
Судья может задавать любые вопросы, на которые возможен ответ «Да» или «Нет». Задача — за минимальное количество вопросов определить, кто есть кто.
Наивный (и неэффективный) способ
Можно задать каждому по два простых вопроса: «Ты абориген?» и «Ты пришелец?». Однако пришелец на оба вопроса ответит «Нет», а абориген — «Да» и «Нет» соответственно. Уже по первому ответу мы узнаём, кто лжёт, но на практике такие прямые вопросы не работают, если присутствует третья группа — конформист (см. ниже) или бог случая, который сам выбирает, лгать или говорить правду.
Универсальный алгоритм решения
Шаг 1. Исключаем лишние сущности
Если условие гарантирует, что перед нами только аборигены и пришельцы (без конформистов и прочих «богов случая»), достаточно одного «умного» вопроса, который обходит ложь пришельца:
- Вопрос №1 (задаём любому, например А):
«Если бы я спросил у тебя: «Ты пришелец?», ты бы ответил “Да”»?
Разбор ответов:
- А отвечает «Да».
• Если А — абориген, то он честно описал бы свой ответ «Нет» на вопрос «Ты пришелец?». Следовательно, «Да» внешне говорит, что он пришелец — противоречие. Значит А пришелец.
• Если А, пришелец, то он солгал бы свой же ответ «Да» → на самом деле он бы ответил «Нет». Но пришелец всегда лжёт, значит он действительно пришелец.
Итак, ответ «Да» гарантированно означает, что перед нами пришелец. - А отвечает «Нет».
Аналогично выводим, что А абориген.
Определив статус одного человека, за два следующих вопроса к оставшимся легко «вычисляем» и их.
Шаг 2. Обобщаем на «три типа»
Если в условии появляется третья группа — конформисты (могут лгать, только если сосед — лжец), или бог случая (говорит правду или лжёт наугад), задача усложняется. Тогда:
- Требуется не менее двух взаимосвязанных вопросов, где второй вопрос зависит от ответа на первый.
- Классический приём — вопрос «Что бы сказал X, если бы я спросил его…», позволяющий «обезвредить» случайность.
Иллюстрация: «Порядок аборигенов» из каталога Школково
Иногда в задачах встречается целая очередь из N аборигенов и пришельцев, где порядок известен частично. Например, из цитаты олимпиады:
«РРЛРРЛРРЛРРЛ…» (обозначения: R — рыцари/аборигены, L, лжецы/пришельцы).
- Всего было 18 человек, тогда рыцарей (R) две трети, т.е. 12.
- Задача сводится к подсчёту количества «R» в заданном шаблоне и проверке условий о «соседях-лжецах» для конформистов.
Чек-лист для решения любой «три-человека» задачи
- Уточните, сколько типов персонажей допущено в условии (2 или 3).
- Запишите все возможные перестановки (AAA, AAP, APA, …) — их всего 8 при двух типах.
- Для каждого возможного набора проверьте, какие ответы дали бы участники.
- Выберите единственный вопрос, ответы которого разбивают множество перестановок на непересекающиеся классы.
- Задавайте вопросы последовательно, сокращая пространство возможностей.
Мини-задача для самостоятельного решения
Условие: Перед вами три человека, Коля, Петя и Вася. Один всегда говорит правду, другой всегда лжёт, третий — «бог случая». Вы можете задать два вопроса, на которые отвечает только один из них (любой по вашему выбору). Как определить, кто есть кто?
Ответ опубликуем в следующей статье.
Логические задачи «три человека — два или три типа поведения» не только развивают абстрактное мышление, но и являются прекрасной иллюстрацией мощности булевой логики и теории информации. Главное — методично исключать невозможные варианты и использовать мета-вопросы, которые «оборачивают» ложь против самого лжеца.
Удачи в решении и помните: даже самый запутанный суд в итоге вынесет вердикт, если вы задаёте правильные вопросы.