Здравствуйте, nikholas, Вы писали:

N>Злобный Дракон поймал двух принцесс, Читу и Ниту, и посадил их в разные башни
<…>
N>То есть Чита должна назвать нечётный номер, а Нита — чётный.

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

Сдаётся мне, что хитрость сидит в том, что последовательность бесконечная. Скорее всего это означает, что можно придумать такую стратегию, что вся ситуация станет внутренне противоречивой. Это будет следствием того, что мы будет использовать операции вроде "просмотреть всю последовательность и что-то посчитать", так как эта операция, скорее всего внутренне противоречива или, наоборот, неполна. Назовём стратегии такого вида Вид1.

С другой стороны, можно представить себе стратегию, в которой принцесса использует только операции вида "просматриваем последовательность, пока что-то не найдём".
Ок. Мы попадаем в ситуацию условной вероятности. Например, Нита ищет такую последовательность из 1000 бросков, в которой решек (или орлов) на 100 больше.
Это эквивалентно тому, что дракон бросает свою монетку 2000 раз и предъявляет последовательность принцессам, только если подпоследовательность Ниты удовлетворяет такому условию. Но даже тут Нита ничего не будет знать про результаты бросков Читы же. Назовём стратегии такого вида Вид2

Не совсем понятно, есть ли ещё какие-то виды стратегий для работы с бесконечной последовательностью.

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

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

Предположим, для начала, что стратегии у них одинаковые.
тогда стратегия -- это отображение пар результатов (0,0), (0,1) и т. д, на номер

Получаем условные вероятности.

Пусть при каких-то конкретных ответах принцесс, a1 и а2 вероятность получить в соответствующих позициях решку(0) — p1 и p2
тогда условная вероятность удачи -- это p1*p2 + (1-p1)*(1-p2) = 1 -p1 — p2 + 2 p1 p2, а неудачи -- p1(1-p2)+(1-p1)p2 = p1 + p2 — 2 p1 p2

Пусть, например, стратегия такая, что всегда 0, а если (1,0), то 1
тогда если принцесса назвала 1, то с вероятностью 2/3 на 0 позиции у неё 0 и с вероятностью 2/3 на 1-й единица. А если назвала 1, то у неё точно (1,0)

при этом ответ 0 принцесса даст с вероятностью 3/4, а 1 -- 1/4

тогда имеем 4 варианта

1-я   2-я   p     p1   p2    p_win   вклад в победу
0      0   9/16   2/3  2/3   5/9     9/16 * 5/9 = 5/16
0      1   3/16    0   2/3   2/3     3/16 * 2/3 = 2/16 -- !!!
1      0   3/16   2/3   0    2/3     3/16 * 2/3 = 2/16
1      1   1/16    1    1     1      1/16 *  1  = 1/16
итого                                            10/16 = 5/8 > 1/2 !!!

Так что решение явно есть, и смысл в том, что деля ситуацию на N (по числу ответов случаям) принцессы смещают условные вероятность проигрыша, при этом, при удачной стратегии, можно сместить так, что в частых раскладах вероятность выигрыша будет > .5, а в редких меньше. Но в среднем это даст общее матожидание > .5 !!!

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

И её матожидание выигрыша легко считается.

пусть у обе бесконечные последовательности представлены в виде первая_монета+хвост.

Тогда стратегия "позиция первой решки" даст :

решка + хвост1  решка + хвост2 -- обе скажут 0, и победят
решка + хвост1  орёл + хвост2  -- первая сделает ставку на орла, вторая с вероятностью .5 угадает позицию орла в хвост1
орёл + хвост1   решка + хвост2 -- аналогично
орёл + хвост1   орёл + хвост2  -- обе играют по той же стратегии на хвост1 и хвост2

Если р -- вероятность выигрыша при этой стратегии, то получим

4р = 1 + .5 + .5 + р => 3p = 2 => p = 2/3

Интересно, можно ли превзойти?

