Мудрецы и фокусы

Приведем стратегию за мудрецов. Пусть мудрецы говорят “пас” до того момента, пока очередь не дойдет до первого мудреца, цвета шляп всех мудрецов перед которым имеют один и тот же цвет. Этот мудрец назовет цвет противоположный тому, шляпы которого надеты на всех предстоящий мудрецах. Каждый следующий вновь скажет “пас”.

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

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

Поскольку все раздачи шляп равновероятны, мудрецы проигрывают с вероятностью

а значит, вероятность выиграть больше

Первые двое мудрецов выбирают нечётное число. Третий выбирает совпадающее со вторым, если не может, то двойку. Если третий выбрал двойку, то четвёртый выбирает нечётное (и тогда общая сумма нечётна), если третий выбрал то четвёртый выбирает или (и тогда сумма меньше если же третий выбрал то четвёртый выбирает или (и тогда сумма больше

Заметим, что зритель может выбрать три числа способами. Четверок чисел, которые могут оказаться перед фокусниками, меньше: всего . Поэтому, как бы фокусник и помощник ни договаривались, каким-то двум тройкам, которые выбирает зритель, будет соответствовать одна и та же четверка, которую увидит фокусник. Тогда определить, какая именно тройка из двух указанных была выбрана зрителем, нельзя.

Во-первых, гарантировать выживание всех 100 мудрецов нельзя: какой бы цвет ни назвал мудрец, оказавшийся последним (тем, кто видит всех остальных), колпак на его голове может оказаться другого цвета, при этом все мудрецы все равно будут видеть ту же картину.

Теперь приведем стратегию, позволяющую выжить 99 мудрецам. Закодируем цвета остатками по модулю 2, и будем считать, что мудрецы называют не цвета, а остатки. Первым высказывается мудрец, находящийся в конце ряда. Он называет остаток суммы всех остальных чисел. Следующий мудрец, зная сумму всех остатков и видя остальные остатки, кроме своего, безошибочно определяет свой остаток. Точно также каждый следующий мудрец может определить цвет своего колпака.

Предположим, что первый мудрец увидел черный колпак на голове у второго. Тогда у него на голове может оказаться как черный, так и белый колпак, и первый мудрец не сможет понять, какого цвета его колпак. поэтому на голове второго мудреца белый колпак, следовательно у первого мудреца на голове черный колпак.

Можно договориться следующим образом. Расставим эти карточки по порядку в вершины пятиугольника. Если зритель выбирает пару соседних вершин, то ассистент выбирает пару соседних, сдвинутую на 2 по часовой стрелке. если же зритель выбирает пару вершин, образующую диагональ, то ассистент выбирает пару, отличающуюся от этой сдвигом на 1 по часовой стрелке.

Поскольку количества колпаков различных цветов принимают все значения от 0 до 24.

Далее, каждый мудрец считает количество колпаков каждого из цветов. Для двух цветов количества колпаков совпадают и мудрец понимает, что на нём колпак одного из этих двух цветов. Остаётся только сделать выбор, какой именно из этих двух цветов ему назвать.

Инверсией в перестановке называется всякая пара индексов такая, что и Чётность числа инверсий в перестановке определяет чётность перестановки. Стратегия, приведённая ниже, основана на понятии чётности перестановки.

Пусть мудрецы заранее занумеровали цвета числами от 0 до 24. Тогда истинному распределению колпаков соответствует перестановка

Если мудрец видит равное количество колпаков цвета и цвета (по штук каждого из этих двух цветов), то ему нужно принять решение, к какому из этих двух цветов отнести свой колпак, то есть выбрать между двумя перестановками

Одна из этих перестановок соответствует истинному распределению цветов, при этом указанные перестановки отличаются расположением ровно двух элементов, поэтому имеют разную чётность.

Мудрецы могут заранее договориться, чтобы ровно 150 из них сделали свой выбор в пользу чётной перестановки, а остальные 150 — в пользу нечётной перестановки.

Тогда ровно 150 мудрецов верно назовут цвет своего колпака.

Можно переформулировать условие задачи так, что каждую минуту король даёт всем золотую монету, а потом сразу же забирает её у кого-то одного. Тогда давайте проделаем эту операцию раз и десять раз заберём монету у первого, девять раз у второго, восемь раз у третьего, …, один раз у десятого. То есть каждому из мудрецов в итоге дали монет и забрали столько, сколько у них имелось до начала всех раздач (операций). Тогда у всех мудрецов будет ровно по монет.

Сопоставим каждой паре чисел, которую мог выбрать зритель, различную тройку чисел, содержащую эту пару. Одно из возможных соответствий:

Теперь помощнику фокусника остается лишь дополнить выбранную зрителем пару до соответствующей тройки. Так как тройки различны, фокусник, видя тройку, безошибочной определяет, какой паре она соответствует, и исходя из этого говорит, какие числа кем взяты.