Чита, Нита и Дракон

[slavav]

Нечётного числителя в вероятности оптимальной стратегии быть не должно.

[wrest]

slavav в сообщении #1376186 писал(а):

Нечётного числителя в вероятности оптимальной стратегии быть не должно.

Но ведь для четырех бросков $\frac{178}{256}=\frac{89}{128}$
Хорошо, а какая вероятность для 5 бросков? Выбор-то небольшой: бОльшие чем $\frac{178}{256}=\frac{712}{1024}$ это: $\frac{713}{1024};\frac{714}{1024};\frac{715}{1024};\frac{716}{1024}$ Следующее уже больше $0,7$

[mihaild]

wrest в сообщении #1376189 писал(а):

Но ведь для четырех бросков $\frac{178}{256}=\frac{89}{128}$

Имелось в виду если в знаменателе $2^{2n}$, где $n$ - число бросков.

slavav в сообщении #1376186 писал(а):

Нечётного числителя в вероятности оптимальной стратегии быть не должно

А почему? Для случая одинаковых стратегий очевидно, для не одинаковых - не понимаю, почему так должно быть.

[slavav]

Я говорил про симметричную стратегию (то что вы называете одинаковыми стратегиями).

-- 15.02.2019, 14:05 --

Пользователь achikin из ODS:

Цитата:

Да, походу 0.7 пробить не просто (если вообще возможно). Искал генетическими алгоритмами симметричные стратегии для фиксированных последовательностей длины 1-8

Нашел стратегии со следующими вероятностями:
# 1: 0.5
# 2: 0.625
# 3: 0.6875
# 4: 0.6953125
# 5: 0.69921875
# 6: 0.69970703125
# 7: 0.699951171875
# 8: 0.699981689453125

Искать несимметричные стратегии смысла не вижу.

[wrest]

slavav в сообщении #1376196 писал(а):

# 5: 0.69921875

Ok, т.е. для 5 бросков выходит $\frac{716}{1024}$
Далее
6 бросков, $\frac{2866}{4096}$
7 бросков, $\frac{11468}{16384}$
8 бросков, $\frac{45874}{65536}$

-- 15.02.2019, 14:40 --

Немножко нумерологии.
Числители в двоичном формате $(2;10;44;178...)$
10
1010
101100
10110010
1011001100
101100110010
10110011001100
1011001100110010
Ну и $0,7_{10}=0,10(1100)_2=0,B(3)_{16}$

Так что стремление к $0,7$ просматривается довольно ясно, как и формулы для вероятности при четном\нечетном количестве бросков.

[waxtep]

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

$$\begin{tabular}{|c|c|c|c|c|c|c|} \hline case&001&010&011&100&101&110\\ \hline 1st&2&1&2&3&3&1\\ \hline 2nd&1&3&3&2&1&2\\ \hline \end{tabular}$$

То есть, если, например, у Ниты выпало $\texttt{РОР}=010$, то она просит показать первый бросок Читы, а если у Читы выпало столько же, она просит показать третий бросок Ниты и т.д. При этом, совершенно не важно, что просить, если выпало $000$ или $111$, повезет ровно в половине случаев; поэтому эти исходы не показаны. Для этой стратегии принцессы не спасаются строго на анти-диагонали, т.е. когда у одной выпало $010$, а у другой $101$ и т.п. Если бы это так же работало для любого числа бросков $n$ у каждой, то принцессы не спасаются только в $3\cdot2^n-4$ случаях из $2^{2n}$ возможных; что в пределе $n\rightarrow\infty$ дает единичную вероятность спасения. Однако, видимо, численные эксперименты этого не подтверждают....

-- 16.02.2019, 01:07 --

Интересно отметить, что стратегии обеих сторон подходят под правило "не совпадать с $(3,2,1,1,2,3)$ ни в одной позиции"

[slavav]

Шесть найденных полным перебором стратегий. Я нумерую позиции с нуля. Ваши две стратегии в списке есть.

