Олимпиадная задача с драконом о гномах и колпаках на теорию алгоритмов
Задача
Дракон запер в пещере шестерых гномов и сказал: "У меня есть семь колпаков семи цветов радуги. Завтра утром я завяжу вам глаза и надену на каждого по колпаку, а один колпак спрячу. Затем сниму повязки, и вы сможете увидеть колпаки на головах у других, но общаться я вам уже не позволю. После этого каждый втайне от других скажет мне цвет спрятанного колпака. Если угадают хотя бы трое, всех отпущу. Если меньше – съем на обед". Как гномам заранее договориться действовать, чтобы спастись?
Решение
Решение 1: Каждый гном видит все колпаки, кроме двух: своего и спрятанного. Надо договориться, какой из двух цветов назвать. Это можно сделать, например, так.
Пронумеруем цвета числами от 1 до 7 (например, в том же порядке, как и цвета радуги) и заранее расположим их по кругу (см. рис.).
Решение 2: Если гном не видит два цвета одной чётности, то он называет цвет с большим номером, а если цвета, которые он не видит, имеют разную чётность, то он называет меньший номер. Какой бы цвет ни имел спрятанный колпак, его назовут ровно три гнома. Например, если спрятан колпак цвета 3, то угадают гномы, на которых надеты колпаки цветов 1, 4 и 6. Остальные случаи можно разобрать аналогично.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь