Comments 24
Надо кричать цвет колпака коллеги и тот потом просто повторит.
Ответ на пятую задачу не понял. Можно на каком-нибудь примере?
Альтернативное решение задачи 0, работающее даже если оба мудреца дают ответ одновременно: Один мудрец называет тот цвет, который видит, а другой — альтернативный цвет. В случае, если их цвета совпадают — отгадает первый, в случае, если цвета разные — второй.
Решение задачи 2 совершенно не годится. Чтобы выбрать табличку противоположного цвета, нужно знать какую табличку выбрал предшественник. Даже если всего лишь пикосекунда прошла, это не одновременно
Это неудачная формулировка. Я смотрю на товарища-мудреца, и вижу на нем белый колпак. Поднимаю белую табличку. Мой товарищ смотрит на меня и видит (допустим) белый колпак — поднимает черную (противоположную) табличку. То есть противоположность — не моей табличке, а моему колпаку. Поэтому мы это делаем одновременно.
Из так и не опубликованного на "Играх разума":
2018 мегамозгов выстроили в колонну и надели на них колпаки с номерами от 1 до 2019 вперемешку, один колпак спрятав и мегамозгам не показав. Далее мегамозги, начиная с того, кто видит всех, кроме себя (т.е. кто стоит позади всех), называют число, предположительно написанное у него на колпаке, при этом нельзя называть уже названное кем-то ранее число. Какое наибольшее число мегамозгов может гарантированно угадать номер на своем колпаке?
Примечания: 1) Повторных номеров нет. 2) Все слышат ответ каждого, но те, кто не видит ответившего, не знают, угадал он или нет - результаты станут известны по окончании.
Я недавно присылал автору ответ, где ошибаются максимум 6 челов, он сказал, что уже подзабыл эту задачу, но "кажется, можно меньше".
Моё решение: 1-й угадывает с 50% вероятностью, остальные - 100%
Решение
Пусть спрятанный колпак находится в 0 позиции, тогда каждый мегамозг видит все колпаки в позициях больше его собственной.
При этом номера колпаков образуют некоторую перестановку.
Первый мегамозг не видит 2 колпака, но предполагает, что перестановка - четная, и называет номер колпака со своей позиции.
Второй мегамозг не видит 3 колпака, но слышал ответ предыдущего, поэтому у него есть только два варианта. Но у них разная четность, поэтому он выберет тот, который соответствует четной перестановке.
Оба отстутствующих колпока могут давать перестановки одинаковой четности.
Да нет, решение правильное. Каждый участник по факту выбирает один вариант перестановки из двух:
***А***В
***В***А
Где звёздочки - то что он видит или слышал. Легко заметить, что между этими вариантами нечётное количество инверсий..
Да, действительно. Приношу извинения Deosis. Классная идея.
Как только стало понятно, что каждый участник выбирает один вариант из двух, задача сводится к более простой с колпаками белого и черного цвета.
Я придумал, как все, кроме 7 отгадывают.
Первые k=7 будут передавать информацию об оставшихся n-k (n=2018). Оставшиеся, обладая этой информацией, все отгадывают. Первые k видят оставшиеся колпаки и знают, что там отсутствует k+1 число. Они называют какую-то перестановку k минимальных из них так, чтобы ее порядковый номер был равен последнему из k+1 отстутствующих чисел. Все оставшиеся, услышав эту перестановку из k чисел, вычисляют ее номер и находят k+1-ое число. Так они все сразу знают все k+1 отсутствующее число. А дальше, первый из оставшихся видит n-k-1 колпаков и знает k+1 отсутствующее число. Отсается только только одно из n+1 чисел, его и называет. Следующий видит n-k-2 колпаков, знает k+1 отстутствующее число и слашал 1 предыдущий колпак. Остается ровно один вариант. И так далее.
Это работет, если k! >= n+1. 7! = 5040 >= 2019.
Похоже, это можно как-то сократить до 6-ти ошибающихся в начале. Ведь из отсутствующих k+1 числа можно выбрать k и их перестановку, чтобы закодировать одно отсутствующее. Я предлагал выше всегда кодировать максимальное число, но есть же выбор, какое число кодировать. Но схему кодирования я пока не придумал.
Можно же называть только число от 1 до 2019? Иначе первый может назвать очень большое число, в котором закодированы все колпаки дальше.
Из условия задачи 0 не вытекает, что порядок опроса мудрецов заранее известен. Поэтому угадать цвет наверняка может только последний мудрец.
Не очень понял задачу 2. Разве нельзя поступить по аналогии с 1 задачей только вместо слов показать табличку нужного цвета в зависимости от четности количества черных/белых шляп у остальных. Дальше все как в первой задаче только вместо "первого" (в качестве того на чью табличку обращать внимание) каждый из мудрецов для себя выберет любого. И тогда каждый сможет ответить правильно. Стало быть, и в оставшихся задачах будет такой же ответ.
В задаче 1 у мудреца есть информация о цветах колпаков остальных и о том какую табличку поднял первый.
В задаче 2 информации о табличке, которую поднял первый нет - только цвета колпаков. Поэтому решение несколько сложнее.
Изначально я слишком сумбурно описал предлагаемую стратегию. Исправляюсь. Далее идет аккуратное описание стратегии.
Назовем мудреца A особым по отношению к мудрецу B, если мудрец B может гарантированно верно назвать цвет своей шляпы, основываясь лишь на цветах шляп остальных мудрецов и на названном мудрецом A цвете, действуя по стратегии, описанной в решении к первой задаче.
В задаче 1 мудрец под номером 1 является особым по отношению ко всем остальным и не существует особого мудреца по отношению к первому. То есть все мудрецы кроме особого знали какой цвет назвал особый мудрец и знали цвета шляп всех остальных мудрецов. Но особый мудрец мог и не называть никакой цвет, а просто поднять табличку с нужным цветом, если таблички всех цветов имелись в его распоряжении.
Чтобы перейти к задаче 2 надо поправить определение выше, заменив слово "названном" на что-то более подходящее. Я не смог подобрать удачное слово, которое бы одновременно означает как "названном", так и "показанном", поэтому пусть будет "названном или показанном".
Переходим к задаче 2. С учетом вышесказанного можно придумать такую стратегию: случайным образом выбирается мудрец, который будет особым по отношению ко всем остальным и на цвет именно его карточки все остальные будут обращать внимание. В таком случае все мудрецы кроме одного гарантированно ответят правильно.
Однако стратегию можно улучшить. Для этого можно заметить, что любой из мудрецов является особым по отношению ко всем остальным. То есть каждый из мудрецов может для себя выбрать какого-нибудь мудреца и назвать правильно цвет своей шляпы. Таким образом приходим к стратегии, когда ВСЕ мудрецы гарантированно верно назовут цвет своей шляпы.
Эту стратегию можно обобщить и для последующих задач.
В задаче 2 нет как такового первого, второго и т.д. Все мудрецы находятся в равных условиях. Получается, что если у мудреца нету информации о табличке, которую поднял первый (кто бы этим "первым" ни оказался), то, с учетом равных условий, у мудреца нету информации ни об одно из табличек, поднятых его коллегами. Получается, что таблички бесполезны и вовсе не нужны. А без табличек гарантированно верно назвать свой цвет никто не может.
В решении к задаче 2 Вы пишете
Оказывается, два мудреца могут так хитро договориться, чтобы гарантированно один из них угадал свой цвет. Один мудрец поднимает табличку того же цвета, что и цвет колпака на другом мудреце, а тот, наоборот, поднимает табличку противоположного цвета.
Получается, что цвет таблички (здесь и далее под цветом таблички подразумеваю цвет поднятой вверх таблички) в руках мудреца B совпадает с цветом шляпы мудреца A. При этом мудрец A видит табличку мудреца B. То есть мудрец A знает цвет своей шляпы. Аналогично если поменять A и B местами.
Но затем Вы пишете
Легко видеть, что ровно один из них "угадает" свой цвет: первый, если король надел одинаковые колпаки, и второй - в противном случае.
Поясните, пожалуйста, что Вы имели в виду?
В задаче 2 мудрецы поднимают таблички одновременно. Можно заменить - пишут цвет на бумаге и кладут в конверт. При этом мудрецы не знаю что выбрал коллега. В случае двух мудрецов они договорились так: первый пишет цвет колпака коллеги, а второй пишет противоположный цвет колпака коллеги. Таким образом, у нас возможны 4 варианта:
Колпаки: белый, белый. Ответы: белый, черный.
Колпаки: белый, черный. Ответы: черный, черный.
Колпаки: черный, белый. Ответы: белый, белый.
Колпаки: черный, черный. Ответы: черный, белый.
Как видите, один мудрец всегда угадывает (но мы не можем сказать какой из них)
Формулировка задачи оказалась неоднозначной. Я подумал, что таблички даны не для "озвучивания" предположения о цвете своей шляпы, а для коммуникации между мудрецами. И что ответ надо по прежнему выкрикивать. Перечитав несколько раз формулировку и предложенное автором решение я понял, что неверно интерпретировал условие.
Знатно я, однако, опростоволосился =)
Переаттестация мудрецов