ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 64616
Темы:    [ Математическая логика (прочее) ]
[ Кооперативные алгоритмы ]
[ Двоичная система счисления ]
[ Четность и нечетность ]
Сложность: 4+
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

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


Решение

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


Ответ

Удастся.

Замечания

8 баллов

Источники и прецеденты использования

олимпиада
Название Турнир городов
Турнир
Номер 29
Дата 2007/2008
вариант
Вариант весенний тур, сложный вариант, 10-11 класс
задача
Номер 6

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .