МАТЕМАТ ИЧ Е С К ИЙ КР У ЖОК
Что не так с угадыванием шляп?
К.КОХАСЬ
–П
РИВЕТ, ДРУЗЬЯ, Я РАД ЧТО ВЫ СНО- ва у экранов телевизоров! Впрочем, отсюда мне вас совершенно не видно. С вами Горгулий, научный обозреватель «Самого первого канала». Очередная программа «Что не так?», посвященная ломке стереотипов и ниспровержению стандартов научного мировоззрения, готова порадовать зрителей незабываемым феерическим выпуском. По традиции мы выбираем тему программы среди вопросов, присланных телезрителями. «Что не так с угадыванием шляп?» – спрашивает нас телезритель Пинок Тухх. Отвечает на вопрос наш замечательный эксперт по вопросам неадекватности – дятел Спятел! Прошу вас, маэстро. – Добрый вечер, уважаемые телезрители. Прежде всего, для правильной расстановки акцентов, мне хотелось бы уточнить, что я являюсь экспертом по вопросам адекватности. Если наш ведущий будет продолжать путаницу, то в следующем выпуске нам придется обсудить вопрос «Что не так с нашим ведущим?» Ясно? – Извините, извините, дорогой маэстро. Я надеюсь загладить свою вину, смотрите: в этой коробке лежат несколько черных и белых шляп, они могут существенно повысить адекватность нашего разбирательства. – Тогда приступим к конкурсу «Угадывание». Я попрошу оператора показать крупным планом насекомое Musca domestica. – Это же обычная домашняя муха! – Совершенно верно. Итак, уважаемые телезрители, пока вы любовались мухой, ассистенты надели на меня и на Горгулия по шляпе. Вам прекрасно видны цвета обеих шляп, а вот я хорошо вижу шляпу Горгулия,
DOI: https://doi.org/10.4213/kvant20191105
но, увы, не могу понять, какого цвета шляпа на мне. – Я тоже не знаю цвета своей шляпы, – подхватил Горгулий, – но при этом прекрасно вижу шляпу дятла Спятла. И что же мы будем угадывать? – По правилам конкурса мы должны, не разговаривая и не подавая друг другу никаких сигналов, попытаться угадать цвет своей шляпы. У каждого из нас есть пультик с кнопками «черная» и «белая», мы должны незаметно нажать на одну из кнопок! – Но маэстро, вряд ли нам обоим удастся угадать цвет своей шляпы. Ведь о цвете своей шляпы у нас нет никакой информации! – Правильно. Но если хоть один из нас угадает, это будет считаться нашей победой в конкурсе! – Что-то тут не так. Каждый из нас вообще ничего не знает о цвете своей шляпы. Как же мы сможем хоть что-нибудь угадать? – Вы забываете, что один из нас является выдающимся экспертом по вопросам адекватности! Конечно, мы сможем преодолеть этот конкурс! И дело тут вовсе не в том большом зеркале, которое не видно телезрителям, но прекрасно видно нам. Мы сможем выиграть этот конкурс… с помощью интеллекта! В самом деле, дорогие телезрители, согласитесь, что имеется всего лишь две возможности – либо наши шляпы одинакового цвета, либо разного. Сейчас мы будем нажимать на кнопки, причем я буду нажимать на кнопку, исходя из предположения, что наши шляпы одинакового цвета, а мой коллега будет исходить из того, что цвета разные! Мы не знаем, какая из этих гипотез осуществилась на самом деле, но одна из гипотез точно осуществилась, и тот, кто придерживался этой гипотезы, угадает цвет! – Маэстро, это потрясающе. Но что мы будем делать, если наш телезритель Пинок Тухх попросит провести конкурс, в котором шляпы будут не двух, а, скажем, восьми цветов? – Мы позовем еще 6 друзей и проведем аналогичный конкурс! На каждого из восьми участников помощники наденут шляпу одного из 8 цветов, каждый будет видеть шляпы у остальных, но не свою собственную. И точно так же нужно, чтобы хотя бы один участник угадал цвет своей шляпы!
36
КВАН T 2019/№11
– Пультики приготовить с восемью кнопками? – Да. А чтобы не путаться с цветами, лучше просто поместить на каждой шляпе число от 0 до 7 и говорить не об угадывании цвета, а об угадывании числа на шляпе. – Неужели мы справимся? – Элементарно. Мы разобьем все возможные расклады шляп на 8 взаимоисключающих случаев: сумма чисел на всех шляпах либо делится на 8, либо дает остаток 1, либо остаток 2 и так далее. Последняя, восьмая, возможность – сумма дает остаток 7. Каждый из нас выберет по одной гипотезе и будет ее придерживаться. Например, если мне досталась гипотеза «сумма дает остаток 2», то я складываю все числа, которые вижу у остальных, и называю число, которое нужно добавить к этой сумме, чтобы получился остаток 2. – Кажется, мы действительно выиграем этот конкурс. Если я правильно догадался, по вашему алгоритму всегда угадывает ровно один участник. Таким образом, каждый участник «берет на себя» 1 8 от числа всех возможных раскладов шляп и угадывает только на них. А если мы увеличим число цветов шляп, не изменив число участников, например будем давать участникам шляпы девяти цветов, баланс нарушится, они смогут победить лишь в 8 9 всех случаев. Но все же я думаю, что мы просто обязаны удовлетворить любопытство нашего телезрителя, Пинока нашего Тухха, и объяснить, нельзя ли хоть немного увеличить число шляп, оставив количество участников конкурса прежним? – Да вы просто маньяк с этим вашим Пиноком Туххом. Можно! Но при условии, что одним участникам вы будете давать шляпы существенно большего количества цветов, а другим – шляпы меньшего числа цветов. – Отличная сделка! Согласен. Это будет впечатляющее зрелище. Сейчас же закажу для этого подходящий комплект шляп, и мы продемонстрируем это зрителям. Давайте позовем автора нашего вопроса Пинока Тухха в студию и наибольшее число шляп дадим ему! Сколько это будет? Сто? Двести? – Хе-хе, боюсь, ответ может вам показаться неприемлемым. Во всяком случае, он больше.
– Сколько же? Тысяча? Миллион? Миллиард? – Видите ли, дорогой Горгулий, ваши приемы работы, несомненно, производят впечатление. Но подозреваю, что Пиноку Тухху ваш энтузиазм… не придется по душе. Все дело в том, что вы наивно полагаете, что сумеете прочесть число, являющееся ответом на ваш вопрос. Но так ли это? Первый участник нашего конкурса будет получать шляпы всего двух цветов. Пожалуй, это буду я. Второму участнику – не возражаю, если это будете вы – будут давать шляпы трех цветов. – Не нагнетайте, маэстро, я вполне готов нести ответственность за свои слова и займу почетное предпоследнее место. – Хорошо. Третий участник должен осилить шляпы 7 цветов, четвертый – шляпы 43 цветов… – Ой. – Пятый – шляпы 1807 цветов, шестой – шляпы 3 263 443 цветов… – Ой, ой, ой… – Седьмому участнику, то есть вам, мой самоуверенный друг, придется иметь дело со шляпами 10 650 056 950 807 цветов… – Десять триллионов с хвостиком… – Это сущая мелочь по сравнению с тем, что мы приготовили восьмому участнику – Пиноку вашему, незабвенному Тухху, количество его цветов равно 27-значному числу, вот оно:
113 423 713 055 421 844 361 000 442.
– Мама… – И обратите внимание, как виртуозно у нас все подобрано: при любом раскладе шляп будет угадывать ровно один участник, при этом первый участник будет угадывать ровно на половине всех раскладов, второй – на одной трети, третий – на одной седьмой и так далее. Стоит ли говорить, что сумма обратных величин указанных чисел в точности равна 1! Есть только один подвох… – Еще один? Какой же? – Алгоритм, с помощью которого мы можем выиграть. Он… не совсем очевиден. – Аааааа! Уважаемые телезрители, мы опять испытываем проблемы с адекватным завершением нашей программы. Безобиднейшая игра с двумя шляпами довела нас до умопомрачительного количества цветов! Мы