Ежегодно по окончании курса лекций по аховым феноменам проф. Ах награждал специально учрежденной им медалью Аха наиболее отличившегося из своих слушателей. На этот раз на получение медали претендовали 3 кандидата.

Чтобы выбрать наиболее достойного из них, проф. Ах решил прибегнуть к тесту. Он усадил всех трех кандидатов на скамью и попросил их зажмурить глаза.

Проф. Ах. На каждого из вас я надену синюю или красную шляпу. Прошу не открывать глаза без моей команды.

Каждому из 3 кандидатов на медаль проф. Ах надел красную шляпу.

Проф. Ах. Прошу всех открыть глаза. Пусть каждый из вас, увидев на ком-нибудь красную шляпу, поднимет руку. Первый, кто сможет определить, какого цвета шляпа у него на голове, получит медаль.

Все трое подняли руки. Через несколько минут Джон вскочил с места.

Джон. Ах, я знаю! На мне красная шляпа!

Джон. Если бы на мне была синяя шляпа, то Мери сразу бы догадалась, — что на ней красная шляпа, так как иначе нельзя было бы объяснить, почему Барбара подняла руку.

Джон. Барбара рассуждала бы так же, как Мери, и сразу догадалась бы, что на ней красная шляпа, так как иначе нельзя было бы объяснить, почему Мери подняла руку.

Джон. А поскольку ни Мери, ни Барбара не заявили о том, что знают, какого цвета их шляпы, то их молчание означает одно: красную шляпу они видят не только друг на друге, но и на мне.

Решить эту классическую логическую задачу-головоломку не составляет особого труда, если речь идет о 3 действующих лицах. Но предположим, что их не трое, а четверо, и у каждого на голове красная шляпа.

Как быть в этом случае?

Цвет шляпы и математическая индукция

Переход в этой задаче от 3 кандидатов на награду к 4 и последующее обобщение на случай произвольного числа кандидатов познакомит вас с весьма важным методом доказательства, известным под названием «метод математической индукции». Этот метод применим лишь в том случае, когда подлежащие доказательству утверждения можно упорядочить, как ступени лестницы. Вы доказываете, что всякое утверждение истинно, если истинно предыдущее, и проверяете, что первое утверждение истинно. Но коль скоро оно истинно, то истинны и все остальные утверждения: если вы можете ступить на первую ступень, то вам удастся подняться по лестнице сколь угодно высоко (или: если вы ступаете не на первую ступень, то вам удастся подняться или спуститься на любую другую ступень).

Предположим, что у проф. Ах особенно отличились и претендуют на награду 4 студента и что он надел им на головы красные шляпы. Все четверо подняли руки. Предположим, что один из них сумел догадаться, какого цвета шляпа у него на голове, чуть раньше других. Победитель (или победительница) рассуждает так:

— Предположим, что у меня на голове синяя шляпа. Тогда все три моих товарища видят, что она синяя. Значит, каждый из них видит по 2 красные шляпы и жаждет узнать, какого цвета шляпа на голове у него самого. Но именно в такой ситуации находились действующее лица в предыдущей задаче, когда ахову награду оспаривали лишь 3 кандидата. Один из них догадался, что у него на голове красная шляпа.

Но никто из моих соперников не заявляет, что у него на голове красная шляпа, хотя прошло уже достаточно много времени, чтобы каждый мог, не торопясь, тщательно обдумать свои умозаключения. Причина молчания может быть только одна: все они видят, что у меня на голове красная шляпа. Следовательно, мое исходное предположение ложно. Значит, у меня на голове красная шляпа.

