Недели три назад собрались мы попить пиво с друзьями и часа в 2 ночи дружеская посиделка превратилась в коллективное решение различных задач. Одна из задачек мне понравилась, понравилась тем что с первого взгяда решения не может быть, а на самом деле есть.
Есть у задачи обычное условие и усложненное, которое придумал Добрый.

Обычное условие:
Дракон поймал N гномов (количество не важно, пусть будет 15) и говорит:
- Завтра утром я выстрою вас в шеренгу (в ряд, гномы смортят в спину переди стоящего ;) ). Я буду надевать на голову каждому гному шапку черного или белого цвета, начиная с первого гнома по порядку до последнего.
Затем, надев все шапки, начну с последнего по порядку спрашивать какая шапка на нем надета. Если гном угадает - то остается в живых. Если нет - дракон его съедает.
Гномы посовещались ночь и придумали, как отвечать так, чтобы в худшем случае погиб 1 гном, а в лучшем - все остались живы.
Вопрос: Что придумали гномы?

И чтоб не было вопросов:
- Гномы могут отвечать только "черная" или "белая", и только когда их спрашивает дракон.
- Количество белых и черных шапок может быть любым (т.е. драком может надевать ЧБЧЧЧББ... или ЧЧЧЧЧБ..)
- Они не могут передвигаться, меняться местами, оглядываться.
- Гномы МОГУТ посмотреть какие шапки надеты на всех впереди стоящих.
- Они слышат что говорят стоящие сзади, но не знают правильно ли ответили.
- Они НЕ могут использовать языки жестов, и вообще любое невербальное общение, а также говорить на разных языках.
- Задача чисто алгоритмическая!

Ее я решил, но вот с дополнительным условием сложно:
Задача усложняется тем, что шапки могут быть разных цветов, например: красная, белая, зеленая, синяя, желтая.... 8-(

Если кто знает решение, не пишите, пусть другие голову поломают.
А вот если сможете решить дополнительное условие - скажите плиз ;)