Здравствуйте!
Народ помогите решить след. задачку:
Людоед поймал N гномиков. И сказал, что завтра наденет на них разноцветные колпачки в K-цветов (количество колпачков неизвестно). 
K<N.
Он поставит их в ряд, друг за другом.
Каждый из гномиков будет видеть только колпачки, которые надеты на всех впереди стоящих (т.е.последний гномик будет видеть, что надето на всех гномиках впереди него, а первый гномик-никого не будет видеать ).Причем каждый гномик не увидит какого цвета колпачок надет на нём. Разговаривать и подавать знаки они не смогут. Людоед будет их спрашивать по одному, начиная с последнего гномика, какой колпачёк на нём одет. Если гномик ответит правильно, то он его отпустит, если нет - съест. За ночь гномики должны придумать оптимальную стратегию поведения, что спаслось мах. кол-во гномиков. Что они придумают?
Подсказка: кол-во спасенных гномиков будет больше N/2

Это сообщение отредактировал(а) FoxyMia - 3.9.2007, 20:01

Честно говоря, странно. Вот простой пример.

У нас есть 3 гномика. Людоед выкрасил их в красный и синий цвета. Первого и второго - в красный, третьего - в синий.
Первый гномик ничего не увидел и не знает - съел. Второй гномик ничего из этого (он знает, что первый в красном) не получит - его тоже съедят. Третий, естественно, спасется.

Гномики смогли спасти 1 человек из 3. Это меньше половины.

Извините за неточность, людоед начинает спрашивать с конца ряда, т.е. с  самого послденего гномика, котрый видит всех

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

ну да я тоже рассматривала такой алгоритм, но он дейтсвительно не спасет мах. кол-во гномиков.
доалвьно просто решаеся задачка, если там всего 2 цвета колпачков-там гномики просто договариваются что последний гном сосчитав кол-во например белых колпачков, если оно четное-говорит БЕЛЫЙ
(нечетное-ЧЕРНЫЙ), его могут сожрать, но тогда гномиик будут знать, что у последнего был черный колпачок, и уже предпоследний -сам сможет вычислить свой цвет, и так по цепочке.
спасутся все кроме последнего, у которго кстати шанс выжить 50/50.

Но к сожалению тут К-кол-вл цветов и поентому я не знаю как здесь поступить.

[сорри, ступил:]

Это сообщение отредактировал(а) SelenIT - 3.9.2007, 22:03

Условие задачи некорректно. Количество колпачков, с одной стороны, неизвестно (см. по тексту). С другой стороны (по тексту же), на КАЖДОГО гномика будет надет колпачок, т.е. количество колпачков будет равно количеству гномиков.

Если же допустить, что в условии ляп и неизвестно количество ЦВЕТОВ колпачков - то задача решаема только в том случае, если известен ПОЛНЫЙ НАБОР возможных цветов колпачков. Пусть даже людоед о половине из них не знает, а половину ему известных - не использует.

Так вот - при известном ПОЛНОМ наборе возможных цветов максимум будет съеден один гномик - тот, кто стоИт последним и кому отвечать первым. А если ему повезет (на что, впрочем, шансов мало) - то людоед вообще останется голодным.

Количество колпачков равно кол-ву гномиков естественно, но количесвто цветов этих колпачков-К
т.е.  гномиков N , а цветов колпачков-К,
K<N
т.е. у вас может быть  5 гномиков, а на них надето колпачков хоть 2-х цветов, хоть 3-х цветов, хоть 4-х цветов, лишь бы меньше кол-ва гномиков. (5 гномиков, 4 цвета: красн, зел, синий, бел.)

Очень и очень давно было такое понятие "Бит четности". Задача решается точно по такому же принципу, как и работает это понятие. Дальше подсказывать уже не буду. Теряется весь кайф решения задачи  При таком решении, максимальная потеря 1 гном 

Это сообщение отредактировал(а) Fin - 3.9.2007, 23:25

FoxyMia, Повторяю - пофиг сколько цветов, но ВСЕ ОНИ должны быть гномикам заведомо известны. И вовсе необязательно 

Вполне возможно, что гномиков пятеро, а колпачок на каждом может быть любого из цветов радуги (т.е. из 7). Впрочем, очевидно, что количество ИСПОЛЬЗОВАННЫХ цветов из этого набора будет не больше количества гномиков.

Суть решения Fin озвучил. Остальное элементарно. Как, впрочем, очевидно и то, что колпачок гномика, отвечающего первым и соответственно стоящего последним, не видит вообще никто, кроме людоеда, т.е. этого гномика может спасти лишь случайность.

Обьясните идиоту, как можно отделаться одним?   
Мне кажется К гномиков надо, чтобы каждый назвал четность К-го цвета.

Очень просто... 

Обозначаем все возможные цвета числами от 0 до К-1.
Последний гномик складывает числа цветов всех колпаков, которые видит, и называет цвет, соответствующий остатку деления полученной суммы на К.
Предпоследний тоже считает такую сумму. Сравнив ее с тем, что сказал последний, определяет цвет своего колпака и называет его.
Пред-предпоследний тоже считает такую сумму, вычитает цвет колпака предпоследнего, определяет цвет своего колпака и называет его.
И так далее, до самого первого.

Ну а повезет последнему или нет, совпадет названный им цвет с цветом его колпака... вероятность = 1/К, т.е. ненулевая, хоть и мала.

Дак если неизвестно количество цветов или даже известно но можно в колпачке использовать несколько то вроде не решается задачка

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

Это сообщение отредактировал(а) apook - 5.9.2007, 14:52

Гран мерси   

и всетаки оптимальное решение в реальных условиях - гномик отвечающий первым ,просто называет колпак впереди стоящего..и так далее.