0 2 0 1 1 2
0 2 2 1 0 1
1 0 0 2 1 2
1 0 1 2 2 0
2 1 1 0 2 0
2 1 2 0 0 1

[Sender]

waxtep в сообщении #1376357 писал(а):

Интересно отметить, что стратегии обеих сторон подходят под правило "не совпадать с $(3,2,1,1,2,3)$ ни в одной позиции"

А если выбрать обе стратегии $(3,2,1,1,2,3)$, получим ровно половину благоприятных исходов для каждого из раскладов, т.е. вероятность спасения $\frac{1}{2}.$

slavav в сообщении #1376364 писал(а):

Шесть найденных полным перебором стратегий.

Можно заметить, что половина из них представляют собой зеркальные отражения остальных.

-- Сб фев 16, 2019 02:29:51 --

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

[waxtep]

Sender в сообщении #1376369 писал(а):

А если выбрать обе стратегии $(3,2,1,1,2,3)$, получим ровно половину благоприятных исходов для каждого из раскладов, т.е. вероятность спасения $\frac{1}{2}.$

Точно, я ведь так свой вариант и вымучал: если одна сторона выбирает крайне неудачную стратегию $(3,2,1,1,2,3)$, то второй ее никакими усилиями на достойные шансы спасения не вытянуть. Значит, искать надо "в противоположном углу". Но вот обобщается ли это на случай $n>3$ и как, если да? С учетом того, что для $n=2$, $(1,2)$ (или $(2,1)$) как раз является оптимальной стратегией для обеих сторон

[wrest]

У меня такой вопрос. Я не понял, является ли условие предварительного сговора принцесс существенным?

[Sender]

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

[wrest]

Sender
Вопрос в другом: смогут ли принцессы поднять вероятность выше $1/2$ если принцессы умные и разумные, но поговорить перед испытанием им не дали.

[slavav]

Sender в сообщении #1376369 писал(а):

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

Вы правы. Рассмотрим симметричную стратегию $s$. Она отображает последовательность бит в номер бита. Номер бита закодируем в виде последовательности бит. Все биты нулевые, один бит в указанной позиции единица: $0 \to (1, 0, 0), 1 \to (0, 1, 0), 2 \to (0, 0, 1)$. Далее я буду считать что $s: \left\lbrace0, 1\right\rbrace^3 \to \left\lbrace0, 1\right\rbrace^3$. Рассмотрим любую перестановку $p \in S^3$. Тогда верно что число побед для $s$ равно числу побед для $p^{-1} \circ s \circ p$.
Все шесть ($3!$) оптимальных стратегий для трёх бит получаются друг из друга такими преобразованиями.

Для четырёх бит число оптимальных симметричных стратегий равно $240$. Десять групп по $24 (= 4!)$.

-- 16.02.2019, 12:41 --

wrest в сообщении #1376401 писал(а):

Sender
Вопрос в другом: смогут ли принцессы поднять вероятность выше $1/2$ если принцессы умные и разумные, но поговорить перед испытанием им не дали.

Уже для трёх бит есть шесть разных стратегий и не все пары дают оптимальный результат. Принцессам надо договорится перед испытанием.

[wrest]

slavav в сообщении #1376409 писал(а):

Уже для трёх бит есть шесть разных стратегий и не все пары дают оптимальный результат. Принцессам надо договорится перед испытанием.

Это ясно, но можно ли все хоть как-то же повысить вероятность не сговариваясь?

[waxtep]

slavav в сообщении #1376409 писал(а):

Уже для трёх бит есть шесть разных стратегий и не все пары дают оптимальный результат

Там же получается три пары стратегий, если не ошибаюсь, т.е., скажем, Нита может выбрать любую из шести, но, тогда Чита должна выбрать вторую стратегию четко из этой же пары. При этом, одна из пар зеркальная, а две другие - несимметричные. Без сговора, правда, все равно ничего у них не получится