Задачка про гномов

← →
saxon (2006-05-19 14:31) [0]

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

← →
Johnmen © (2006-05-19 14:35) [1]

баян

← →
Хельг © (2006-05-19 14:36) [2]

Ответ: гном называет цвет шапки впереди стоящего

← →
saxon (2006-05-19 14:36) [3]

Может быть.
А какой ответ?

← →
Чапаев © (2006-05-19 14:37) [4]

> выстрою вас в шеренгу (в ряд, гномы смортят в спину переди
> стоящего ;-) ).

Это называется колонной, а не шеренгой...

← →
McSimm © (2006-05-19 14:37) [5]

Например, первый спрашиваемый гном может своим ответом сообщить остальным четность/нечетность, например, черного цвета. Остальное вроде - дело подсчетов.

← →
Сергей М. © (2006-05-19 14:37) [6]

В шеренге (строка) термин в спину впереди стоящего (соотв.элемент колонки) не имеет смысла
?

← →
McSimm © (2006-05-19 14:39) [7]

> Хельг © (19.05.06 14:36) [2]

дракон был доволен и сыт, раздав шапки чередуя цвета :)

← →
Хельг © (2006-05-19 14:44) [8]

а при чем тут чередование?

← →
ilya39 © (2006-05-19 14:46) [9]

Хрень какая-то:

← →
McSimm © (2006-05-19 14:47) [10]

> а при чем тут чередование?

при том, что в этом случае ни один гном, кроме самого первого в ряду, не сможет назвать цвет надетой на нем шапки :)

> гном называет цвет шапки впереди стоящего

← →
ilya39 © (2006-05-19 14:48) [11]

> - Количество белых и черных шапок может быть любым (т.е.
> драком может надевать ЧБЧЧЧББ... или ЧЧЧЧЧБ..)

Т.е. закономерности нет? Как тогда решеть задачу т.е. выявлять закономерность?

← →
Хельг © (2006-05-19 14:50) [12]

> McSimm © (19.05.06 14:47) [10]

согласен, не прав

← →
vovnuke © (2006-05-19 15:04) [13]

первый кого спрашивают отвечает "такой же цвет как у того кто стоит впереди", если не правильно, то второй отвечает "не тот цвет какой был у того кто сзади (кого съели)"

← →
Cashmare © (2006-05-19 15:06) [14]

2vovnuke © (19.05.06 15:04) [13]
- Они слышат что говорят стоящие сзади, но не знают правильно ли ответили.

Нутром чую, что это похоже на детскую игру "бакара", но доказать не могу, не помню всех тонкостей :(

← →
vovnuke © (2006-05-19 15:08) [15]

ну если второго спрашивают то наверно не правильно или не так :-)

← →
vovnuke © (2006-05-19 15:10) [16]

еще раз перечитал вопрос, фишка в другом каждый позади стоящий гном должен сказать правильный цвет шапки впереди стоящего, в худшем случае съедят только первого :-)

← →
Хельг © (2006-05-19 15:12) [17]

> vovnuke © (19.05.06 15:10) [16]
> еще раз перечитал вопрос, фишка в другом каждый позади стоящий
> гном должен сказать правильный цвет шапки впереди стоящего,
> в худшем случае съедят только первого :-)

смотри тпики [10] и [12]

← →
vovnuke © (2006-05-19 15:13) [18]

2 [17] Хельг © (19.05.06 15:12)
ответ был дан еще в [2]

← →
Хельг © (2006-05-19 15:16) [19]

2 vovnuke © (19.05.06 15:13) [18]
угу я и довал, а в [12] чесно признался что не прав, объяснения в [10]

← →
Cashmare © (2006-05-19 15:17) [20]

А, все-таки, ответ в [5]

← →
TUser © (2006-05-19 15:17) [21]

Согласен с [9] и [11].

← →
Хельг © (2006-05-19 15:21) [22]

> Cashmare © (19.05.06 15:17) [20]
> А, все-таки, ответ в [5]

> - Гномы могут отвечать только "черная" или "белая", и только когда их спрашивает дракон.

← →
Styx_ (2006-05-19 15:23) [23]

Например, "черная" - чёт, "белая" - нечет.

