мозголомки

[х]

как вы их решаете?и так то понять сложно

[НекрЫсь]

Марри Беррондо по этому поводу придумала фразу "В стране удивительных целых чисел"

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

Трехцветные гномы, способ 2.

Сотый гном говорит К в любом случае если число красных нечетно, Ж, если число желтых и только желтых нечетно, С, если число синих и только синих нечетно. При этом он конечно же остается в живых с вероятностью 33%.

В случае С и Ж все гномы сразу получают полную информацию о четности или нечетности всех трех цветов (и спасаются все). В случае К (вероятность которого 33 %) гномы не знают, были ли С и Ж оба четными или оба нечетными. Все гномы в Красных колпачках спасаются, а первый гном в НЕ красном колпачке увидит перед собой один из НЕ красных цветов четным, другой нечетным. И будет должен назвать нечетный цвет, рискуя в 50% (из той трети, которую составляет случай К). таким образом общая вероятность выживания ДРУГОГО гнома окажется аж 83% (!), что выше, чем в предложенном мною способе (там вероятность для ДРУГОГО была 50%). Так что суммарная вероятность (как бы ее не считать) действительно окажется выше при такой тактике, хотя общее число гарантированно выживших гномов останется таким же - 98.

Не говоря уж о том, что этот способ компактнее и проще для запоминания гномами.
_________________
Dum spiro - spero
Spero, ergo sum

[НекрЫсь]

Остается добавить, что дальнейшее увеличение цветов видимо заставит задачку распадаться на решение отдельных задач. Так с пятью цветами изначально надо будет поделить цвета в группы, содержащие 2 и 3 цвета, после чего действовать исходя из ранее приведенной тактики (наудачу предположу, что при этом гарантированно выживут 97 гномов), семь цветов это отдельное решение задач на 4 и 3 цвета (96 гномов как будто) и т.д.

правда не исключено, что для большого числа цветов можно придумать еще более рациональные и принципиально отличные способы. Справедливо также и то, что чем больше цветов, тем менее реально для гномов в столь нервной обстановке отслеживать их четность и нечетность. Но это уже не арифметика, а психология.

А ведь общественное мнение считает арифметику наукой скучной, для первоклашек!
_________________
Dum spiro - spero
Spero, ergo sum

[х]

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

[Эрик М. Кауфман]

Не может быть. Что — даже если цветов 100?!
_________________
Конечно, я — засасывающая черная дыра хаоса... Но все-таки... я довольно классный!
(с) Хэнк Моуди

Если не встанешь на какую-либо сторону, то становишься врагом для всех.
(с) Раде Шербеджия

[х]

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

[х]

[НекрЫсь]

У нас, насколько я могу судить отличные коллективы в математике и программировании. Уровень задач мне не постичь, но и поговорить-то приятно. Вот куда конкурс бы.
_________________
Dum spiro - spero
Spero, ergo sum

[х]

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

[НекрЫсь]

По-моему я нашел для случая с тремя цветами колпачков эффективный способ спасения гномов при котором рискует собой ТОЛЬКО первый (как верно заметил ранее Эрик "героический") гном. Судя по всему общее решение этой задачи требует знакомства с какой-то отраслью математики целых чисел, аппаратом которой я не владею. Поэтому в решении мне пришлось ввести несколько доморощенных терминов, которые я помечаю прописными буквами, и которые имеют в тексте задачи определенный условный смысл.

Итак.
Условимся считать, что на гномах колпачки трех цветов, а именно - Красный (К), Синий (С) и Зеленый (З).
Прежде всего запишем их в строго определенном порядке
К С З
Запомним этот порядок и, исходя из него условимся считать, что Красный СЛЕВА от синего, синий СЛЕВА от зеленого, а зеленый (это важно) СЛЕВА от красного (чтобы лучше это запомнить, можно продолжить последовательность так К С З К с и так далее...)
Заметим, что каждый из цветов СЛЕВА от одного и НЕ СЛЕВА(СПРАВА) от другого из соседних.

