Снова о рыцарях и лжецах

42

КВАНТ 2014/№3

рой внутренней точки треугольника до его вершин через p, q, r. Докажите, что p + q + r < b + c. 9. Найдите точку, сумма расстояний от которой до четырех данных точек минимальна (нужно рассмотреть два случая: когда точки образуют выпуклый четырехугольник и когда одна точка лежит в треугольнике из трех других точек).

Хотелось бы расширить свою коллекцию решений замечательной задачи о точке Торричелли. Если вы найдете еще одно красивое решение, присылайте его, пожалуйста, автору по адресу [email protected]

Снова о рыцарях и лжецах

Наш вопрос должен быть «индикатором» рыцарей и лжецов: т.е. либо рыцари всегда на него должны отвечать «йа», а лжецы – всегда «ва», либо наоборот. Зададим любому из аборигенов вопрос «Йа – это Да?» Вариант 1. Пусть «йа» означает «да». Тогда рыцарь на такой вопрос должен отвечать «да», т.е. «йа». Лжец же должен ответить на такой вопрос «нет», т.е. «ва». Вариант 2. Пусть «йа» означает «нет». Тогда рыцарь на такой вопрос отвечает «нет», т.е. это опять же «йа»! А лжец должен ответить «да», т.е. снова «ва»! Итак, рыцарь на наш вопрос всегда отвечает «йа», а лжец – «ва». Задача решена.

Л.БОЙКО, М.БОЙКО

НАВЕРНЯКА ЧИТАТЕЛЬ ВСТРЕЧАЛ ЗАНИМАТЕЛЬНЫЕ ЗА- дачи о рыцарях, которые всегда говорят правду, и лжецах, которые всегда врут. Иногда в подобных задачах появляются и другие персонажи.

Кто такие хитрецы? Задача 1 (XXVIII Турнир городов). Известно, что лжецы всегда врут, рыцари всегда говорят правду, а хитрецы могут и врать, и говорить правду. Вы можете задавать вопросы, на которые возможен ответ «да» или «нет» (например: «Верно ли, что этот человек – хитрец?»). Перед вами трое – лжец, рыцарь и хитрец, которые знают, кто из них кто. Как и вам это узнать? У этой задачи есть несколько решений. Перед тем как прочесть одно из них в следующем абзаце, попробуйте придумать свое! Ключом к решению может стать некоторый вопрос, заданный каждому из трех людей, ответ на который отличит рыцаря от лжеца. Например, спросим у каждого из трех людей: «Вы хитрец?» Рыцарь ответит «нет», лжец ответит «да». Что бы ни ответил хитрец, среди трех полученных нами ответов есть либо единственное «нет», либо единственное «да». В первом случае мы однозначно определяем рыцаря, спрашивая которого далее легко добыть информацию про остальных двух людей. Во втором случае мы однозначно определяем лжеца. Далее, спрашивая его про остальных людей (с учетом того, что ответы лжеца противоположны истине), мы опять узнаем информацию про остальных людей.

Упражнение (XXVIII Турнир городов). Пусть в условиях задачи 1 перед вами четверо – лжец, рыцарь и два хитреца (все четверо знают, кто из них кто). Докажите, что хитрецы могут договориться отвечать так, что вы, спрашивая этих четверых, ни про кого из них не узнаете наверняка, кто он.

Языковые трудности

Но что, если вы не вполне хорошо знаете местный язык? Задача 2. Часть жителей некого острова – рыцари, остальные – лжецы. Островитяне понимают наш язык, а мы про язык островитян знаем лишь, что в нем одно из слов «йа» и «ва» означает «да», а другое – «нет» (но не помним точно, как именно). Пусть мы встретили двух аборигенов, один из которых – рыцарь, а другой – лжец. Сможем ли мы, задав всего один вопрос (предполагающий ответ «да» или «нет», т.е. «йа» или «ва»), узнать, кто из них кто?

