(Большая преамбула из Гарднера)
Из цикла «задачи о разноцветных колпаках».
Троим людям (назовем их А, В и С) завязывают глаза и говорят, что каждому из них на голову надели либо красный, либо зеленый колпак. Затем глаза им развязывают и просят поднять руку, если они видят красный колпак, и выйти из комнаты, если они уверены в том, что знают, какого цвета колпак у них на голове. Все три колпака оказались красными, поэтому все трое подняли руку. Прошло несколько минут, и С, который отличается большей сообразительностью, чем А и В, вышел из комнаты. Каким образом С смог установить, какого цвета колпак на нем?
С спрашивает себя, может ли его колпак быть зеленым. Если бы это было так, то А сразу же узнал бы, что на нем красный колпак, потому что только красный колпак на его голове мог бы заставить В поднять руку. Но тогда А вышел бы из комнаты. В стал бы рассуждать точно так же и тоже вышел бы из комнаты. Поскольку ни тот, ни другой не вышли, С заключил, что его собственный колпак должен быть красным.
Эта задача допускает обобщение на случай, когда имеется любое число людей и на всех них надеты красные колпаки. Предположим, что в задаче появилось четвертое действующее лицо D, еще более проницательное, чем С, D мог бы рассуждать так: «Если бы мой колпак был зеленым, то A, В и С оказались бы точно в такой же ситуации, какая только что была описана, и через несколько минут самый догадливый из трио непременно вышел бы из комнаты. Но прошло уже пять минут, а никто из них не выходит, следовательно, мой колпак красный».
Если бы появился пятый участник, еще более сообразительный, чем D, то он смог бы прийти к заключению, что на нем красный колпак, выждав минут десять. Разумеется, наши рассуждения теряют в убедительности из-за предположений о различной степени сообразительности A, В, С ... и довольно смутных соображений относительно того, сколько времени должен выжидать наиболее догадливый человек, прежде чем он сможет с уверенностью назвать цвет своего колпака.
Некоторые другие задачи «о цветных колпаках» содержат меньшую неопределенность. Такова, например, следующая задача, также придуманная Смулльяном. Каждый из троих — A, В и С — в совершенстве владеет логикой, то есть умеет мгновенно извлекать все следствия из данного набора посылок, и знает, что остальные также обладают этой способностью.
Берем четыре красные и четыре зеленые марки, завязываем нашим «логикам» глаза и каждому из них наклеиваем на лоб по две марки. Затем снимаем с их глаз повязки и по очереди задаем А, В и С один и тот же вопрос: «Знаете ли вы, какого цвета марки у вас на лбу?» Каждый из них отвечает отрицательно. Затем мы спрашиваем еще раз у A и снова получаем отрицательный ответ. Но когда мы вторично задаем тот же вопрос В, тот отвечает утвердительно. Какого цвета марки на лбу у В?
В задаче с марками у В имеются три возможности. Его марки могут быть: 1) обе красными; 2) обе зелеными; 3) одна зеленой, а другая красной. Предположим, что обе марки красные.
После того как все трое ответили по одному разу, А может рассуждать так: «Марки у меня на лбу не могут быть обе красными (потому что тогда С увидел бы четыре красные марки и сразу узнал бы, что у него на лбу две зеленые марки, а если бы у С обе марки были зелеными, то В, увидев четыре зеленые марки, понял бы, что у него на лбу две красные марки). Поэтому у меня на лбу одна зеленая и одна красная марки».
Но когда А спросили второй раз, он не знал, какого цвета его марки. Это позволило В отбросить возможность того, что обе его собственные марки красные. Рассуждая точно так же, как и А, В исключил случай, когда обе его марки зеленые. Следовательно, у него осталась единственная возможность: одна марка зеленая, другая красная.
Несколько читателей быстро заметили, что задачу можно решить очень быстро, не занимаясь анализом вопросов и ответов. Вот что написал по этому поводу один из читателей: «Условия задачи полностью симметричны относительно красных и зеленых марок. Поэтому, распределив марки между А, В и С с соблюдением всех условий задачи и заменив красные марки зелеными и, наоборот, зеленые красными, мы придем к иному распределению, для которого все условия также будут выполнены. Отсюда следует, что если решение единственно, то оно должно быть инвариантным (не должно меняться) при замене зеленых марок на красные, а красных на зеленые. Таким решением может быть только такoе распределение марок, при которому В окажется одна зеленая и одна красная марка».
Как выразился декан математического факультета Бруклинского колледжа У. Манхеймер, это изящное решение исходит из того обстоятельства, что в совершенстве владеют логикой не A, В и С (как о том сказано в условии задачи), а Рэймонд Смулльян!
(Конец преамбулы)
Задача (Смородинский)
Задача о мудрецах в зеленых колпаках сформулирована в тексте так, что она не может иметь решения. Это особенно хорошо видно, когда число мудрецов велико. Сколько времени понадобится первому мудрецу, чтобы догадаться об истинной ситуации?
В конце сороковых годов (видимо, прошлого века
эта задача усиленно обсуждалась в Москве в школьных математических кружках, и был придуман новый ее вариант, в котором введено дискретное время. Задача эта выглядела так.
В древние времена в одном городе жили мудрецы. У каждого из них была жена. По утрам они приходили на базар и узнавали там все городские сплетни. Они и сами были сплетниками. Им доставляло большое удовольствие узнать о неверности какой-либо жены — узнавали они об этом тотчас. Однако одно негласное правило соблюдалось неукоснительно: мужу о его жене никогда ничего не сообщалось, так как каждый из них, узнав о собственном позоре, выгнал бы свою жену из дому. Так они и жили, получая удовольствие от задушевных бесед и оставаясь в полном неведении относительно собственных дел.
Но однажды в город приехал настоящий сплетник. Он явился на базар и во всеуслышание заявил: «А не у всех-то мудрецов жены верные!» Казалось бы, сплетник ничего нового не сказал — и так это все знали, знал это и каждый мудрец (только с ехидством думал. не о себе, а о другом), поэтому никто из жителей и не обратил внимания на слова сплетника. Но мудрецы задумались—на то они и мудрецы — и на Н-и день после приезда сплетника Н мудрецов выгнали Н неверных жен (если их всего было Н).
Рассуждения мудрецов восстановить нетрудно. Труднее ответить на вопрос: какую же информацию добавил сплетник к той, которая была известна мудрецам и без него?
Эта задача неоднократно встречалась в литературе.
Итак, 2 вопроса:
1. Рассуждения мудрецов?
2. Какую же информацию добавил сплетник к той, которая была известна мудрецам и без него?
