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

• Название: Есть идея!
• Автор: Мартин Гарднер
• Издательство: Мир
• Жанр: Прочая научная литература
• Год: 1982

Книга известного американского популяризатора науки Mapтина Гарднера, посвященная поиску удачных идей для решений задач из области комбинаторики, геометрии, логики, теории чисел и игр со словами.

Рассчитана на самый широкий круг читателей.

---

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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