Есть идея!

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

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

Нелегкий выбор

Проезжая через небольшой городок по дороге в Лас-Вегас, Джон обнаружил в своей автомашине неисправность. Оставив машину в ремонтной мастерской, он решил пойти подстричься.

В городке было всего две парикмахерских. Одна из них принадлежала Биллу, другая Джо.

Заглянув через витрину в парикмахерскую Билла, Джон передернулся от отвращения.

Джон. Какая ужасная грязь! На зеркалах толстый слой пыли, на полу валяются волосы, владельцу парикмахерской не мешало бы побриться, да и подстрижен он кое-как.

Джон перешел на другую сторону улицы и решил попытать счастья у Джо.

Заглянув сквозь витрину в парикмахерскую Джо, Джон увидел иную картину.

Джон. Совсем другое дело! На зеркалах ни пылинки, пол чисто подметен, и сам Джо аккуратно подстрижен.

Но в парикмахерскую Джо наш Джон так и не зашел. Он предпочел подстричься в грязной парикмахерской у Билла. Почему?

Кому отдать предпочтение?

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

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

В кресле у парикмахера

Парикмахера Билла вряд ли кто-нибудь мог назвать молчуном. Едва Джон уселся в кресло, как Билл принялся болтать без умолку.

Билл. Должно быть, вы не здешний, сэр? Люблю стричь нездешних!

Билл. По мне, так лучше подстричь двух нездешних, чем одного здешнего!

Джон. Почему?

Билл. Потому, что за две стрижки я заработаю вдвое больше, чем за одну стрижку!