Мартин Гарднер - Есть идея!

Судья соревнования на сообразительность выбирает 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 ), выписанных на доске, среди которых нет двух одинаковых. Все участники игры по предположению обладают безграничной мощью интеллекта и отличаются абсолютной честностью. Каждый участник игры видит все номера, кроме своего, и все числа на доске.

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