Решение задачи 460

Условие:

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

Решение:

Закодируем все цвета различными последовательностями из 0 и 1, но длины не 10, а 11. И с условием, что количество единиц в этих последовательностях четно. Таких последовательностей 2¹⁰=1024, что больше 1000, значит мы сможем закодировать цвета разными кодами.

Пронумеруем мудрецов от 1 до 11. Каждый мудрец будет отвечать за какой-то разряд, k-ый мудрец — за k-ый разряд. Рассмотрим мудреца, пусть он отвечает за k-ый разряд. Он видит перед собой 10 одиннадцатизначных кодов и считает количество единиц в k-ом разряде у всех кодов. Если это число четно, то он показывает белую карточку, если нечетно — черную.

Как мудрецы будут угадывать свой цвет? Возьмем первого мудреца, он отвечает за первый разряд. Он видит сколько всего единиц во втором разряде у остальных мудрецов. Еще он видит что показывает второй мудрец, поэтому может определить цифру, стоящую во втором разряде его кода. Аналогично он восстанавливает цифры во всех разрядах, кроме первого. Чтобы определить цифру первого разряда он вспоминает, что в его коде количество единиц четно (мы так изначально закодировали!) и восстанавливает цифру. Аналогично действуют остальные мудрецы. Получается, мудрецам удастся назвать свои цвета.

Ответ: Да.