Здравствуйте, nikholas, Вы писали:

N>Злобный Дракон поймал двух принцесс, Читу и Ниту, и посадил их в разные башни
<…>
N>То есть Чита должна назвать нечётный номер, а Нита — чётный.

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

Сдаётся мне, что хитрость сидит в том, что последовательность бесконечная. Скорее всего это означает, что можно придумать такую стратегию, что вся ситуация станет внутренне противоречивой. Это будет следствием того, что мы будет использовать операции вроде "просмотреть всю последовательность и что-то посчитать", так как эта операция, скорее всего внутренне противоречива или, наоборот, неполна. Назовём стратегии такого вида Вид1.

С другой стороны, можно представить себе стратегию, в которой принцесса использует только операции вида "просматриваем последовательность, пока что-то не найдём".
Ок. Мы попадаем в ситуацию условной вероятности. Например, Нита ищет такую последовательность из 1000 бросков, в которой решек (или орлов) на 100 больше.
Это эквивалентно тому, что дракон бросает свою монетку 2000 раз и предъявляет последовательность принцессам, только если подпоследовательность Ниты удовлетворяет такому условию. Но даже тут Нита ничего не будет знать про результаты бросков Читы же. Назовём стратегии такого вида Вид2

Не совсем понятно, есть ли ещё какие-то виды стратегий для работы с бесконечной последовательностью.

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

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

Предположим, для начала, что стратегии у них одинаковые.
тогда стратегия -- это отображение пар результатов (0,0), (0,1) и т. д, на номер

Получаем условные вероятности.

Пусть при каких-то конкретных ответах принцесс, a1 и а2 вероятность получить в соответствующих позициях решку(0) — p1 и p2
тогда условная вероятность удачи -- это p1*p2 + (1-p1)*(1-p2) = 1 -p1 — p2 + 2 p1 p2, а неудачи -- p1(1-p2)+(1-p1)p2 = p1 + p2 — 2 p1 p2

Пусть, например, стратегия такая, что всегда 0, а если (1,0), то 1
тогда если принцесса назвала 1, то с вероятностью 2/3 на 0 позиции у неё 0 и с вероятностью 2/3 на 1-й единица. А если назвала 1, то у неё точно (1,0)

при этом ответ 0 принцесса даст с вероятностью 3/4, а 1 -- 1/4

тогда имеем 4 варианта

1-я   2-я   p     p1   p2    p_win   вклад в победу
0      0   9/16   2/3  2/3   5/9     9/16 * 5/9 = 5/16
0      1   3/16    0   2/3   2/3     3/16 * 2/3 = 2/16 -- !!!
1      0   3/16   2/3   0    2/3     3/16 * 2/3 = 2/16
1      1   1/16    1    1     1      1/16 *  1  = 1/16
итого                                            10/16 = 5/8 > 1/2 !!!

Так что решение явно есть, и смысл в том, что деля ситуацию на N (по числу ответов случаям) принцессы смещают условные вероятность проигрыша, при этом, при удачной стратегии, можно сместить так, что в частых раскладах вероятность выигрыша будет > .5, а в редких меньше. Но в среднем это даст общее матожидание > .5 !!!

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

И её матожидание выигрыша легко считается.

пусть у обе бесконечные последовательности представлены в виде первая_монета+хвост.

Тогда стратегия "позиция первой решки" даст :

решка + хвост1  решка + хвост2 -- обе скажут 0, и победят
решка + хвост1  орёл + хвост2  -- первая сделает ставку на орла, вторая с вероятностью .5 угадает позицию орла в хвост1
орёл + хвост1   решка + хвост2 -- аналогично
орёл + хвост1   орёл + хвост2  -- обе играют по той же стратегии на хвост1 и хвост2

Если р -- вероятность выигрыша при этой стратегии, то получим

4р = 1 + .5 + .5 + р => 3p = 2 => p = 2/3

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