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

← →
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]

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

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

← →
default © (2006-05-19 17:48) [45]

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

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

> default © (19.05.06 17:48) [45]

Ок!

← →
default © (2006-05-19 23:03) [47]

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

← →
Ajax © (2006-05-19 23:59) [48]

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

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

← →
McSimm © (2006-05-20 00:10) [49]

> Ajax © (19.05.06 23:59) [48]

это неверно.

← →
Ajax © (2006-05-20 00:13) [50]

>[49] McSimm © (20.05.06 00:10)
Можно пример когда алгоритм не сработает?

← →
McSimm © (2006-05-20 00:36) [51]

2+0 = 1+1

← →
SergP © (2006-05-20 04:41) [52]

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

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

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

← →
SergP © (2006-05-20 04:56) [53]

Хотя ИМХО

> Ajax © (19.05.06 23:59) [48]

прав..

← →
Копир © (2006-05-20 07:55) [54]

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

← →
Гарри Поттер © (2006-05-20 10:18) [55]

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

← →
McSimm © (2006-05-20 12:17) [56]

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

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

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

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

>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 ее суммой нельзя

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

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