Это рассуждение (принесшее своему автору заслуженную награду) допускает обобщение на случай n кандидатов. Если число претендентов на ахову награду равно 5, то самый умный из них увидит перед собой 4 красные шляпы и вскоре поймет, что любой из его соперников может рассуждать так, как рассуждал победитель в состязании 4 кандидатов, и, следовательно, определить цвет своей шляпы. А поскольку все соперники не торопятся заявлять, что у них на головах красные шляпы, то причина подобной сдержанности может быть только одна: все они видят перед собой по 4 красные шляпы. «Значит, — заключил свои рассуждения самый умный из 5 кандидатов, — у меня на голове должна быть красная шляпа». Аналогичные рассуждения применимы в случае любого числа претендентов на ахову награду. Самый умный из n кандидатов всегда может свести задачу к предыдущему случаю, который в свою очередь сводится к предыдущему и т. д., пока задача не сведется к уже решенной задаче о 3 претендентах на ахову награду.

В свази с рассмотрением задачи в общем случае возникает интересный вопрос относительно того, насколько хорошо она определена и не содержит ли она в своих условиях чрезмерный произвол, исключающий возможность однозначного ответа. При каких предположениях задача в общем случае допускает однозначный ответ? Обязательно ли предполагать, что быстрота, с которой соображает каждый из n претендентов на ахову награду, может служить его отличительным признаком, то есть всех претендентов можно упорядочить но быстроте, с которой они думают? Нужно ли предполагать, что с увеличением n возрастает продолжительность времени, в течение которого претендент на награду успевает прийти к заключению о цвете своей шляпы? Предположим, что число претендентов на ахову награду возросло до 100 человек. Верно ли утверждение о том, что по истечении достаточно продолжительной паузы самый умный из них заявит, что у него на голове красная шляпа, затем с некоторым запозданием к аналогичному выводу придет второй по сообразительности из претендентов, затем третий и так далее до тех пор, пока последний тугодум (из лучших студентов проф. Аха) не поймет, что у него на голове красная шляпа?

Классическая задача о шляпах (или колпаках) существует во множестве вариантов. Вот один из них, отчетливо показывающий, насколько усложняется задача, если шляпы на головах действующих лиц могут быть трех или более различных цветов. Предположим, что из 5 белых, 2 красных и 2 черных шляп выбраны какие-то 5 шляп и надеты на головы 5 людей. Если все шляпы белые, то каким образом один из великолепной пятерки, более сообразительный, чем остальные, догадается, что у него на голове белая шляпа?

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

Судья соревнования на сообразительность выбирает 3 шляпы из 3 белых и 2 черных шляп. Сидящие зажмуривают глаза и открывают их по команде лишь после того, как им на головы наденут шляпы, а лишние шляпы уберут.

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

Когда же судья спрашивает у сидящего впереди, знает ли тот цвет своей шляпы, то получает ответ: «Знаю, у меня на голове белая шляпа». Каким образом сидящий впереди отгадал цвет своей шляпы?

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

Как и предыдущий вариант, эта задача также легко обобщается методом математической индукции на случай n людей «с прогрессирующей слепотой», сидящих в затылок друг другу на n стульях. Судья обходит всех участников состязания на сообразительность и каждому по очереди задает один и тот же вопрос: «Знаете ли вы, какого цвета шляпа у вас на голове?», причем первый спрашивает того, кто сидит сзади, потом сидящего перед ним и т. д. Запас шляп состоит из n белых и n − 1 черных шляп. Рассмотрим случай n = 4. Сидящий впереди «слепой» знает, что если шляпа черная, то трое сидящих сзади него видят ее и знают, что среди доставшихся им шляп черных не более двух. Тем самым задача сводится к предыдущей. Если на вопрос судьи сидящий сзади и тот, кто сидит непосредственно перед ним, ответили бы отрицательно, то сидящий непосредственно за «слепым» ответил бы утвердительно, как и в предыдущем случае. А поскольку он отвечает утвердительно, то «слепой» отбрасывает свое первоначальное предположение как ложное и заключает, что его шляпа должна быть белой. Математическая индукция позволяет распространить доказательство на случай n человек. Если на вопрос судьи все, кроме «слепого» отвечают отрицательно, то у всех n на головах должны красоваться белые шляпы.

