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

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

Условие

Дракон запер в пещере шестерых гномов и сказал: "У меня есть семь колпаков семи цветов радуги. Завтра утром я завяжу вам глаза и надену на каждого по колпаку, а один колпак спрячу. Затем сниму повязки, и вы сможете увидеть колпаки на головах у других, но общаться я вам уже не позволю. После этого каждый втайне от других скажет мне цвет спрятанного колпака. Если угадают хотя бы трое, всех отпущу. Если меньше – съем на обед". Как гномам заранее договориться действовать, чтобы спастись?


Решение 1

  Каждый гном видит все колпаки, кроме двух: своего и спрятанного. Надо договориться, какой из двух цветов назвать. Это можно сделать, например, так.
  Пронумеруем цвета числами от 1 до 7 (например, в том же порядке, как и цвета радуги) и заранее расположим их по кругу (см. рис.).

  Каждый гном должен назвать тот из двух цветов, от которого до другого цвета ближе добраться по часовой стрелке. Тогда три гнома угадают, а три других ошибутся. Например, если спрятан колпак цвета 1, то угадают гномы, на которых надеты колпаки цветов 2, 3 и 4.


Решение 2

  Если гном не видит два цвета одной чётности, то он называет цвет с большим номером, а если цвета, которые он не видит, имеют разную чётность, то он называет меньший номер. Какой бы цвет ни имел спрятанный колпак, его назовут ровно три гнома. Например, если спрятан колпак цвета 3, то угадают гномы, на которых надеты колпаки цветов 1, 4 и 6. Остальные случаи можно разобрать аналогично.

Замечания

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

2. Строго говоря, решения отличаются только нумерацией цветов. Если расположить цвета по кругу, как на рисунке, то принцип действия гномов из решения 1 в точности описывает решение 2.

3. Можно доказать, что никакая договорённость не позволит наверняка угадать цвет спрятанного колпака более чем половине гномов.

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

олимпиада
Название Математический праздник
год
Год 2011
Класс
Класс 6
задача
Номер 5

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

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