теперь представим, что гномы построены. Как мы хорошо это знаем, сотый гном всегда рискует, с вероятностью 1/n где n число цветов, то есть в нашем случае с вероятностью 1/3. Понимая это он должен своим ответом сообщить оставшимся гномам информацию, которая позволит им спастись.
Что же видит перед собой и что при этом знает сотый гном?
Он видит 99 колпачков разных цветов.
Он может их пересчитать.
Он знает общее возможное количество цветов (в данном случае 3)
1. Героический гном пересчитывает колпачки каждого цвета, получая последовательность трех чисел такого типа
К С З
x y z
где x y z количество колпачков того цвета, под которым они записаны.
2. Героический гном производит следующую математическую операцию - делит каждое из этих чисел на количество цветов (в нашем случая 3), получая при делении целую часть и остаток. Остаток может быть нулевым (при делении нацело), а также 1 и 2 (в общем случае от нуля до n-1 включительно). Гном получает еще одну последовательность трех чисел (обозначим их a,b,c), каждое из которых 0, 1 или 2
К С З
x y z
a b c
примечание с этого момента гномов должно перестать интересовать общее число колпачков каждого цвета, они должны ориентироваться только на остатки, то есть a,b,c и результаты действий с этими числами (записанными во все той же последовательности цветов К С З слева направо).

3. Какие же результаты может получить при подсчете Героический гном?
Остаток от деления ОБЩЕГО числа колпачков которые видит Героический гном (в случае со ста гномами из всегда девяносто девять) на n, в нашем случае, где n=3 будет нулевым, то есть 99 делится на 3 нацело. Следовательно сумма остатков от деления на 3 чисел, составляющих в сумме 99 тоже должна делиться на 3 нацело или быть нулевой (мне это кажется очевидным, но для сомневающихся я готов расписать доказательство). Таким образом героический гном может увидеть перед собой следующие a,b, c

К С З
a b c
0 0 0
1 1 1
2 2 2
1 2 0
1 0 2
2 1 0
2 0 1
0 1 2
0 2 1

и никакие другие. Это девять разных сочетанийв. И гному нужно одним выкриком сообщить товарищам, какое именно он видит перед собой.

4. Отметим, что первые три сочетания 000 111 и 222 сходны - остатки всех трех цветов в них равны. Следовательно во всех этих случах 99-й гном, пересчитав колпачки разных цветов, поделив число каждого на 3, и подсчитав остатки получит одну и ту же картину - три числа, два из которых равны, а третье отличается от них на единицу - оно и поменялось.

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

0 1 2 (или 0 1 2 0 1 2 и так далее).

Введем еще одно определение. Будем считать что ноль РАНЬШЕ единицы, единица РАНЬШЕ двойки, а двойка РАНЬШЕ нуля. Я мог бы написать не РАНЬШЕ, а СЛЕВА, но не хочу спутать сравнение цветов и чисел (оба раза по чисто формальному признаку, условному порядку).
Заметим, что по этому определению каждый из остатков обязательно РАНЬШЕ одного и НЕ РАНЬШЕ (ПОЗЖЕ) другого возможного остатка.

таким образом 99 гном после подсчета получит три остатка, из которых один РАНЬШЕ двух других. Это и будет цвет колпачка на нем. 98 гном услышав это, поймет, что Героический видел три одинаковых цвета, и будет знать, какой из них был на 99-м. Этой информации ему будет достаточно, чтобы назвать колпачок, который на нем (если это неочевидно, я могу пояснить).

5. У нас остаются шесть случаев расстановки остатков, которые получает Героический гном. Во всех них три остатка - разные числа. У Героического гнома остается два цвета, чтобы закодировать информацию для этих случаев.

разобьем возможные варианты на две группы.

группа П
К С З
1 2 0
0 1 2
2 1 0

группа О
К С З
0 2 1
1 0 2
2 1 0

легко видеть, что в первой группе (П) во всех трех сочетаниях чем цвет ЛЕВЕЕ, тем остаток РАНЬШЕ. Иными словами если написать числа 0 1 2 по часовой стрелке на круге, то начиная от каждого из чисел и выписывая их по ходу часовой стрелки, мы получим эти три сочетания. Назовем эти сочетания ПРЯМЫМИ. Если Героический гном видит одно из них, он называет Синий цвет.
Во второй группе ситуация обратная и мы назовем эту группу ОБРАТНОЙ. Если сотый гном видит одно из этих сочетаний, он называет Зеленый.