Теперь мы уже достаточно подготовлены и к более трудному варианту. Предположим, что трем участникам состязания на сообразительность судья раздает шляпы, выбирая их в любом наборе из 3 белых и 2 черных шляп. Участников состязания судья опрашивает в том же порядке, что и прежде. Будет ли кто-нибудь из них на вопрос судьи всегда отвечать утвердительно? Предоставляем вам возможность самостоятельно решить эту задачу и доказать, что ее можно обобщить на случай n человек и n белых и n − 1 черных шляп. Кое-кто из участников на вопрос судьи всегда будет отвечать утвердительно. Первый, кто всегда отвечает судье утвердительно, — это первый из тех, кто сам носит белую шляпу и не видит ни одной белой шляпы перед собой.

Шляпы двух цветов эквивалентны шляпам, пронумерованным двоичными числами 0 и 1. Во многих задачах такого типа цвета шляп отличаются большим разнообразием (одну из таких задач мы рассмотрели) и разобраться в них легче, если каждый цвет заменить соответствующим натуральным числом. Рассмотрим, например, следующую игру для 2 лиц.

Судья выбирает любую пару последовательных натуральных чисел. Кружочек с одним из этих чисел судья приклеивает на лоб одному игроку, а кружочек со вторым числом — на лоб другому игроку. Каждый игрок видит число на лбу у другого, но не видит числа у себя на лбу.

Судья по очереди спрашивает у каждого из участников, знает ли тот, какое число у него на лбу, до тех пор, пока кто-нибудь из них не назовет число у себя на лбу. Методом математической индукции можно доказать, что если большее из 2 чисел равно n, то один участник игры ответит «да» n или n − 1 раз. Доказательство этого утверждения начинается с рассмотрения простейшего случая: чисел 1 и 2. Человек с числом 2 на лбу отвечает «да» на первый или на второй вопрос (в зависимости от того, к кому из двух участников игры судья обратится прежде), так как, видя на лбу у партнера число 1, он сразу же заключает, что у него самого на лбу число 2.

Рассмотрим теперь случай, когда выбраны числа 2 и 3. На первый вопрос человек с числом 3 на лбу ответит «нет», потому что у него на лбу могло бы стоять и число 1, и число 3. Затем он может рассуждать так: «Предположим, что у меня на лбу число 1. Тогда мой партнер, у которого на лбу число 2, на вопрос судьи ответил бы «да» (как в предыдущем случае). Следовательно, если он ответит «нет», то это будет означать, что у меня на лбу стоит число 3, а не 1». И когда судья задаст игроку с числом 3 на лбу свой вопрос вторично, тот ответит «да». Так же как в задачах со шляпами, это рассуждение обобщается на случай любых двух последовательных натуральных чисел.

Для полного решения задачи необходимо лишь знать, в каких случаях игрок ответит «да» на n-й вопрос и в каких на (n − 1)-й вопрос. Исследовав задачу до конца, вы убедитесь в том, что это зависит от двух причин: во-первых, от того, кому из игроков судья задает первый вопрос, и, во-вторых, от четности числа n.

Более тонкое обобщение задачи было исследовано недавно знаменитым математиком из Кембриджского университета Джоном Хортоном Конуэем. Вот что оно собой представляет. Каждому из n участников игры на лоб приклеивается кружок с номером. Номера могут быть любыми неотрицательными целыми числами. Сумма всех этих чисел равна одному из k чисел (k ≤ n), выписанных на доске, среди которых нет двух одинаковых. Все участники игры по предположению обладают безграничной мощью интеллекта и отличаются абсолютной честностью. Каждый участник игры видит все номера, кроме своего, и все числа на доске.

Первого из участников игры спрашивают, может ли он назвать свой номер. Если он отвечает «нет», то тот же вопрос задают второму и так далее по кругу до тех пор, пока один из участников не ответит «да». Конуэй утверждает (хотя это кажется невероятным), что рано или поздно кто-то из участников непременно ответит «да».