Здравый смысл и задача о разноцветных шляпах
Моя (уже, как и я сам, бородатая) задачка-головоломка про 100 мудрецов, выстроенных в ряд с надетыми на них разноцветными шляпами, как недавно выяснилось, получила неожиданное продолжение, ставящее этот сюжет в один ряд с парадоксом Банаха-Тарского...
Вот вольный перевод на русский язык этого продолжения.
Рассмотрим такую вариацию этой задачи: cчётное множество мудрецов выстроены в натуральный ряд (лицом в сторону возрастания ряда, так что каждый видит перед собой бесконечное число мудрецов). Можно считать, что каждый из мудрецов знает свой номер в последовательности. Каждому мудрецу надета на голову шляпа одного из допустимых цветов, и каждому задается вопрос о цвете его шляпы. Всех, кто дает неправильный ответ, казнят. В отличие от конечного варианта, мудрецы не слышат чужих ответов на заданные им вопросы (и не видят казней неправильно ответивших коллег) и, следовательно, не могут получать никакой новой информации. Тем не менее, они могут заранее договориться так, чтобы казнено было лишь конечное число мудрецов.
Решение этой задачи выглядит вроде бы так.
Назовем две разных цветовых последовательности принадлежащими к одному классу, если они совпадают, начиная с некоторого момента. По аксиоме выбора, из каждого класса можно выбрать по одному различному "представителю" - то есть сопоставить каждому классу одну конкретную последовательность цветов, причем все эти последовательности будут различными. Заставим мудрецов запомнить это сопоставление. Тогда, видя перед собой бесконечное число шляп, каждый мудрец легко определяет класс, в который входит данная последовательность, и отвечает на заданный ему вопрос, называя тот цвет, который находится на данном месте в последовательности-"представителе". Поскольку все последовательности одного класса различаются только в каком-то (заведомо конечном) количестве начальных позиций, то казнено могут быть только конечное число мудрецов.
[Для тех, кто не любит абстрактных рассуждений и любит "пощупать" решение руками. Давайте будем считать, что допускаются все те и только те последовательности цветов шляп, которые (после перенумерации цветов цифрами) будут представлять дробные части рациональных чисел. Как известно, каждое рациональное число - это бесконечная смешанно-периодическая дробь. Все такие дроби объединим в классы с одинаковыми периодами (и разными предпериодами). Для каждого такого класса мы называем "представителем" дробь, не содержающую предпериода. Это означает, что мы заставляе каждого мудреца называть тот цвет, который был бы у него, если бы наблюдаемый им впереди себя период продолжался в обратную сторону и на него - даже если он видит, что на ком-то из мудрецов перед ним эта периодичность уже нарушилась. Ясно, что при этом лишь конечное число мудрецов ошибется.]
В "ручной" версии я специально ограничил кол-во последовательностей счетным множеством, чтобы использовать не чистую аксиому выбора, а прямую конструкцию для установления соответствия. Однако аксиома выбора не требует счетности числа множеств - следовательно, "абстрактная" версия решения работает и в более общем случае.
Это решение кажется парадоксальным и удивительным, потому что даже для двух цветов вероятность одному отдельно взятому мудрецу угадать свой цвет равна 1/2, а значит, ожидаемая доля казненных не должна быть менее 1/2 и уж точно не должна стремиться к 0. Но совсем уж фантастичным этот результат выглядит для счётного числа цветов, а ведь приведенное доказательство обобщается и на этот случай - то есть несмотря на то, что вероятность спасти одного человека равна 0, в целом по-прежнему удается спастись всем, кроме конечного числа людей!!
Вот вольный перевод на русский язык этого продолжения.
Рассмотрим такую вариацию этой задачи: cчётное множество мудрецов выстроены в натуральный ряд (лицом в сторону возрастания ряда, так что каждый видит перед собой бесконечное число мудрецов). Можно считать, что каждый из мудрецов знает свой номер в последовательности. Каждому мудрецу надета на голову шляпа одного из допустимых цветов, и каждому задается вопрос о цвете его шляпы. Всех, кто дает неправильный ответ, казнят. В отличие от конечного варианта, мудрецы не слышат чужих ответов на заданные им вопросы (и не видят казней неправильно ответивших коллег) и, следовательно, не могут получать никакой новой информации. Тем не менее, они могут заранее договориться так, чтобы казнено было лишь конечное число мудрецов.
Решение этой задачи выглядит вроде бы так.
Назовем две разных цветовых последовательности принадлежащими к одному классу, если они совпадают, начиная с некоторого момента. По аксиоме выбора, из каждого класса можно выбрать по одному различному "представителю" - то есть сопоставить каждому классу одну конкретную последовательность цветов, причем все эти последовательности будут различными. Заставим мудрецов запомнить это сопоставление. Тогда, видя перед собой бесконечное число шляп, каждый мудрец легко определяет класс, в который входит данная последовательность, и отвечает на заданный ему вопрос, называя тот цвет, который находится на данном месте в последовательности-"представителе". Поскольку все последовательности одного класса различаются только в каком-то (заведомо конечном) количестве начальных позиций, то казнено могут быть только конечное число мудрецов.
[Для тех, кто не любит абстрактных рассуждений и любит "пощупать" решение руками. Давайте будем считать, что допускаются все те и только те последовательности цветов шляп, которые (после перенумерации цветов цифрами) будут представлять дробные части рациональных чисел. Как известно, каждое рациональное число - это бесконечная смешанно-периодическая дробь. Все такие дроби объединим в классы с одинаковыми периодами (и разными предпериодами). Для каждого такого класса мы называем "представителем" дробь, не содержающую предпериода. Это означает, что мы заставляе каждого мудреца называть тот цвет, который был бы у него, если бы наблюдаемый им впереди себя период продолжался в обратную сторону и на него - даже если он видит, что на ком-то из мудрецов перед ним эта периодичность уже нарушилась. Ясно, что при этом лишь конечное число мудрецов ошибется.]
В "ручной" версии я специально ограничил кол-во последовательностей счетным множеством, чтобы использовать не чистую аксиому выбора, а прямую конструкцию для установления соответствия. Однако аксиома выбора не требует счетности числа множеств - следовательно, "абстрактная" версия решения работает и в более общем случае.
Это решение кажется парадоксальным и удивительным, потому что даже для двух цветов вероятность одному отдельно взятому мудрецу угадать свой цвет равна 1/2, а значит, ожидаемая доля казненных не должна быть менее 1/2 и уж точно не должна стремиться к 0. Но совсем уж фантастичным этот результат выглядит для счётного числа цветов, а ведь приведенное доказательство обобщается и на этот случай - то есть несмотря на то, что вероятность спасти одного человека равна 0, в целом по-прежнему удается спастись всем, кроме конечного числа людей!!