Немного истории В 1992 году американский философ и логик Джордж Булос опубликовал задачу, которую он назвал «Cамой сложной логической задачей». Внешне «Самая сложная задача» похожа на разобранную выше задачу 1, но в ней имеется дополнительная сложность, которая была в задаче 2: персонажи понимают наш язык, но отвечают нам исключительно на своем языке, который непонятен нам. Дж.Булос называет персонажей мифическими богами, мы же позволим себе сохранить более привычные персонажи. Кроме того, это кажется нам более естественным, поскольку автором «Cамой сложной задачи» Дж.Булос указывает Рэймонда Смаллиана. Нам неизвестно, действительно ли это так, но безусловно Р.Смаллиан – наиболее известный популяризатор задач такого рода. Авторы настоящей статьи с большим интересом в школе решали логические задачи из книг Р.Смаллиана. В русском переводе этой книги, как правило, использовались именно такие персонажи: рыцари и лжецы.

Постановка «Самой сложной логической задачи» Итак, дадим точную формулировку «Самой сложной логической задачи». Задача 3. На острове Йава люди делятся на три типа: рыцари – те, кто всегда говорят правду; лжецы – те, кто всегда врут; и хитрецы – те, кто могут говорить как правду, так и ложь. Предположим, перед нами три человека – мистер A, мистер Б, мистер В. Мы знаем, что среди них ровно один рыцарь, один лжец и один хитрец, но мы не знаем, кто из них кто. Требуется определить, кто из людей – рыцарь, кто – лжец, а кто – хитрец, задав не более трех вопросов. Вопросы должны быть такими, чтобы на них можно было ответить «да» или «нет». Каждый вопрос задается только одному человеку. Дополнительная сложность состоит в том, что островитяне понимают наш язык, но отвечают нам исключительно на своем языке. Мы знаем, что в этом языке есть два слова «йа» и «ва», которые означают «да» и «нет», но мы не знаем, какое именно слово означает «да», а какое – «нет». Дадим несколько пояснений к формулировке, которые указывает в своей статье Дж.Булос. i Можно задавать одному человеку более чем один вопрос (в таком случае другим людям может быть не задано ни одного вопроса).

43

МАТЕМАТИЧЕСКИЙ

i Каков будет следующий вопрос и кому он будет задан, может зависеть от ответа на предыдущий вопрос. i Нельзя задавать вопросы-парадоксы, на которые можно ответить и «да» и «нет» или никак нельзя ответить. Например, «Ты сейчас ответишь «йа»?» i Хитрец отвечает на вопросы совершенно произвольно. Можно считать, что каждый раз он подбрасывает мысленно монетку и если выпадает орел – он отвечает правду, а если решка – лжет. Добавим к этому, что, конечно же, мистеры А, Б и В знают друг друга и знают, кто из них лжец, кто рыцарь, а кто хитрец. Перед тем как изложить решение, введем две мысленные конструкции.

Мистер Йа, мистер Ва и мистер Хи Выше мы назвали рыцарем человека, который всегда говорит правду. Другими словами можно сказать так: рыцарь – это человек, который отвечает «да», если утверждение, сформулированное в вопросе, истинно. В то же время лжец – это тот, кто отвечает на такое утверждение «нет». Вспомним, что островитяне используют свой язык. Таким образом, на вопрос, в котором сформулировано истинное утверждение, и лжец и рыцарь отвечают либо всегда «йа», либо всегда «ва». Тому, кто отвечает «йа», дадим второе имя – мистер Йа. А того, кто отвечает всегда «ва», будем называть мистер Ва. Наконец, хитреца будем называть мистер Хи. Заметим, что мы не можем знать о мистере Йа, рыцарь он или лжец, но сами островитяне А, Б и В должны знать, кто из них кто. Поэтому мы можем использовать новые имена в вопросах. Например, мы можем спросить у мистера А: «Ты являешься мистером Йа?» или спросить у него же: «Мистер Б – это мистер Ва?»

Колода карт Теперь возьмем три одинаковых листочка бумаги и на первом напишем «мистер Йа», на втором – «мистер Ва», на третьем – «мистер Хи». Получим три карты – карту Йа, карту Ва и карту Хи.

