Вероятностные мудрецы

[molch64]

Вспомнилась задача про мудрецов и колпаки, и вроде такой ещё не было (поиск результатов не дал).
Если была и я не нашел - киньте ссылкой и тапочком да закройте сию тему нафиг.

А теперь, задачка
На трех мудрецов надели случайным образом по колпаку белого или черного цвета.
Тут стоит заметить, что эти колпаки заранее случайно достали из огромного мешка с большим, но одинаковым количеством колпаков разных цветов
(короче говоря, на каждом мудреце белый колпак с вероятностью 50%, и эти вероятности друг от друга не зависят).
Мудрецов показывают друг другу и, по традиции, мудрец видит цвета всех колпаков, кроме своего.
При всем этом действии мудрецам запрещено обмениваться между собой любой информацией.

Увидев цвета колпаков остальных мудрецов, каждый одновременно пишет записку с одним из двух следующих содержаний:
а) На мне ... колпак.
б) Пас.
То есть, разрешается либо попытаться угадать свой цвет, либо пасануть.

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

Задача - выиграть с наибольшей вероятностью.

Для решивших задачу - усложненная версия. Мудрецов теперь 7. Вероятность, с которой нужно выиграть назову после решения первой задачи.

P.S> Да, если варианта "пас" нет и мудрецы обязаны угадывать свой цвет, то они могут выиграть с вероятностью 50%.
Для этого им необходимо заранее договориться, что количество черных колпаков в сумме будет, например, четно (это 50/50) и всем говорить такой цвет колпака, чтобы черных по сумме было четно.
Так что принимаются ответы только с вероятностью, строго большей 50%.

[Юляша]

Обеспечу вероятность 75%

При этом вероятность "правильного угадывания" остается но уровне 50%, а вот вероятность "выигрыша" - она выше.

[molch64]

75% - это правильный ответ!
Теперь, нужно увеличить это число, если мудрецов - 7

[Юляша]

Формальное применение того же принципа дает вероятность 21/32 (примерно 65,6%).
Но есть возможности для вариаций.

[molch64]

А можно в личку или мелким шрифтом, как 21/32 достигнута? Жутко интересно
P.s. Но в любом случае ответ от числа мудрецов уменьшаться не должен. Ибо они заранее могут договориться и выделить подмножество мудрецов, которые спасуют и подмножество тех, кто будет играть , не смотря на цвета шапок спасовавших мудрецов

[Dendr]

Можно взять и свести все к таблице.
То есть, формализовать задачу: мудрецам (пронумеруем их, скажем, по старшинству) пишут на лбу по биту из двоичной записи некого числа (в случае троих - от 0 до 7), потом выстраивают друг напротив друга. Задание - либо назвать "свой" бит, либо сказать "не знаю". Причем "называют" не в открытый эфир, а пишут на карточке и передают некому демиургу тайком. Общая задача - нужно, чтобы хотя бы один участник назвал "свой" бит, причем если он ошибется, то засчитывается общий проигрыш.

Понятно, что мудрецы отталкиваются от информации, которую видят сами. Поэтому вариантов ответа - 4: мудрец видит 00, 01, 10 или 11 (соответственно, ответы x, y, u и z). Тактика у каждого может быть своя, поэтому у каждой буквы появится цифра (от 1 до 3) - итого 12 неизвестных.
Например - на 00 он пишет "0", на 01 - "не знаю" и т.д.
А дальше, начиная с таблицы и работы над ней - напишу "скрытым" текстом

...

-->Итого получаем таблицу ответов каждого из мудрецов в каждом из случаев задуманного демиургом числа:
0 (000) - x1, x2, x3
1 (001) - y1, y2, x3
2 (010) - u1, x2, y3
3 (011) - z1, y2, y3
4 (100) - x1, u2, u3
5 (101) - y1, z2, u3
6 (110) - u1, u2, z3
7 (111) - z1, z2, z3.
Видно, что попарно числа нигде не повторяются. (это важно!)

Понятно, что вероятность угадать везде равна 50%, именно для этого и придуманы пасы.

Пусть устроим x1=1. (так удобнее) Тогда в случае "4" победа будет тогда и только тогда, когда u2 и u3 одновременно не равны 1 - либо нули, либо "пасы".
А вот на "0" - сразу проигрыш, как бы ни ответили второй и третий. Давайте расставим так, чтобы "0" в любом случае проигрывал (!) поэтому x2=1, x3=1.

Перепишем нашу таблицу с известными данными (видно, что еще два варианта сразу стали "почти выигрышными")^
0 (000) - 1, 1, 1
1 (001) - y1, y2, 1
2 (010) - u1, 1, y3
3 (011) - z1, y2, y3
4 (100) - 1, u2, u3
5 (101) - y1, z2, u3
6 (110) - u1, u2, z3
7 (111) - z1, z2, z3.

Видно теперь, что u2, u3 и еще 4 ответа можно свободно поставить, как пасы: мудрецы уже победили , а портить еще варианты нет смысла, поэтому таблица приходит к виду:
0 (000) - 1, 1, 1
1 (001) - p, p, 1
2 (010) - p, 1, p
3 (011) - z1, p, p
4 (100) - 1, p, p
5 (101) - p, z2, p
6 (110) - p, p, z3
7 (111) - z1, z2, z3.

Теперь очевидно, что надо взять z1=0, z2=0, z3=0 - тогда "7" проиграет, зато 3 других пока не определившихся варианта - выиграют, это хорошо видно из окончательной таблицы.
0 (000) - 1, 1, 1 ***
1 (001) - p, p, 1
2 (010) - p, 1, p
3 (011) - 0, p, p
4 (100) - 1, p, p
5 (101) - p, 0, p
6 (110) - p, p, 0
7 (111) - 0, 0, 0 ***.

