Эрудиция и смекалка

[GORLAB]

Стратегию 50 я понял. 66 -не понял. Про 3 трупа мне кажется вполне логично. Впрочем, утро вечера мудренее. Я увлёкся, завтра алгоритм нарисую графически. Призову изобразительное искусство на помощь логике. И прочитаю вашу версию. Возможно в моих рассуждениях ошибка, что вполне допускаю. "Все мы немощны ибо человече" (ц). Доброй ночи.
п.с.
Курение убивает.

[Alex9797]

Обозначим численное значение цвета буквой "N", а остаток от деления суммы на 3 - буквой "p".
Первый мудрец-камикадзе называет свой остаток p(1).
Второй мудрец, зная свой p(2), вычисляет свой код цвета по формуле:
N(2) = остаток{[(3+p(1)-p(2)]/3}

Третий вычисляет свой цвет по формуле:

N(3) = остаток{[(6+p(1)-N(2)-p(3)]/3}

И для всех j=3...100 :

N(j) = остаток{[(6+p(j-2)-N(j-1)-p(j)]/3}

[olc0267]

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

Нет, не работает. Второй, допустим, угадал свой цвет, используя информацию от предыдущего. Но ему мало угадать свой цвет, ему надо ещё передать информацию для двух следующих. А если эта информация не совпадает с его собственным цветом? Он может только, сообщив свой цвет, передать информацию только для одного следующего. Для следующей тройки информации уже нет.

[olc0267]

Первый мудрец-камикадзе называет свой остаток p(1).
Второй мудрец, зная свой p(2), вычисляет свой код цвета по формуле:

А откуда он знает р(2)? Он может назвать р(2) для цветов Третьего и Четвёртого мудрецов. Но при этом он должен ещё назвать свой собственный, который ему подсказал Первый. А если ответ не сходится?
Говоря другими словами. Второй видит цвет Четвёртого. В зависимости от этого цвета, у Второго могут быть три варианта р(2). Но он не может выбирать варианты. Он должен назвать свой цвет без вариантов. И эту его информацию сможет использовать только один впереди стоящий мудрец.

[Марья-2]

Нет, не работает. Второй, допустим, угадал свой цвет, используя информацию от предыдущего. Но ему мало угадать свой цвет, ему надо ещё передать информацию для двух следующих. А если эта информация не совпадает с его собственным цветом? Он может только, сообщив свой цвет, передать информацию только для одного следующего. Для следующей тройки информации уже нет.

Вы почему-то "зациклились" на тройках
Собственный цвет каждого, который он вслух сообщает - это И ЕСТЬ информация для ВСЕХ следующих, с помощью которой они мысленно корректируют p(1) . Когда очередь доходит до n-го, разность между p (n) и этим самым мысленно скорректированным c учетом всех предыдущих p(1) равна его цвету.
Формулы, которые привел Alex9797, конечно, выглядят слегка устрашающе, просто попробуйте "на пальцах"
(Только что спросила знакомого инженера, знает ли он, что такое деление по модулю. Ответ был "а на фига мне это знать?" )

[olc0267]

Формулы, которые привел Alex9797, конечно, выглядят слегка устрашающе, просто попробуйте "на пальцах"

Эти формулы мне кажутся странными уже потому, что в них присутствуют числа 3 и 6, которые делятся на 3 без остатка, и на конечный ответ (остаток) не влияют. С таким же успехом я могу заменить их на 30 или 60. Там со скобками фигня какая-то. Закрывающей не хватает. Но на конечную сумму слагаемых скобки не повлияют.
Попробовал на пальцах. Не получается.
На всякий случай почитал статью
https://ru.wikipedia.org/wiki/%D0%94...BA%D0%BE%D0%BC
Может, что не так делаю? Продемонстрируйте на своих пальчиках.
ЗЫ. Кажется, начинаю понимать. Надо суммировать ВСЕ впереди стоящие числа? Но за одну минуту (60 сек.) сложить 100 чисел нереально. А кричать надо каждую минуту.

[shurik_ss]

Спасибо olc0267 (а также всем, кто сам догадался, но поздно прочитал тему и был не первым ответившим) и, особенно, Марья-2 за правильные ответы. Марья-2, Вы уже знали этот ответ или только что его придумали? Задача действительно непростая даже для детей с их гибким мышлением. Я говорил, что это для 7-го класса, но умолчал, что это олимпиадная задача. Так что примите поздравления.

Тут возникли сомнения по поводу 66 спасенных. Вот, к примеру: "Или ещё сложнее 100 в белом, 99 и 98 в синих, а остальные в красных колпаках."
Постараюсь объяснить. Мы разбиваем мудрецов на тройки. Кодирование происходит внутри каждой тройки, то есть, рассматриваем только троих, и нам совершенно без разницы, какие цвета у остальных 97: одинаковые или разные. Для процитированного примера, мудрецы будут стоять так (считаем с последнего, 100-го): БССККККККККККККККК.....К. Для первой тройки происходит следующее:
100 (смертник): передо мной два одинаковых С, кричу С (казнят)
99: первый в тройке крикнул С, передо мной тоже С, кричу тоже С (спасен)
98: первый и второй крикнули одинаково С, тоже кричу С (спасен)
97: (смертник): передо мной два одинаковых К, кричу К (застрелился сам)
96: первый в тройке крикнул К, передо мной тоже К, кричу К (спасен)
95: первый и второй крикнули одинаково К, тоже кричу К (спасен)
94,93,92 и остальные - аналогично.
Другой расклад: БСКККККККККККККККККККККККККККК...
100 (смертник): передо мной разные: С и К, кричу Б (застрелился сам)
99: первый в тройке крикнул Б, передо мной К (не Б), кричу дополнительный С (спасен)
98: первый и второй крикнули разные: Б и С, кричу дополнительный К (спасен)
97 и далее - как в первом примере.

Следующий ответ, который дали школьники, был несколько замудрёный, использовал троичную систему счисления и спасал около 80 человек, но давал сбой при определенной комбинации, отправлен на доработку, сам автор до ума алгоритм не довел (по нашим прикидкам, для устранения возможности сбоя надо пожертвовать еще 8..10 мудрецами).

Следующее красивое решение, спасающее 97 человек: первые трое сообщают остальным чётность колпаков каждого цвета (за исключением тех, что на смертниках). Например, договариваемся, что Б - четное, С - нечетное, 100-й отвечает за красный, 99-й - за С, 98-й - за Б. Остальные, подсчитав колпаки перед собой и отняв те, что выкрикнули до них (кроме первых трех смертников), определяют по четности/нечетности, какого цвета не хватает (то есть, он у них на голове), и называют его (похвастаюсь: этот вариант я сразу придумал. А вот до последнего - да, доходил долго). Решение легко доработать: мы знаем, сколько всего колпаков, и если мы знаем, четно или нечетно количество, например, красных и синих, то легко вычисляем четность белых. Спасаем еще одного мудреца (итого, 98 ).

Ну и самое сложное и самое оптимальное решение - то, что описано Марья-2

[olc0267]

Ну и самое сложное и самое оптимальное решение - то, что описано Марья-2

Марья-2 ссылается на формулы Alex9797. Но они не работают. Затык происходит уже на четвёртом мудреце, как я и сказал.
Смотрим эту формулу.

N(j) = остаток{[(6+p(j-2)-N(j-1)-p(j)]/3}

В этой формуле неизвестное слагаемое р(j-2). Мудрец знает только свой остаток p(j), цвет предыдущего мудреца N(j-1) но не знает остаток p(j-2), т.к. его никто не называл - все называли только свой цвет. Т.е. невозможно одним словом сообщить свой цвет и одновременно передать информацию дальше.
Поэтому, единственно верным решением остаётся считать по чётности. Но для этого самым первым нужно успеть просчитать всю цепочку из ста колпаков за одну минуту. У моих извилин тактовой частоты бы не хватило. Последующим проще - они могут просчитать впереди стоящих заранее, пока до них идёт очередь.

[IlyaTIP]

Я тут, как всегда, поздно посмотрел тему, но свои 5 копеек тоже хочу вставить. Был несколько удивлен, что детская задачка про шляпы (рекомендована для дополнительных занятий младшим школьникам) вызвала такое бурное обсуждение. Подобные задачи у нас в классе (наверное, класс 4), решались особо не задумываясь (вариаций таких задач много, принцип решения - общий для всех). А попробуйте решить задачку посложнее, она для средних и старших школьников (от 7-го класса, ну или с нынешней 11-леткой - от 8-го):

Было при дворе короля 100 мудрецов. Засомневался король в их интеллектуальных способностях, и решил казнить самых бестолковых. Процесс обставил так: выстроил их в колонну по одному и надел каждому колпак белого, синего или красного цветов (соотношение количества цветов неизвестно). Все мудрецы видят цвета всех колпаков впереди стоящих мудрецов, а цвет своего и всех стоящих сзади не видят. Раз в минуту один из мудрецов (любой) должен выкрикнуть один из трех цветов (каждый мудрец выкрикивает цвет один раз).
После окончания этого процесса (когда все 100 выкрикнули) король казнит каждого мудреца, выкрикнувшего цвет, отличный от цвета его колпака.
Накануне такой "переаттестации" все сто мудрецов договорились и придумали, как минимизировать число казненных. Скольким из них гарантированно удастся избежать казни?

Сразу скажу, не надо придумывать "детские" отмазки про разную интонацию голоса, задержку выкрика, секретные знаки и пр. Задача чисто логическая. И все вы это прекрасно понимаете.
И, кстати, всем гарантированно спастись не удастся. Вероятностные варианты не в счет. Считаем, что если мудрец не был уверен в своем цвете, и вынужден был тупо угадывать, то он застрелится после испытания сам. От горечи и обиды.

если мудрецы договорились правильно и случайное попадание исключим по моему мнению живыми останутся 49 мудрецов по тому что начиная с последнего застрелятся через одного и первый тоже итого остаток 49

[John_p]

если мудрецы договорились правильно и случайное попадание исключим по моему мнению живыми останутся 49 мудрецов по тому что начиная с последнего застрелятся через одного и первый тоже итого остаток 49

Стратегии 50 и 66 уже всяко разжевали и пояснили, нет, опять особое мнение...