← →
McSimm © (2006-05-19 15:24) [24]

> и только когда их спрашивает дракон.

а спрашивает он их по порядку, начиная с заднего. Так что все ок.

← →
Хельг © (2006-05-19 15:27) [25]

> McSimm © (19.05.06 15:24) [24]
>
> а спрашивает он их по порядку, начиная с заднего. Так что все ок.

а по подробнее можно?

← →
saxon (2006-05-19 15:28) [26]

Задача алгоритмическая.

Из условия видно несколько возможных ситуаций и их пересечений
- Гномов может быть четное число
- Гномов может быть не четное число
- Белых шапок может быть четное число
- Белых шапок может быть не четное число
- Черных шапок может быть четное число
- Черных шапок может быть не четное число

Каков должен бать алгоритм?

← →
Cashmare © (2006-05-19 15:37) [27]

Последний гном видит перед собой четное кво черных шапок - гговорит "черная". Тут его либо едят (царствие ему), либо нет (пойдет напьется за второй ДР).
Предпоследний видит, что перед ним нечетное кво черных шапок, но зная, что сказал "покойник", делает вывод о том, что на нем - черная шапка.
Препредпоследний видит, что перед ним нечетное кво черных шапок, значит ничего не изменилось, значит на нем самом - белая. И т. д. Имхо, так...

← →
wal © (2006-05-19 15:39) [28]

> [26] saxon (19.05.06 15:28)
Усложняешь. Ситуации всего две:
1. Последний видит перед собой четное количество черных, говорит "черная".
2. Последний видит перед собой нечетное количество черных, говорит "белая".

баян баянович бояновский

да ладно вам, заладили - баян, баян.

Всего один раз на Мастерах эту задачку решали ;-) вот про продажу delphi - это действительно баян..

Причем, как видно из списка обсуждающих, многие старую тему и не видели, так что для них это не баян.

Толпой завалить дракона, прикрываясь одним из гномов.

Уточнение:

если гном ответит неправильно и дракон его сожрет, на этом все прекращается (а) или продолжается дальше (б)?

если (а) - отвечай от балды, погибнет, как максимум один гном
если (б) - правильного алгоритма нет!

правильный алгоритм приведен несколько раз, начиная с [5]

oldman © (19.05.06 17:14) [33]
"если гном ответит неправильно и дракон его сожрет, на этом все прекращается "
для данного гнома да:)
"если (б) - правильного алгоритма нет!"
ну-ну

← →
dimodim-furyz (2006-05-19 17:21) [36]

Естетвенно сдонет последний в клоне гном!!

> default © (19.05.06 17:20) [35]

Насчет [5]:

Предположим гномов 5 и дракон надел шапки ЧБЧБЧ

1. Гномы договорились отвечать про черные (чет - Б, нечет - Ч)
ответы: ?ЧЧББ - погибло 2 гнома
2. Гномы договорились отвечать про черные (чет - Ч, нечет - Б)
ответы: ?ББЧЧ - погибло 2 гнома
3. Гномы договорились отвечать про белые (чет - Б, нечет - Ч)
ответы: ??ЧЧБ - погибло 2 гнома
4. Гномы договорились отвечать про белые (чет - Ч, нечет - Б)
ответы: ??ББЧ - погиб 1 гном (о, елки!)

? - это я не знаю, что думать первому гному или что должен отвечать гном если перед ним Ч или Б = 0...

oldman © (19.05.06 17:28) [37]
не хочется рассказывать всё, подсказка в [5] и так больше чем полрешения если не всё решение...если saxon хочет знать решение, а не дойти до него самостоятельно, тут ему быстро всё расскажут, но лучше самому ему дойти...

> Гномы договорились отвечать про черные

Гномы договорились, что первый отвечающий сообщает про чет или нечет, остальные без проблем совершенно безошибочно сообщают цвет своей шапки.
(Если они, конечно, не американцы.)

← →
saxon (2006-05-19 17:39) [40]

> default © (19.05.06 17:34) [38]

Я решил. Не сразу конечно но решил. Про то что ее тут уже решали не знал.
Подумал может кому интересно будет.

Задачка про гномов Найти похожие ветки