В 6 из 8 случаев мудрецы побеждают! 75% - совсем неплохо. И тактика (возвращаясь к колпакам) такая: "Видишь разные цвета - пасуй! Видишь одинаковые - пиши противоположный!"

Мне пока видится, что это же самое можно развить и до большего числа мудрецов. А то и... цветов колпака. В числах выражать - это подсчитать надо будет.<--

[Шшок]

Тактика должна быть такой:

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

Если мудрецов 7 (или миллион, не важно), то все, кроме трех, должны пасовать, а оставшиеся три должны действовать по той же самой схеме. Получаются те же 75%.

[Юляша]

Так как реально вероятность угадать или не угадать для конкретного мудреца - всегда 50%, поднять вероятность можно только методом "усиленного фэйла". То есть, если мудрецы ошибаются, то ошибаются все сразу, а если угадывают, то один угадывает, а остальные пасуют. Вероятность 75% при трех мудрецах достигается именно таким способом.

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

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

Из такой логики понятно, что теоретический предел для K мудрецов равен K/(K+1) (=87,5% для семи мудрецов), а вот достижим ли он хотя бы для каких-то K - это уже вопрос.

[Dendr]

Из такой логики понятно, что теоретический предел для K мудрецов равен K/(K+1) (=87,5% для семи мудрецов), а вот достижим ли он хотя бы для каких-то K - это уже вопрос.

По-моему, это верно, если K+1 - степень двойки.
Сейчас пробую руками (в Excel точнее) для 5 мудрецов перебрать варианты.

[Юляша]

По-моему, это верно, если K+1 - степень двойки.

Да!

Теорикрафт у меня готов.

Пусть имеются упорядоченные последовательности из K двоичных цифр, где K=2**L-1.

Назовем расстоянием между двумя последовательностями количество несовпадающих цифр, стоящих на одних и тех местах. Например, расстояние между 1001011 и 0101111 равно 3.

Предположим, что существует набор последовательностей M, состоящий из 2**(K-L) последовательностей, и удовлетворяющий следующему условию.

Для произвольной последовательности A из К цифр существует такая последовательность B, принадлежащая M, что расстояние между A и B не превосходит 1.

Нетрудно убедиться, что последовательность B в таком случае единственная.

Назовем последовательности, входящие в множество M, фэйлопоследовательностями.

В этом случае мудрецы могут действовать следующим образом.

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

Если множество М существует, то достигается теоретический передел, равный K/(K+1). Мудрецы проигрывают, если они нарвались на фэйлопоследовательность, и выигрывают во всех остальных случаях.

Чтобы довести решение до конца, надо построить реальное множество M (включающее 16 последовательностей, расстояние между любыми двумя из которых - три или больше).

[Юляша]

Множество M существует!
См., например http://ru.wikipedia.org/wiki/%D0%9A%D0% ... 0%B3%D0%B0

[molch64]

Чтобы довести решение до конца, надо построить реальное множество M (включающее 16 последовательностей, расстояние между любыми двумя из которых - три или больше).

Браво! Быстро раздолбали!
Ключевое слово задачи - "фэйлопоследовательности", они же - коды Хемминга

UPD: Вот черт, ту же самую ссылку дал в то же самое время

[molch64]

Кстати, приведу пример решения для 7 мудрецов ручками, пришедшее мне первым.
Оно улучшает вероятность в 3/4, но не достигает вероятности в 7/8.
Тем не менее, никаких кодов Хемминга оно не использует.

Разобьем 7 мудрецов на тройку и четверку.
4 мудреца играют в следующую игру: "если я вижу на трех соседях колпаки одинакового цвета, я говорю другой цвет, иначе - пасую".
Тогда, в случает 4х мудрецов c одинаковыми колпаками у нас провал с вероятностью 2/16.
В случае 3/1 - победа с вероятностью 8/16.
И, наконец, с вероятностью 6/16 будет колпаки будут 2/2 и все четверо спасуют.
3 мудреца знают, как сыграли первые четверо и будут играть сами только в случае, если на первых четырех колпаки 2/2.
Иначе - пасы.
Тогда общая вероятность победы - 8/16 + 6/16 * 75% = 25/32.

Как и обещал, число, большее 3/4, но меньшее 7/8.

[Dendr]

Вот... добил вариант из 5 мудрецов. Результат - те же 75%, больше - никак. То есть 8 "обязательных" ошибок из 32 вариантов.
В моем варианте это -
варианты типа А: "Белые колпаки на первых двух мудрецах И нечетное количество белых на остальных трех, независимо от расположения" ИЛИ
варианты типа Б: негатив к А.
То есть каждый мудрец смотрит на остальных, потом мысленно примеряет на себя белый колпак - если получившаяся комбинация входит в тип А или Б, то он пишет записку "У меня белый". Если же нет - повторяет все то же, но с умозрительным черным колпаком. Если и тут ошибки не получается, то он пасует.

Для семи же - уже будет вероятность общей победы 87.5%. Навскидку:
Тип А - у первых 3 белые колпаки, у других 4 - четное количество белых (0, 2 или 4). (БББББББ, БББЧЧЧЧ, БББ+(Б,Б,Ч,Ч) вразброс)
Тип Б - негатив к А. Итого выйдет 16 ошибок из 128 вариантов.

Формула для вероятности проигрыша (при наилучшей стратегии), получается, должна быть такая:
P(N)=2^(n(N)-N),
где n(N)=ceil(log2(2^N/(N+1))),
^ - символ возведения в степень, ceil - округление в большую сторону.

P.S. Пытаюсь представить теперь, что если добавить серые колпаки...

[Dendr]

Вот график написанной мной выше функции. (на наклонные участки не смотрите - это соединительные линии между точками с целочисленной абсциссой)