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

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

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

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

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

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

Пусть мудрецы условились действовать по следующей тактике. Если мудрец видит две одноцветные метки у других мудрецов, то он называет другой цвет, иначе говорит «пас». Тогда мудрецы будут спасаться во всех случаях, кроме ситуаций, в которых все три метки метки одного цвета. То есть мудрецы спасутся в 6 ситуациях из 8.

Фокусник, видя набор из четырех карт на столе должен понимать, какие числа выбрали первый и второй зритель. Всего способов у зрителей выбрать два числа . С другой стороны на каждый такой выбор должна быть своя четверка оставшихся на столе карт. Но таких четверок — противоречие.

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

Все 100 гарантированно спастись не могут, так как изначально ни один из мудрецов не может гарантированно определить цвет своего колпака.

Покажем, как спастись 99 мудрецам. Пронумеруем цвета числами от 1 до 10. Сначала первый последний мудрец называет сумму номеров цветов на колпаках 99 впереди стоящих (по модулю 10). Тогда предпоследний мудрец знает сумму первых 98 чисел, а также сумму первых 99 чисел, поэтому сможет вычислить цвет своего колпака. Аналогично на очередном шаге мудрец знает цвета колпаков всех, стоящих после него (кроме последнего), и всех, стоящих перед ним, а следовательно и свой. То есть первые 99 мудрецов в ряду гарантированно спасаются.

Расставим цвета в вершины правильного семиугольника. Когда гномам наденут колпаки, каждый из них будет знать 2 возможных цвета своего колпака (так как он будет знать 5 цветов других гномов). Он смотрит на эти 2 цвета. Смотрим на расстояние между ними (то есть кратчайший путь) по вершинам семиугольника. Пройдем по этому пути по часовой стрелке. Каждый гном будет выбирать цвет, в который о пришел. Легко видеть, что тогда всегда ровно 3 мудреца будут отвечать правильно.

Пусть колпаков белого цвета было 50. Тогда все мудрецы с черными колпаками заведомо угадают цвет своего колпака, поскольку видят 50 белых колпаков. Если же мудрец видит видит поровну черных и белых колпаков, то путь он будет действовать так. Он будет называть тот цвет, который преобладает среди 49 человек, следующих за ним по часовой стрелке. Рассмотрим пару мудрецов в белых колпаках, такую, что между ними с каждой стороны ровно по 24 мудреца в белых колпаках. Заметим, что на одной из 2 частей (дуг), на которые они поделили стол сидят не больше 48 людей, из которых ровно 24 имеют белый цвет колпака. Тогда эта часть была рассмотрена одним из выбранных мудрецов, причем в нее также вошел второй выбранный мудрец, то есть уже 25 человек с белыми колпаками. Тогда выбранный мудрец ответит верно. То есть мы разбили всех людей в белых колпаках на 25 пар, в каждой из которых хотя бы ё человек ответит верно. Тогда верных ответов хотя бы .

Пусть мудрецы будут действовать следующим образом. Первый мудрец предполагает, что сумма всех чисел по модулю 10 равна 0, второй — что сумма всех 10 чисел равна 1,, последний — что сумма всех чисел равна 9 (все по модулю 10). Тогда понятно, что хотя бы один мудрец сделал правильное предположение о сумме всех 10 чисел. Каждый мудрец видит числа других 9 мудрецов. Поэтому, опираясь на свое предположение, он вычисляет и свое число. Тогда тот человек, предположение которого оказалось верным, угадает свое число.

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

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

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

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

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

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

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

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

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

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

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