|
|
 |
Условие
Одиннадцати мудрецам завязывают глаза и надевают каждому на голову колпак одного из 1000 цветов. После этого им глаза развязывают, и каждый видит все колпаки, кроме своего. Затем одновременно каждый показывает остальным одну из двух карточек – белую или чёрную. После этого все должны одновременно назвать цвет своих колпаков. Удастся ли это? Мудрецы могут заранее договориться о своих действиях (до того, как им завязали глаза); мудрецам известно, каких 1000 цветов могут быть колпаки.
Решение 1
Сопоставим цветам десятизначные двоичные числа. Каждый мудрец возьмет первую цифру своего соседа слева, вторую цифру второго мудреца влево от него, третью цифру третьего мудреца слева, последнюю цифру своего соседа справа. Если среди этих цифр число единиц чётно, он покажет чёрную карточку, иначе белую. Каждый мудрец знает, что каждая цифра его номера участвовала в вычислении одного из мудрецов, и знает все остальные цифры, участвовавшие в вычислении, поэтому он способен угадать все свои цифры.
Решение 2
Существует ровно 211 11-разрядных последовательностей из 0 и 1, из них с чётным числом единиц – ровно половина, то есть 210 = 1024. Закодируем тысячу цветов тысячей таких последовательностей. Распределим разряды между мудрецами. k-й мудрец среди видимых им 10 цветов колпаков подсчитывает число ak тех, у кого в k-м разряде стоит 1. Если это число чётно, он показывает чёрную, а в противном случае – белую карточку.
После этого каждый мудрец может вычислить все разряды в коде цвета своего колпака, кроме одного – за который он сам отвечает. Для этого он подсчитывает число bk единиц в k-х разрядах девяти мудрецов (кроме себя и k-го мудреца), и если чётность bk совпадает с показанной чётностью ak, у него в k-м разряде 0, иначе 1. Недостающий разряд восстанавливается благодаря чётности общего числа единиц в коде.
Ответ
Удастся.
Замечания
8 баллов
