|
1. На развилке двух дорог, одна из которых ведёт в город А, где живут правдивые люди, а другая ведёт в город В, где живут лгуны, математик встретил жителя одного из этих городов. Может ли математик за один вопрос выяснить у встреченного им жителя, какая из дорог ведёт в город А?
 Вопрос должен задаваться в такой форме, чтобы ответом на него служили слова «да» или «нет». Вопрос, решающий задачу 1, таков: «Ведёт ли эта дорога (указывая на одну из дорог) в ваш родной город? Легко проверить, что ответ «да» означает, что данная дорога ведёт в А, ответ «нет» - что в В. В самом деле, если отвечающий является жителем города А, то он всегда говорит правду и поэтому его ответ «да» означает, что указанная дорога ведёт в А, а ответ»нет» - что в В. Если же отвечающий живёт в В, то его ответ «да», поскольку этот человек всегда говорит неправду, означает, что указанная дорога ведёт не в В, то есть в А, а ответ «нет» означает, что эта дорога ведёт в его родной город, то есть в В. Таким образом, в обоих случаях ответ «да» означает, что данная дорога ведёт в А, и ответ «нет» - что в В, что и утверждалось.
Заметим, что мы не определяем при ответе, с кем мы разговариваем – с жителем города А или с жителем города В, но это и не требовалось. Можно задать и другой вопрос, но самое главное, что вопрос о том, ведёт ли данная дорога в город А, нужно задать в такой форме, чтобы лгуну приходилось давать «дважды отрицательный» ответ. Поскольку двойное отрицание эквивалентно положительному ответу, лгун в этом случае даёт тот же ответ, что и человек, говорящий правду. Это и происходит в приведённом нами решении.
Вторая задача, которую мы разберём, является усложнением первой. Это усложнение связано с появлением среди отвечающих обманщика. 2. Пусть в условиях задачи 1 математик встретил на развилке не одного, а трёх человек, один из которых является жителем города А, второё – жителем города В, а третий – обманщиком. При этом математик знает, что среди этих троих – один житель города А, другой – житель города В, а третий – обманщик, но конкретно не знает, кто из них есть кто. Может ли математик за два вопроса выяснить дорогу в А?
Уточним, что каждый из двух вопросов может быть задан любому из трёх лиц, встреченных математиком на развилке, и на вопрос отвечает только тот, кому этот вопрос задан. Кроме того, каждый из встреченных знает «кто есть кто» среди них и какая дорога ведёт в А и какая – в В.
Перенумеруем для удобства всех трёх человек произвольным образом. Вопрос задаётся первому. Вот он: «Предположим, что каждый из вас троих сейчас отправится в А или в В по следующему принципу: житель города А пойдёт в город А, житель города В – в город В, а обманщик – если только обманщиком не являетесь вы сами – пойдёте вместе с вами; если же вы обманщик, то вы пойдёте куда угодно. Пойдёт ли при этих условиях в А вот этот (указывая на второго) человек?»
Мы утверждаем, что при ответе «да» третий человек – не обманщик, а при ответе «нет» второй человек – не обманщик. Действительно, если вопрос мы задали обманщику, то второй и третий из опрашиваемых, не являются обманщиками. Далее, если вопрос мы задали человеку, который всегда говорит правду, то его «да» означает, что второй является обманщиком, и стало быть третий им не является. Наоборот, его ответ «нет» свидетельствует о том, что второй человек является лгуном (ведь только лгун не идёт вместе с ним). Если же вопрос мы задали лгуну, то его «да» означает, поскольку обманщик идёт в В, а человек, говорящий правду, – в А, что второй человек – обманщик, а третий – человек, говорящий правду. «Нет» же означает, что наоборот, второй – это человек говорящий правду, а третий – обманщик.
Проанализировав все возможности, нетрудно увидеть, что при ответе «да» третий человек, а при ответе «нет» второй человек заведомо не являются обманщиками. Таким образом, в обоих случаях мы можем указать человека, не являющегося обманщиком. Теперь задача 2 сведена к задаче 1 и, задав выделенному человеку тот же вопрос, что и в задаче 1, мы узнаем дорогу в А.
Заметим, что, как и при решении задачи 1, основная идея состояла в том, чтобы заставить лгуна сделать двойное отрицание, то есть добиться того, чтобы его ответы имели тот же смысл, что и у человека, говорящего правду, и чтобы они при этом различали обманщика и необманщиков. ОСТРОВ РЫЦАРЕЙ И ЛЖЕЦОВ Существует множество хитроумных задач об острове, населенном "рыцарями", всегда говорящими только правду, и лжецами, изрекающими только ложь. Предполагается, что каждый обитатель острова либо рыцарь, либо лжец. Мы начнем с одной хорошо известной задачи этого типа.
3. Трое жителей острова (А, B и C) разговаривали между собой в саду. Проходивший мимо незнакомец спросил у A: "Вы рыцарь или лжец?" Тот ответил, но так неразборчиво, что незнакомец не смог ничего понять. Тогда незнакомец спросил у B: "Что сказал A?" "А сказал, что он лжец", - ответил B. "Не верьте B! Он лжет! - вмешался в разговор островитянин C. Кто из островитян B и C рыцарь и кто лжец?
Решение. Ни рыцарь, ни лжец не могут сказать: "Я лжец" (высказав подобное утверждение, рыцарь солгал бы, а лжец изрек бы истину). Следовательно, A, кем бы он ни был, не мог сказать о себе, что он лжец. Поэтому B, утверждая, будто A назвал себя лжецом, заведомо лгал. Значит, B - лжец. А так как C сказал, что B лгал, когда тот действительно лгал, то C изрек истину. Следовательно, C - рыцарь. Таким образом, B - лжец, а C - рыцарь. (Установить, кем был A, не представляется возможным.) 4. Предположим, что A говорит: "Или я лжец, или B рыцарь". Кто из двух персонажей A и B рыцарь и кто лжец?
Решение. Предположим, что A - лжец. Тогда высказанное им утверждение ложно. "Перевести" это можно так: неверно, что A - лжец и что B - рыцарь. Таким образом, если бы A был лжецом, то из этого следовало бы, что он не лжец, то есть мы пришли бы к противоречию. Отсюда мы заключаем, что A должен быть рыцарем. Итак, мы установили, что A - рыцарь. Следовательно, его высказывание о том, что выполняется по крайней мере одна из двух альтернатив (1) A - лжец, 2) B - рыцарь), истинно. А поскольку первая альтернатива (А - лжец) ложна, то должна выполняться вторая альтернатива, то есть B - рыцарь.
Таким образом, установлено, что A и B - оба рыцари. 5.Перед нами снова три островитянина A, B и C, о каждом из которых известно, что он либо рыцарь, либо лжец. Двое из них (А и B) высказывают следующие утверждения:
A: Мы все лжецы.
B: Один из нас рыцарь.
Кто из трех островитян A, B и C рыцарь и кто лжец?
Решение. Прежде всего, заметим, что A должен быть лжецом. Действительно, если бы A был рыцарем, то из его высказывания следовало бы, что все трое лжецы. Но тогда A (по предположению, рыцарь) оказался бы лжецом, что невозможно. Следовательно, A - лжец. Но тогда его высказывание ложно и по крайней мере один из трех островитян A, B и C - рыцарь.
Предположим теперь, что B - лжец. Тогда A и B - оба лжецы, поэтому C должен быть рыцарем (так как, по крайней мере, один из трех островитян рыцарь). Это означает, что ровно один из трех островитян рыцарь, и, следовательно, высказывание B истинно, но это невозможно, так как любое высказывание лжеца не истинно. Отсюда мы заключаем, что B должен быть рыцарем.
Итак, мы установили, что A - лжец, а B - рыцарь. Так как B - рыцарь, то его высказывание истинно, поэтому ровно один из трех островитян - рыцарь. Им должен быть B, следовательно, C должен быть лжецом. Итак, A - лжец, B - рыцарь и C - лжец. 6.Перед нами в очередной раз три островитянина A, B и C, о каждом из которых известно, что он либо рыцарь, либо лжец. Условимся называть двух островитян однотипными, если они оба рыцари или оба лжецы. Пусть A и B высказывают следующие утверждения:
A: B - лжец.
B:A и C однотипны.
Кто такой C: рыцарь или лжец?
Решение. Предположим, что A - рыцарь. Тогда его высказывание о том, что B - лжец, должно быть истинным, в силу чего B должен быть лжецом. Но тогда высказывание B о том, что A и C однотипны, ложно, поэтому A и C не однотипны. Следовательно, C - лжец (так как A - рыцарь). Таким образом, если A - рыцарь, то C - лжец. С другой стороны, предположим, что A - лжец. Тогда его высказывание о том, что B - лжец, ложно, в силу чего B - рыцарь. Следовательно, высказывание B о том, что A и C однотипны, истинно. Отсюда мы заключаем, что C - рыцарь (так как A - рыцарь).
Итак, мы доказали, что независимо от того, кто такой A - рыцарь или лжец, C должен быть лжецом. Следовательно, C - лжец. 7.Перед нами снова трое островитян A, B и C. А высказывает утверждение: "В и C однотипны". Кто-то спрашивает у C: "А и B однотипны?" Что ответит островитянин C?
Решение. Для решения этой задачи необходимо рассмотреть отдельно два случая. Первый случай: A - рыцарь. Тогда B и C однотипны. Если C - рыцарь, то и B - рыцарь и, следовательно, однотипен с A. Поэтому C, будучи человеком правдивым, должен был ответить "Да". Если C - лжец, то и B - лжец (поскольку B однотипен с C) и, следовательно, принадлежит к иному типу островитян, чем A. Поэтому C, будучи лжецом, должен солгать и ответить "да".
Второй случай: A - лжец. Тогда B и C не однотипны. Если C - рыцарь, то B - лжец и, следовательно, однотипен с A. Поэтому C, будучи рыцарем, должен ответить "да". Если C - лжец, то B, будучи человеком иного типа, чем C, - рыцарь и принадлежит к иному типу островитян, чем A. Но тогда C, будучи лжецом и утверждая, что A и C не однотипны, должен лгать, поэтому на заданный вопрос он ответит "да". Таким образом, в обоих случаях C ответит "да". РЫЦАРИ, ЛЖЕЦЫ И НОРМАЛЬНЫЕ ЛЮДИВ не менее увлекательном виде задач персонажи делятся на три типа: рыцарей, говорящих всегда только правду, лжецов, изрекающих только ложь, и нормальных людей, которые иногда лгут, а иногда говорят правду. 8.Перед нами трое людей A, B и C. Один из них рыцарь, другой лжец и третий - нормальный человек (типы людей могут быть перечислены не в том же порядке, в каком выписаны их "имена" A, B и C). Наши знакомые высказывают следующие утверждения.
A: Я нормальный человек.
B: Это правда.
C: Я не нормальный человек.
Кто такие A, B и C?
Решение. Прежде всего заметим, что A не может быть рыцарем, потому что рыцарь не назвал бы себя нормальным человеком. Следовательно, A - либо лжец, либо нормальный человек. Тогда истинно высказывание островитянина B. Значит, B - либо рыцарь, либо нормальный человек. Но B не может быть нормальным человеком (так как A - нормальный человек), поэтому B - рыцарь, а C - лжец. Но лжец не может сказать о себе, что он не нормальный человек (так как любой лжец - не нормальный человек), и мы приходим к противоречию. Итак, A не может быть нормальным человеком. Следовательно, A - лжец. Это означает, что высказывание островитянина B ложно, в силу чего B должен быть нормальным человеком (лжецом он быть не может, так как лжец - островитянин A). Итак, A - лжец, а B - нормальный человек. Отсюда мы заключаем, что C - рыцарь. 9. Двое людей A и B, о которых известно, что каждый из них либо рыцарь, либо лжец, либо нормальный человек, высказывают следующие утверждения:
A: B - рыцарь.
B: A - не рыцарь.
Докажите, что по крайней мере один из них говорит правду, но это не рыцарь.
Решение. Эта задача обладает интересной особенностью. Условия ее не позволяют установить, кто из двух островитян говорит правду, не будучи рыцарем: A или B. Мы можем доказать более слабое утверждение: по крайней мере один из двух островитян A и B говорит правду, не будучи рыцарем. Островитянин A либо говорит правду, либо не говорит правду. Докажем два утверждения: 1) если A говорит правду, то он говорит правду, не будучи рыцарем; 2) если A лжет, то B говорит правду, не будучи рыцарем.
1) Предположим, что A говорит правду. Тогда B - рыцарь и, следовательно, говорит правду. Значит, A - не рыцарь. Таким образом, если A говорит правду, то A - лицо, говорящее правду, не будучи рыцарем.
2) Предположим, что A не говорит правду. Тогда B - не рыцарь. Но B должен говорить правду, так как A не может быть рыцарем (ведь A не говорит правду). Следовательно, в этом случае B говорит правду, не будучи рыцарем. 10. Табель о рангах.
На одном острове, где живут рыцари, лжецы и нормальные люди, лжецы считаются особами низшего ранга, нормальные люди - особами среднего ранга и рыцари - особами высшего ранга. Два человека A и B, о каждом из которых известно, что он либо лжец, либо нормальный человек, высказывают утверждения:
A: По рангу я ниже, чем B.
B: Не правда!
Можно ли определить ранг A или B? Можно ли установить, истинно или ложно каждое из этих двух утверждений?
Решение. Прежде всего заметим, что A не может быть рыцарем, так как если бы A был рыцарем, то его высказывание было бы ложным (рыцарь как особа высшего ранга не может быть по рангу ниже B). Предположим, что A - лжец. Тогда его высказывание ложно. Следовательно, A по рангу не может быть ниже, чем B. Значит, B также должен быть лжецом (так как если бы B не был лжецом, то A был бы особой более высокого ранга, чем B). Но это невозможно, так как высказывание B противоположно высказыванию A, а два противоположных высказывания не могут быть истинными одновременно. Следовательно, предположение, что A - лжец, приводит к противоречию. Значит, A не лжец, но тогда A должен быть нормальным человеком. А что можно сказать о B? Если бы он был рыцарем, то A (будучи нормальным человеком) был бы особой более низкого ранга, чем B. Тогда высказывание A было бы истинным, из чего следовало бы, что высказывание B ложно. Таким образом, рыцарь высказал бы ложное утверждение, что невозможно. Значит, B не рыцарь. Предположим, что B был бы лжецом. Тогда высказывание A было бы ложным, из чего следовало бы, что высказывание B истинно. Таким образом, лжец высказал бы истинное утверждение, что невозможно. Следовательно, B не может быть не только рыцарем, но и лжецом. Значит, B - нормальный человек. Итак, A и B - нормальные люди. Высказывание A ложно, высказывание B истинно. Тем самым задача полностью решена. 11. Трое людей A, B и C, о каждом из которых известно, что он либо рыцарь, либо лжец, либо нормальный человек, высказывают следующие утверждения: A:
B по рангу выше, чем C.
B: C по рангу выше, чем A.
Затем у C спрашивают: "Кто старше по рангу - A или B?" Что ответит C?
Решение. Первый шаг. Прежде всего докажем, что в силу высказывания A островитянин C не может быть нормальным человеком. Действительно, если A - рыцарь, то B - особа более высокого ранга, чем C. Следовательно, B должен быть нормальным человеком, а C - лжецом. Таким образом, в этом случае C - не нормальный человек. Предположим, что A - лжец. Тогда B по рангу не выше C. Следовательно, B - особа более низкого ранга, поэтому B должен быть нормальным человеком, а C - рыцарем. Таким образом, и в этом случае C - не нормальный человек. Предположим, наконец, что A - нормальный человек. Тогда C - заведомо не нормальный человек (так как из трех островитян A, B и C только один – нормальный человек). Итак, C - не нормальный человек.
Второй шаг. При аналогичных рассуждениях из высказывания B можно вывести, что A - не нормальный человек. Таким образом, ни A, ни C не нормальны. Следовательно, B - нормальный человек.
Третий шаг. Поскольку C - не нормальный человек, то он может быть рыцарем или лжецом. Предположим, что он рыцарь. Тогда A - лжец (так как B - нормальный человек). Следовательно, B - особа более высокого ранга, чем A, и C, будучи рыцарем, даст правдивый ответ: "В по рангу выше A". С другой стороны предположим, что C - лжец. Тогда A должен быть рыцарем, поэтому B по рангу не выше A. В этом случае C, будучи лжецом, солгал бы и ответил так: "В по рангу выше A". Таким образом, независимо от того, кто такой островитянин C - рыцарь или лжец, он ответит, что B по рангу выше A.
|
