маньяк и шапочки

[photon]

IT-Маньяк предложил своим 10-ти жертвам вариант, по которому некоторые
из них могут сохранить свою жизнь. Он рассказал им условия и дал время,
чтобы продумать по какому принципу они будут угадывать цвета своих
головных уборов, которые впоследствии будут на них одеты.

Условия:
- Жертвы будут выстроены в ряд друг за другом - обычная очередь (последний видит девятерых перед собой; предпоследний видит восьмерых перед собой и т.д. до первого, который не видит никого);

- Каждому на голову маньяк повязывает по бандане (желтого или зеленого цвета в произвольном порядке и количестве, т.е. всего может быть 5 желтых/5 зеленых бандан или 10 желтых/0 зеленых и т.д.), причем цвет банданы на своей голове жертвы не видят.

- Подойдя к последней жертве (10-я в очереди) маньяк спрашивает цвет его банданы и убивает жертву в том случае, если она не угадывает. В противном случае оставляет в живых. Далее вопрос задается 9-му и т.д.

- Жертва может произнести только одно слово ("желтый", "зеленый", без вариантов интонаций и жестов), причем все участники "розыгрыша" слышат что произносят претенденты и что с ним происходит.

Нужно придумать алгоритм, чтоб спасти 9 из 10 жертв

[ИСН]

Боян (хотя здесь вроде не было). Кодирование по чётности - и все, кроме заднего, гарантированно спасаются.

[Александр Воронцов]

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

Еще есть вариация -- "что происходит, если кто-то в цепочке ошибается (то есть нарушает разработанную стратегию)?"

[worm2]

Александр Воронцов писал(а):

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

Если набор заранее известен (например, по 3 шапочки красного и снинего цветов, по 2 зелёного и жёлтого), то вообще все могут спастись. Это другая задача.

[Профессор Снэйп]

worm2 писал(а):

Александр Воронцов писал(а):

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

Если набор заранее известен (например, по 3 шапочки красного и снинего цветов, по 2 зелёного и жёлтого), то вообще все могут спастись. Это другая задача.

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

[ИСН]

Естественно, только набор цветов. (Если известен набор цветов с количествами, это не другая задача - это вообще не задача.)

[photon]

Александр Воронцов писал(а):

Еще есть вариация -- "что происходит, если кто-то в цепочке ошибается (то есть нарушает разработанную стратегию)?"

А результат-то (убит/не убит) известен. Если ошибка одиночная и не у последнего, то количество жертв увеличится на того, кто ошибся, если у последнего, то по его вине помрет предпоследний...

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

[Sikle]

Что значит кодирование по четности?

[photon]

Sikle писал(а):

Что значит кодирование по четности?

Если сопоставить цветам 0 и 1, то отвечающий первым выбирает ответ в зависимости от четности суммы.

[Архипов]

Sikle писал(а):

Что значит кодирование по четности?

Как я понял, первый видит перед собой 9 шапок. Возможных цветов всего два. Сумма 9 может быть только из одного четного и одного нечетного числа. Вероятность угадать цвет шапки для первого равна 1/2. А вдруг все 10 шапок зеленого цвета? Лучше тогда условиться: первый называет цвет нечетного количества шапок одного цвета (в надежде, что и на его голове зеленая). Все 9 человек приняли эту информацию (зеленые). Второй считает зеленые шапки (если их четное количество, то на его голове - нечетная зеленая шапка). Он с неизбежностью называет: "зеленая". Третий (и остальные) теперь знают, что зеленых шапок осталось четное количество. Если же кто-то называет "желтая", то каждый оставшийся будет знать: зеленых осталось прежнее (нечетное) количество. И т.д.

[photon]

Интересно (может быть кому-то) было бы определить поведение всех жертв (только, пожалуй, стоит ограничиться меньшим их количеством - скажем, 5-6 человек), если они знают о возможной ошибке тех, кто говорил до них и знают вероятности ошибок всех остальных участников.

Пусть вероятности ошибок (под вероятностью ошибки понимаем вероятность выбора не того цвета, который обеспечивает на данном этапе максимальную выживаемость в группе) будут $p_1, p_2,... p_N$.

Например, для $N-2$-ой жертвы ситуация $(N-1)$-й и $N$-й оба ошиблись и $(N-1)$-й и $N$-й оба сказали правильно выглядит одинаково: $(N-1)$-й остался жив. Тогда для правильного принятия решения он должен сравнить вероятности одновременной ошибки и одновременного правильного выбора и по результату сравнения делать свой выбор, допустив при этом с определенной вероятностью ошибку.

[worm2]

ИСН писал(а):

Естественно, только набор цветов.

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

[ewert]

worm2 писал(а):

ИСН писал(а):

Естественно, только набор цветов.

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

На самом деле 3 бита: 2 бита -- тот цвет, который он называет, а 3-й бит возвращает секир-башка.

[worm2]

Ой, и точно. Стормозил Два бита точно есть.

ewert писал(а):

3-й бит возвращает секир-башка

А этот 3-й бит, вроде бы, не несёт полезной информации. Хотя она и не нужна...

[Александр Воронцов]

Если цветов не два, а больше, то каждый ответ даёт не один бит информации, а больше.