Естественным образом получается соответствие между людьми и картами. Таким образом, если в вопросе встретится понятие «карта мистера А», островитяне должны понимать это так: нужно посмотреть, кто такой мистер А – мистер Йа, Ва или Хи, – и найти карту, на которой написано соответствующее имя. Аналогично надо поступать, если в вопросе присутствует понятие «твоя карта». Теперь сложим эти три карты в колоду: сверху карта Йа, потом карта Ва и нижняя – карта Хи. Если у нас нет бумаги и мы не можем изготовить такую колоду, мы должны попросить островитян сделать мысленный эксперимент: представить эти три карты именно в таком порядке. Почему выбран именно такой порядок карт? Чуть позже мы дадим этому пояснение. В дальнейшем в вопросах будет встречаться понятие «одна карта лежит в колоде на другой». В данном случае мы

КРУЖОК

понимаем это так: карта находится в колоде выше другой, и эти две карты являются соседними в колоде. Таким образом, в нашей колоде карта Йа лежит на карте Ва, а карта Ва лежит на карте Хи. Но карта Йа НЕ лежит на карте Хи. Теперь мы можем перейти непосредственно к вопросам, которые должны определить, кто из островитян кто.

Решение задачи 3

Первый вопрос

Спросим у мистера А следующее: «Лежит ли твоя карта в колоде на карте мистера Б?» Докажем, что в случае ответа «йа» на этот вопрос, мистер Б – не хитрец (он рыцарь или лжец), а в случае ответа «ва» на этот вопрос мистер В – не Хи. Заметим, что если А – мистер Хи, то ни Б, ни В не могут быть Хи, что нам и нужно. Предположим, что мистер А – не Хи, и рассмотрим варианты его ответов на вопрос. Пусть А ответил «йа». Вариант 1: мистер А – это мистер Йа. Тогда утверждение в вопросе истинно, и карта мистера А – это карта Йа. Так как в колоде карта Йа лежит на карте Ва, то мистер Б – это мистер Ва. Вариант 2: мистер А – это мистер Ва. Раз мистер Ва ответил «йа», то утверждение «карта мистера А лежит на карте мистера Б» – ложно. Значит, карта Ва не лежит на карте мистера Б. По определению колоды карта Ва лежит на карте Хи. Значит, мистер Б – не Хи. Пусть А ответил «ва». Вариант 1: мистер А – это мистер Йа. Утверждение в вопросе ложно. Карта Йа лежит в колоде на карте Ва и не лежит на карте Хи. Значит, мистер Б – это Хи, а мистер В – это мистер Ва. Вариант 2: мистер А – это мистер Ва. Утверждение истинно. Карта Ва лежит в колоде на карте Хи. Значит, мистер Б – это Хи, а мистер В – это мистер Йа.

Второй вопрос

Первым вопросом мы из мистеров Б и В определили того, который точно не является хитрецом. Второй вопрос нужно задать именно этому, не являющемуся хитрецом, островитянину. В обоих случаях вопрос будет один и тот же и будет очень похож на предыдущий: «Лежит ли твоя карта в колоде на карте мистера А?» Как мы видели выше, ответ на этот вопрос указывает нам среди двух островитян (тех, которым не адресован текущий вопрос) одного, который точно не является мистером Хи. Для определенности рассмотрим случай, когда вопрос задается Б. Тогда или А, или В – не Хи. Пусть В. Тогда Хи – это мистер А. Аналогично во всех возможных случаях мы узнаем того, кто является мистером Хи.

Третий вопрос

Итак, предыдущими двумя вопросами мы нашли среди островитян мистера Хи. Как и в решении задачи 2, зададим любому из двух оставшихся жителей острова вопрос-«индикатор» рыцарей и лжецов «Йа – это Да?» и тем самым узнаем, кто есть кто. Алгоритм предъявлен и задача решена! Приведенное решение идейно близко к оригинальному решению Дж. Булоса. Однако две мысленные конструкции – новые имена людей и колода карт (отношение среди новых имен) – позволили избежать условных высказываний, а