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

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

Условие

Автор: Фольклор

Переаттестация Совета Мудрецов происходит так: король выстраивает их в колонну по одному и надевает каждому колпак белого или чёрного цветов. Все мудрецы видят цвета всех колпаков впереди стоящих мудрецов, а цвет своего и всех стоящих сзади не видят. Раз в минуту один из мудрецов должен выкрикнуть один из двух цветов (каждый мудрец выкрикивает цвет один раз). После окончания этого процесса король казнит каждого мудреца, выкрикнувшего цвет, отличный от цвета его колпака. Накануне переаттестации все сто членов Совета Мудрецов договорились и придумали, как минимизировать число казнённых. Скольким из них гарантированно удастся избежать казни?


Решение

Ясно, что мудрец, стоящий в колонне последним, может спастись только случайно, ведь его колпака не видит никто из мудрецов. Но он может спасти всех остальных, сообщив им чётность числа белых колпаков, надетых на них (по договоренности он скажет "белый", если это число нечётно, и "чёрный" в противном случае). Теперь мудрецы должны вычислять и называть цвета своих колпаков по порядку от предпоследнего к первому: сначала предпоследний, видя колпаки впереди стоящих и зная чётность числа белых колпаков (среди колпаков впереди стоящих и своего), легко определит цвет своего колпака и назовёт его; затем мудрец, стоящий перед ним, зная цвета всех тех же колпаков, кроме своего (передние он видит, а про задний только что услышал), по чётности может определить цвет своего колпака и назвать его. Остается продолжать описанную процедуру до тех пор, пока первый мудрец не определит цвет своего колпака.


Ответ

Всем, кроме одного.

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

web-сайт
задача
олимпиада
Название Всероссийская олимпиада по математике
год
Год 1997
Этап
Вариант 5
Класс
Класс 9
задача
Номер 97.5.9.4

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

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