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

← →
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. Последний видит перед собой нечетное количество черных, говорит "белая".

← →
default © (2006-05-19 15:41) [29]

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

← →
jack128 © (2006-05-19 16:34) [30]

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

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

← →
Andy BitOff © (2006-05-19 16:39) [31]

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

← →
Ji © (2006-05-19 17:09) [32]

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

← →
oldman © (2006-05-19 17:14) [33]

Уточнение:

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

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

← →
McSimm © (2006-05-19 17:18) [34]

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

← →
default © (2006-05-19 17:20) [35]

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

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

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

← →
oldman © (2006-05-19 17:28) [37]

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

Насчет [5]:

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

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

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

← →
default © (2006-05-19 17:34) [38]

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

← →
McSimm © (2006-05-19 17:35) [39]

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

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

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

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

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

← →
oldman © (2006-05-19 17:40) [41]

> McSimm © (19.05.06 17:35) [39]

Я тоже "не американец", поэтому пойду и нормально подумаю... :)))
Хотя тут есть проблема:
гном может дать всего 2 ответа - Б или Ч
а вариантов 4 (Б чет, Б нечет, Ч чет, Ч нечет)...

Пойду таки подумаю.

← →
default © (2006-05-19 17:41) [42]

в принципе в [27] всё и рассказали...

← →
Cashmare © (2006-05-19 17:45) [43]

oldman © (19.05.06 17:40) [41]
гном может дать всего 2 ответа - Б или Ч
а вариантов 4 (Б чет, Б нечет, Ч чет, Ч нечет)...

Щас пойду плакать %)

← →
oldman © (2006-05-19 17:47) [44]

Все... Закрою я эту тему для себя... Пойду подумаю...

ПИВО ВРЕДНО!!! Завтра подумаю, пожалуй...

saxon (19.05.06 17:39) [40]
"Подумал может кому интересно будет."
понял
кстати, на будущее, лучше пиши, что ты её решил и предлагаешь решить интересующимся, а то когда я тоже так предлагал мне писали, иногда, в стиле "а самому подумать?", "что своих мозгов нет?" и тд:)

← →
saxon (2006-05-19 18:05) [46]

в продолжение, для желающих
"Собрал султан N своих мудрецов и поместил в темницу
сказал им: завтра вас выведут на площадь
поставят в колонну по 1 человеку
каждому на голову наденут колпак
одного из трех цветов - красный, зеленый, синий
причем стоящий сзади будет видеть цвета колпаков каждого стоящего впереди него
но не будет видеть цвета колпака тех, кто за ним и своего собственного
каждую минуту будут бить в гонг и при этом один мудрец должен сказать цвет колпака
если этот цвет совпадет с цветом его колпака - он останется в живых
если нет - ему отрубят голову
в случае молчания головы отрубят всем
(каждый раз цвет называет разный мудрец, разумеется)
мудрецы за ночь посовещались и придумали алгоритм
сколько мудрецов можно 100% спасти"
по-моему, есть способ такой, что для любого числа цветов максимум потерять можно одного гнома

Для любого количества цветов, мудрецов, гномов и драконов задача решается с максимум 1 потерей.

Алгоритм можно описать так:
1) Кодируются цвета шапок. Например красная - 0, зеленая - 1, синяя - 2 (и так далее).
2) Первая жертва суммирует числа соответствующие цветам шапок впередистоящих, делит на количество цветов и сообщает цвет, соответствующий остатку от деления.
3) Остальные считают по стоящим впереди, уже назвавшимся сзади и необходимом остатке от деления.

2+0 = 1+1

> default © (19.05.06 23:03) [47]

> по-моему, есть способ такой, что для любого числа цветов
> максимум потерять можно одного гнома

Решение [47] с потерей одного мудреца в студию!

http://forums.avalon.ru/forum/topic.asp?TOPIC_ID=1715

Стоит одному ошибиться - сожрут его и всех остальных...
Ответственность однако :)

> Стоит одному ошибиться - сожрут его и всех остальных...

сожрут его и последующих, пока опять кто-нибудь не ошибется :)

>Стоит одному ошибиться - сожрут его и всех остальных...
>Ответственность однако :)

Ну пусть будут не гномы/мужрецы, а компьютеры/контроллеры/роботы

>McSimm © (20.05.06 00:36)

Если бы надо было назвать скажем 2 цвета, то действительно такая неоднозначность имела бы место. В описанном случае такой неоднозначности нет.

Пусть мудрецов было 4 и шапки у них всех 3 цветов. Обозначим их как R, G, B и X. Где RGB - мудрецы с шапками соответствующего цвета, а X - первая несчастная жертва, цвет шапки которой неважен. Стоят они цепочкой RGBX. X считает сумму кодов цветов впередистоящих. Получается 0 + 1 + 2 = 3. Остаток от деления на 3 - 0. X называет цвет, соответствующий 0 - красный. Теперь мудрец B знает, что цвету его шапки соответствует число, которое надо добавить к 0 + 1, чтобы получить деление на 3 с нулевым остатком. Такое число единственное (в рамках условия задачи о 3-х возможных цветах). Это число 2. И он называет цвет - синий. Для мудреца G нужно найти число, при добавлении которого 0 + 2 дает деление на 3 с остатком 0. И сново число единственное - 1. Называет цвет - зеленый. Для последнего мудреца рассуждения аналогичны.

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

> Пусть мудрецов было 4 и шапки у них всех 3 цветов.

пусть их было 10 и все шапки одного цвета с кодом 0

> Ну или еще какой-либо аргументированный довод против.

пожалуйста
1+1+1 = 2+0+1

Я даже не буду вникать в ваши рассуждения.
Закодировать последовательность 0,1,2...N ее суммой нельзя

Наверное это все-таки я протормозил, извиняюсь.

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