6. Во всех случаях сочетаний ПРЯМОЙ и ОБРАТНОЙ групп (то есть сочетаний, где остатки не равны друг другу), девяносто девятый, подсчитав остатки во всех случаях увидит перед собой сходную картину. Два остатка будут совпадать, а третий будет РАНЬШЕ двух других. Девяносто девятый гном должен будет назвать один из двух цветов, остатки для которых совпадают. В случае ОБРАТНОЙ группы (сотый назвал ЗЕЛЕНЫЙ цвет) девяносто девятый должен назвать из двух совпадающих тот, что СЛЕВА (напоминаю, что Зеленый СЛЕВА от красного). В случае ПРЯМОЙ группы (сотый назвал Синий), девяносто девятый гном должен назвать из двух совпадающих по остаткам цветов тот, который НЕ СЛЕВА (СПРАВА, если хотите).


7. После этого девяносто восьмой гном обладает следующей информацией. Он знает, что исходные (виденные Героическим гномом)
остатки были неравны. Он знает, ПРЯМУЮ или ОБРАТНУЮ группу они образовывали. Наконец он знает, какой колпачок был на 99-м, то есть, что ситуация поменялась по данному цвету на единицу (данный цвет стал РАНЬШЕ, чем был по остатку).
Сам же 98-й посчитав колпачки и получив остатки, обязательно получит ситуацию, когда два остатка совпадают, а третий отличается от них и он НЕ РАНЬШЕ (если хотите, ПОЗЖЕ) двух других.

например.
Если сотый видел ситуацию

1 2 0

девяносто девятый увидел

1 1 0 (ноль раньше двух единиц, группа прямая, следовательно поменялся более правый цвет - синий) девяносто девятый называет синий

девяносто восьмой увидит

1 0 0 или 0 1 0 или 1 1 2 (во всех трех случаях число отличающееся от других ПОЗЖЕ двух других)

8. девяносто восьмой гном должен рассуждать так.

Если среди двух совпадающих остатков нет цвета, который называл 99-й то этот цвет точно не поменялся (поменявшись два раза он обязательно оказался бы равен по остатку тому цвету, который изначально отличался от него на 2, и не менялся не разу). Следовательно поменялся цвет, который только что был ему равен. Теперь надо вспомнить какую группу ПРЯМУЮ или ОБРАТНУЮ видел перед собой сотый гном. Если он видел ОБРАТНУЮ (назвал зеленый), то 99-й назвал из двух совпадающих тот цвет, что СЛЕВА, этот цвет и поменялся на 98, поэтому из двух совпадающих надо назвать тот, что СПРАВА.
По той же причине если 100 гном назвал синий цвет, 98-й должен назвать из двух совпадающих по подсчитанному им самим остатку цветов тот, что СЛЕВА.

Если же среди двух подсчитанных 98-м гномом остатков есть то же цвет, что назвал 99-й рассуждения таковы. Если сотый назвал синий цвет, значит группа прямая, и 99-й назвал из двух совпадающих тот цвет, что СПРАВА. Если и сейчас из двух совпадающих названный 99-м СПРАВА, значит поменялся тот цвет, который с этими двумя не совпадает. Если же названный 99-м цвет сейчас в паре СПРАВА, значит он и поменялся.
Аналогичны рассуждения и для случая, когда сотый назвал зеленый.

9. Задача Героического гнома достаточно проста, хотя он и рискует жизнью. А вот пункты 6 и 8 требуют от 99 и 98 гномов крайней сосредоточенности. Если колпачки на них одного цвета, те же выводы, что и 98 придется делать 97 и так далее, к этому надо быть готовым. Однако в самом простом случае можно считать, что после вычислений и выводов 98-го гнома остальные получают полную информацию о том

какое сочетание остатков видел 98 гном.

