Есть идея! - [46]
Шляпы двух цветов эквивалентны шляпам, пронумерованным двоичными числами 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 парикмахерских, то каждый из парикмахеров вынужден стричься у своего конкурента. Джон мудро рассудил, что ему лучше подстричься у парикмахера-грязнули, потому что именно он так аккуратно подстриг владельца парикмахерской, блиставшей чистотой и порядком.
А вот еще одна задача, очень близкая по духу предыдущей. Два горняка после долгого трудового дня в шахте поднялись на поверхность. У одного из них лицо было чистым, у другого запорошено угольной пылью. У выхода с шахтного двора горняки пожелали друг другу спокойной ночи. Горняк с чистым лицом прежде, чем отправиться домой, вытер лицо носовым платком. Горняк с лицом, запорошенным угольной пылью, отправился домой в таком виде, как был. Можете ли вы объяснить их не совсем обычное поведение?
