Содержание

Главная >> Информатика 10 класс. Босова

§ 22. Логические задачи и способы их решения

Задачи о рыцарях и лжецах

Задачи о рыцарях и лжецах — это такой класс логических задач, в которых фигурируют персонажи:

• рыцарь — человек, всегда говорящий правду;
• лжец — человек, всегда говорящий ложь;
• обычный человек — человек, который в одних ситуациях может говорить правду, а в других — лгать.

Решение подобных задач сводится к перебору вариантов и исключению тех из них, которые приводят к противоречию.

Пример 2. Двое жителей острова А и В разговаривали между собой в саду. Проходивший мимо незнакомец спросил у А: «Вы рыцарь или лжец?». Тот ответил, но так неразборчиво, что незнакомец не смог ничего понять. Тогда незнакомец спросил у В: «Что сказал А?». «А сказал, что он лжец», — ответил В. Может ли незнакомец доверять ответу В? Мог ли А сказать, что он лжец?

Если А — рыцарь, то он скажет правду и сообщит, что он рыцарь.

Если А — лжец, то он скроет правду и сообщит, что он рыцарь.

Это значит, что В, утверждающий, что «А сказал, что он лжец» заведомо лжёт; он — лжец. Определить же, кем является А, в данной ситуации невозможно.

Пример 3. Рядом стоят два города: город Лжецов (Л) и город Правдивых (П). В городе Лжецов живут лжецы, а в городе Правдивых — правдивые люди. Лжецы всегда лгут, а правдивые — всегда говорят правду. Лжецы и правдивые ходят друг к другу в гости.

Вы попали в один из городов, а в какой не знаете. Вам нужно у первого встречного, задав простой вопрос, узнать, в каком вы городе. Ответом на вопрос может быть только «Да» или «Нет».

Нужен простой вопрос, ответ на который точно известен вашему респонденту. Например: «Вы находитесь в своём городе? ».

Надо задать вопрос и проанализировать варианты ответов с учетом того, кто их мог дать.

Самостоятельно разберитесь с решением задачи, рассмотрев блок-схему на рис. 4.12.

Пример 4. Перед нами три человека: А, B и С. Один из них рыцарь, другой — лжец, третий — нормальный человек. При этом неизвестно, кто есть кто. Эти люди утверждают следующее:

1) А: я нормальный человек;
2) B: это правда;
3) С: я не нормальный человек.

Кто такие А, B и С?

Для решения этой задачи следует рассмотреть все возможные варианты распределения ролей.

Начнём с А. Он может быть рыцарем (Р), лжецом (Л) или нормальным человеком (Н). Если А — рыцарь, то B может быть лжецом или нормальным человеком и т. д. Представим все варианты распределения ролей в таблице:

Проанализируем имеющиеся три утверждения, считая, что роли между А, B и С распределены в соответствии с первой строкой таблицы.

Итак, А утверждает, что он нормальный человек (1). Но, согласно первой строке таблицы, — он рыцарь, который не может так о себе сказать. Получено противоречие. Следовательно, первая строка не удовлетворяет условию задачи.

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