Математические головоломки и развлечения
Шрифт:
3. Элен ровно на 26 недель старше своего мужа, который родился в августе.
4. Сестра м-ра Уайта замужем за свояком брата Элен и вышла за него замуж в день своего рождения, в январе.
5. Маргарет Уайт ростом ниже Уилльяма Блейка.
6. Сестра Артура красивее, чем Беатрис.
7. Джону исполнилось 50 лет.
Как зовут миссис Браун?
Не менее распространена и другая разновидность логических задач, которые по аналогии со следующим хорошо известным примером можно назвать задачами типа «задачи о разноцветных колпаках». Троим людям (назовем их А, В и С) завязывают глаза и говорят, что каждому из них на голову надели либо красный, либо зеленый
[Задача о мудрецах в зеленых колпаках сформулирована в тексте так, что она не может иметь решения. Это особенно хорошо видно, когда число мудрецов велико. Сколько времени понадобится первому мудрецу, чтобы догадаться об истинной ситуации?
В конце сороковых годов эта задача усиленно обсуждалась в Москве в школьных математических кружках, и был придуман новый ее вариант, в котором введено дискретное время. Задача эта выглядела так.
В древние времена в одном городе жили мудрецы. У каждого из них была жена. По утрам они приходили на базар и узнавали там все городские сплетни. Они и сами были сплетниками. Им доставляло большое удовольствие узнать о неверности какой-либо из жен — узнавали они об этом тотчас. Однако одно негласное правило соблюдалось неукоснительно: мужу о его жене никогда ничего не сообщалось, так как каждый из них, узнав о собственном позоре, выгнал бы свою жену из дому. Так они и жили, получая удовольствие от задушевных бесед и оставаясь в полном неведении относительно собственных дел.
Но однажды в город приехал настоящий сплетник. Он явился на базар и во всеуслышание заявил: «А не у всех-то мудрецов жены верные!» Казалось бы, сплетник ничего нового не сказал — и так это все знали, знал это и каждый мудрец (только с ехидством думал не о себе, а о другом), поэтому никто из жителей и не обратил внимания на слова сплетника. Но мудрецы задумались — на то они и мудрецы — и на n– й день после приезда сплетника п мудрецов выгнали п неверных жен (если их всего было n).
Рассуждения мудрецов восстановить нетрудно. Труднее ответить на вопрос: какую же информацию добавил сплетник к той, которая была известна мудрецам и без него?
Эта задача неоднократно встречалась в литературе].
С спрашивает себя, может ли его колпак быть зеленым. Если бы это было так, то А сразу же узнал бы, что на нем красный колпак, потому что только красный колпак на его голове мог бы заставить В поднять руку. Но тогда А вышел бы из комнаты. В стал бы рассуждать точно так же и тоже вышел бы из комнаты. Поскольку ни тот, ни другой не вышли, С заключил, что его собственный колпак должен быть красным.
Эта задача допускает обобщение на случай, когда имеется любое число людей и на всех на них надеты красные колпаки. Предположим, что в задаче появилось четвертое действующее лицо D, еще более проницательное, чем С. D мог бы рассуждать так: «Если бы мой колпак был зеленым, то А, В и С оказались бы точно в такой же ситуации, какая только что была описана, и через несколько минут самый догадливый из трио непременно вышел бы из комнаты.
Но прошло уже пять минут, а никто из них не выходит, следовательно, мой колпак красный».
Если бы появился пятый участник, еще более сообразительный, чем D, то он смог бы прийти к заключению, что на нем красный колпак, выждав минут десять. Разумеется, наши рассуждения теряют в убедительности из-за предположений о различной степени сообразительности А, В, С… и довольно смутных соображений относительно того, сколько времени должен выжидать наиболее догадливый человек, прежде чем он сможет с уверенностью назвать цвет своего колпака.
Некоторые другие задачи «о цветных колпаках» содержат меньшую неопределенность. Такова, например, следующая задача, также придуманная Смаллианом. [47] Каждый из троих — А, В и С — в совершенстве владеет логикой, то есть умеет мгновенно извлекать все следствия из данного набора посылок и знает, что остальные также обладают этой способностью.
Берем четыре красные и четыре зеленые марки, завязываем нашим «логикам» глаза и каждому из них наклеиваем на лоб по две марки. Затем снимаем с их глаз повязки и по очереди задаем А, В и С один и тот же вопрос: «Знаете ли вы, какого цвета марки у вас на лбу?» Каждый из них отвечает отрицательно. Затем мы спрашиваем еще раз у А и снова получаем отрицательный ответ. Но когда мы вторично задаем тот же вопрос В, тот отвечает утвердительно.
47
См. главу, посвященную Рэймонду Смаллиану в книге М. Гарднера «Путешествие во времени» (М.: Мир, 1990).
Какого цвета марки на лбу у В?
Третью разновидность популярных логических головоломок составляют задачи о лжецах и тех, кто всегда говорит правду. В классическом варианте задачи речь идет о путешественнике, попавшем в страну, населенную двумя племенами. Члены одного племени всегда лгут, члены другого говорят только правду. Путешественник встречает двух туземцев. «Вы всегда говорите только правду?» — спрашивает он высокого туземца. Тот отвечает: «Тарабара». «Он сказал «да», — поясняет туземец поменьше ростом, знающий английский язык, — но он ужасный лжец». К какому племени принадлежит каждый из туземцев?
Систематический подход к решению заключался бы в выписывании всех четырех возможностей: ИИ, ИЛ, ЛИ, ЛЛ (И означает «истина», Л— «ложь») — и исключении тех из них, которые противоречат данным задачи. Ответ можно получить гораздо быстрее, если заметить, что высокий туземец должен ответить утвердительно независимо от того, лжет ли он или говорит правду. Поскольку туземец поменьше ростом сказал правду, он должен принадлежать к племени правдивых, а его высокий приятель — к племени лжецов.
Самую знаменитую задачу этого типа, усложненную введением вероятностных весов и не очень ясной формулировкой, можно найти довольно неожиданно в середине шестой главы книги английского астронома А. Эддингтона «New Pathways in Science [48] ». «Если А, В, С и D говорят правду в одном случае из трех (независимо друг от друга) и А утверждает, что В отрицает, что С говорит, будто D лжец, то какова вероятность того, что D сказал правду?»
48
Eddington A. New Pathways in Science. — Cambridge: 1935; Michigan: 1959.