В задачах про рыцарей и лжецов рыцарь всегда говорит правду, а лжец произносит ложное высказывание. Чтобы решить задачу, назначьте каждому островитянину один из двух типов, проверьте смысл каждого его предложения и оставьте только согласованные варианты. Не угадывайте по интонации: если фраза истинна, её автор должен быть рыцарем; если ложна — лжецом.
На острове встретились Ася и Борис. Ася сказала: «Борис — лжец». Борис ответил: «Мы разных типов». Кто они? Эта короткая история покажет весь метод. Обозначим Р — рыцаря, Л — лжеца. Для двух людей есть четыре версии: РР, РЛ, ЛР и ЛЛ. В каждой нужно сверить не только слова Аси, но и слова Бориса.
Проверяем каждую версию
Предложение Аси «Борис — лжец» истинно ровно тогда, когда Борис Л. Предложение Бориса «Мы разных типов» истинно, когда один Р, а другой Л. Версия годится, если истинность обоих предложений совпадает с типом их говорящего. Таблица показывает, в каком месте версия ломается.
| Ася, Борис | Слова Аси | Слова Бориса | Итог |
|---|---|---|---|
| Р, Р | Ложь от Р | Ложь от Р | Нет |
| Р, Л | Правда от Р | Правда от Л | Нет |
| Л, Р | Ложь от Л | Правда от Р | Да |
| Л, Л | Правда от Л | Ложь от Л | Нет |
Разбор 1. Итак, Ася — лжец, Борис — рыцарь. Проверка в обе стороны: Борис действительно не лжец, поэтому фраза Аси ложна; их типы действительно различны, поэтому фраза Бориса истинна. Одного правдоподобного предположения недостаточно: мы перебрали все четыре и показали, почему три не подходят. Это пример согласованного варианта: каждая реплика имеет именно ту истинность, которую требует тип говорящего.
На практике тот же перебор используют в программировании логических задач: компьютеру задают два возможных типа для каждого участника и оставляют строки, где выполнены все условия. Но смысл фраз нужно точно задать до перебора. Для работы с несколькими условиями полезен раздел «Логические рассуждения»; другой вид олимпиадной головоломки разобран в задачах со спичками.
Когда островитян трое
К Асе и Борису присоединилась Вера, но условия другой задачи изменились. Ася сказала: «Борис — рыцарь». Борис сказал: «Вера — лжец». Вера сказала: «Ася и Борис одного типа». Здесь уже восемь версий. Можно начать с слов Веры: если она Р, типы Аси и Бориса одинаковы; если Л, они различаются. Затем проверить слова Аси и Бориса. Эта развилка экономит записи, но не отменяет проверку оставшейся версии.
| Допущение | Следствие из её слов | Проверка остальных |
|---|---|---|
| Вера Р | Ася и Борис одинаковы | РРР: Борис лжёт; ЛЛР: оба лгут. Подходит ЛЛР. |
| Вера Л | Ася и Борис различны | РЛЛ: Ася лжёт как Р; ЛРЛ: Ася говорит правду как Л. Оба отпадают. |
Разбор 2. Если Вера Р, то Ася и Борис одинаковы. При РРР Борис утверждает, что Вера Л, и лжёт как рыцарь — нельзя. При ЛЛР Ася ложно называет Бориса рыцарем; Борис ложно называет Веру лжецом; Вера правдиво говорит, что первые двое одинаковы. Эта версия подходит. Если Вера Л, Ася и Борис должны быть разными. При РЛЛ Ася правдиво назвала бы Бориса рыцарем лишь если он Р, но он Л — нельзя. При ЛРЛ Ася говорит «Борис Р», то есть правду как лжец — тоже нельзя. Ответ один: Ася Л, Борис Л, Вера Р.
Точная формулировка меняет ответ
«Хотя бы один рыцарь» означает одного или нескольких. «Ровно один рыцарь» исключает случаи с двумя рыцарями. Для двух людей первая фраза истинна в РР, РЛ и ЛР, а вторая только в РЛ и ЛР. Не заменяйте одну другой. И не предполагайте, что задача непременно имеет единственный ответ: согласованных вариантов может быть несколько или не быть вовсе. Тогда так и нужно сообщить, а не выбирать один наугад.
Три задачи для самостоятельной проверки
Для каждой задачи сначала выпишите все версии типов. Раскройте ответ после проверки обоих говорящих. Результат может быть не единственным.
Задача 1. Глеб говорит: «Дина — рыцарь». Дина говорит: «Мы оба лжецы». Кто они?
Ни одной согласованной версии. Если Глеб Р, Дина тоже Р по его словам, но фраза Дины «оба Л» ложна — рыцарь так не скажет. Если Глеб Л, его слова ложны, значит Дина Л; тогда её фраза «оба Л» истинна — лжец так не скажет. Других версий нет. Ошибка — объявить ЛЛ ответом, проверив только Глеба.
Задача 2. Ира говорит: «Женя — рыцарь». Женя говорит: «Ира — рыцарь». Определите типы.
Два решения: РР и ЛЛ. При РР обе фразы истинны, при ЛЛ обе ложны. Смешанные пары не подходят: один из говорящих тогда назвал бы тип другого неверно для своего типа. Не добавляйте в условие невысказанное «ровно один рыцарь».
Задача 3. Кирилл говорит: «Ровно один из Лены и Максима — рыцарь». Лена говорит: «Кирилл — лжец». Максим говорит: «Лена — лжец». Кто они?
Кирилл Р, Лена Л, Максим Р. Среди Лены и Максима ровно один Р, поэтому слова Кирилла истинны. Лена ложно называет Кирилла лжецом; Максим правдиво называет Лену лжецом. Проверка всех восьми версий оставляет только РЛР. Если получилось РРР, сравните «ровно один» с «хотя бы один»: при двух рыцарях в названной паре первая фраза была бы ложной.
После этих проверок можно перейти к разделу «Основы олимпиадной математики». Публичная страница раздела доступна; наличие именно задач про рыцарей и лжецов внутри курса здесь не обещается.