10. И с этого момента их жизнь значительно упрощается. Они должны просто каждый раз, начиная с ответа 98 повторять это сочетание в правильном порядке (например 0 2 1) изменяя остаток, соответствующего цвета каждый раз, когда он назван, заменяя числом на единицу меньшим (точнее БОЛЕЕ РАННИМ). Это не слишком сложно, и может быть выполнено.

Мне кажется, что способ должен работать, и кажущаяся его сложность определяется исключительно самопальностью терминологии.
_________________
Dum spiro - spero
Spero, ergo sum

[х]

это надо осознать))

[Эрик М. Кауфман]

Не, тут я точно голову сломаю — это уже высшая математика какая-то пошла! А я все-таки образно мыслил.....
_________________
Конечно, я — засасывающая черная дыра хаоса... Но все-таки... я довольно классный!
(с) Хэнк Моуди

Если не встанешь на какую-либо сторону, то становишься врагом для всех.
(с) Раде Шербеджия

[НекрЫсь]

Жаль, я надеялся, что ты проверишь меня на фишках из "Нашей игротеки". Могу вывесить краткий алгоритм. Но только он все равно из 15 пунктов.

Я бы назвал это скорее высшей арифметикой.
_________________
Dum spiro - spero
Spero, ergo sum

[Эрик М. Кауфман]

Ну, давай попробуем проверить на фишках. Выкладывай алгоритм!
_________________
Конечно, я — засасывающая черная дыра хаоса... Но все-таки... я довольно классный!
(с) Хэнк Моуди

Если не встанешь на какую-либо сторону, то становишься врагом для всех.
(с) Раде Шербеджия

[НекрЫсь]

Краткий алгоритм для проверки
1. сотый гном считает все цвета, делит каждое число на 3, получает три остатка.

2. если остатки равны он называет красный. Ситуация А.
3 (А) Девяносто девятый называет тот цвет, который отличается по остатку от двух других.
4. (А) Девяносто восьмой видит два равных цвета и один отличающийся. Если отличающийся цвет не был назван девяносто девятым, значит поменялся тот из совпадающих, который также не был назван. После этого гномы получают полную информацию.
5 (А) Если отличающийся цвет был назван, значит поменялся именно он. Следующий гном должен произвести рассуждения, аналогичные рассуждениям 98-го. Как только цвет очередного колпачка будет отличаться от колпачка 99-го, гномы получат полную информацию.

6. Остатки, которые подсчитал сотый гном не равны. Ситуация Б.
7. Сотый гном определяет сочетание остатков, на принадлежность к ПРЯМОЙ или ОБРАТНОЙ группам. В первом случае он называет синий цвет, во втором зеленый.
8. 99-й гном считает колпачки разных цветов перед собой и подсчитывает остатки. Два остатка совпадают, третий нет.
9. Если сотый назвал зеленый цвет, 99-й называет из двух цветов для которых подсчитанные им самим остатки совпадают, ЛЕВЫЙ. Если сотый назвал синий цвет, 99-й называет ПРАВЫЙ.
10. Девяносто восьмой гном подсчитывает цвета перед собой и подсчитывает остатки. Два остатка совпадают, третий нет.
11. Если среди совпадающих остатков нет цвета, названного 99 м, а сотый назвал зеленый, девяносто восьмой называет из двух совпадающих тот, что СПРАВА.
12. Если среди совпадающих остатков нет цвета, названного 99 м, а сотый назвал синий, девяносто восьмой называет из двух совпадающих тот, что СЛЕВА.
13. Если среди совпадающих остатков есть цвет, названный 99-м, и он СПРАВА притом, что сотый назвал синий, или если он СЛЕВА (при том, что сотый назвал зеленый), 98-й называет тот цвет, который не совпадает с двумя другими.
14. В случаях 11-13 гномы получают полную информацию.
15. Если ни один из этих случаев не реализован, 98-й называет тот же цвет, что 99-й и умозаключения, предполагающие получение полной информации переходят к следующему гному. Как только один из колпачков не совпадает по цвету с колпачком 99-го, гномы получают полную информацию.
_________________
Dum spiro - spero
Spero, ergo sum