Злобный Дракон поймал двух принцесс, Читу и Ниту, и посадил их в разные башни
своего замка. Затем Злобный Дракон подбросил правильную монетку бесконечное число раз.
Все результаты чётных бросков он сообщил Чите, а все результаты нечётных — Ните.
Далее Дракон предлагает каждой из принцесс назвать номер
любого подбрасывания, результат которого ей не известен.
То есть Чита должна назвать нечётный номер, а Нита — чётный.
Если результаты бросков, названных Читой и Нитой, одинаковые, то Злобный Дракон
дарит каждой принцессе тортик, розового плюшевого зайца и отпускает на свободу.
Если же результаты бросков отличаются, то Злобный Дракон съедает Читу и Ниту
с клюквенным вареньем. Дракон обожает принцесс и клюквенное варенье!
Принцессы знают о повадках Злобного Дракона и могли заранее до похищения договориться
о стратегиях. Как им следует себя вести и чему равна вероятность спасения?
Здравствуйте, nikholas, Вы писали:
N>Злобный Дракон поймал двух принцесс, Читу и Ниту, и посадил их в разные башни N>своего замка. Затем Злобный Дракон подбросил правильную монетку бесконечное число раз. N>Все результаты чётных бросков он сообщил Чите, а все результаты нечётных — Ните. N>Далее Дракон предлагает каждой из принцесс назвать номер N>любого подбрасывания, результат которого ей не известен. N>То есть Чита должна назвать нечётный номер, а Нита — чётный.
N>Если результаты бросков, названных Читой и Нитой, одинаковые, то Злобный Дракон N>дарит каждой принцессе тортик, розового плюшевого зайца и отпускает на свободу. N>Если же результаты бросков отличаются, то Злобный Дракон съедает Читу и Ниту N>с клюквенным вареньем. Дракон обожает принцесс и клюквенное варенье!
N>Принцессы знают о повадках Злобного Дракона и могли заранее до похищения договориться N>о стратегиях. Как им следует себя вести и чему равна вероятность спасения?
Вероятность спасения 100%
Одна принцесса ищет в "своих" бросках последовательность 01. Озвучивает индекс единицы.
Вторая принцесса смотрит результат броска по этому индексу. Если "ее" бросок равен 1, то он озвучивает тот же индекс, если равен 0, то предыдущий.
Более точное описание:
Запишем результаты бросков следующим образом
Ч[0], Н[0], Ч[1], Н[1] ...
Ч — броски, о которых знает Чита. Н — броски, о которых знает Нита. Такая нумерация отличается от нумерации Дракона, но эти нумерации взаимозаменяемы.
Чита находит такое k, что ее последовательные броски Ч[k]=0 и Ч[k+1]=1. Чита озвучивает свое решение: k+1
Нита проверяет, чему равно Н[k+1].
Если Н[k+1]=1, то Нита озвучивает k+1. Принцессы спасаются т.к. Ч[k+1] = Н[k+1] = 1
Если Н[k+1]=0, то Нита озвучивает k. Принцессы спасаются т.к. Ч[k] = Н[k+1] = 0
Здравствуйте, Буравчик, Вы писали:
Б>Одна принцесса ищет в "своих" бросках последовательность 01. Озвучивает индекс единицы. Б>Вторая принцесса смотрит результат броска по этому индексу. Если "ее" бросок равен 1, то он озвучивает тот же индекс, если равен 0, то предыдущий.
Они сидят в разных башнях и не слышат ответы друг друга
Здравствуйте, nikholas, Вы писали:
N>Здравствуйте, Буравчик, Вы писали:
Б>>Одна принцесса ищет в "своих" бросках последовательность 01. Озвучивает индекс единицы. Б>>Вторая принцесса смотрит результат броска по этому индексу. Если "ее" бросок равен 1, то он озвучивает тот же индекс, если равен 0, то предыдущий.
N>Они сидят в разных башнях и не слышат ответы друг друга
Я как понял, этот номер бесконечен, все дело в способе его выбора. Это так?
В условии нечетко сформулированы некоторые аспекты.
> Затем Злобный Дракон подбросил правильную монетку бесконечное число раз.
По идее, хотя монетка правильная, но четко не сказано, что Дракон бросает ее честно.
Полагаю, что это надо понимать как
— каждый бросок монетки дает случайный исход 0 или 1 с одинаковой вероятностью 1/2
> Дракон предлагает каждой из принцесс назвать номер любого подбрасывания, результат которого ей не известен.
Эту фразу, опять же, можно понять по разному. Чуть ниже в топике вы уточнили, что Чита и Гита дают ответы независимо друг от друга и не имеют никакой дополнительной информации.
С учетом таких замечаний совершенно ясно, что Чита и Гита могут называть какие угодно разрешенные им индексы.
Вероятность спастись от этого не изменится и составит 1/2.
Здравствуйте, nikholas, Вы писали:
N>Злобный Дракон поймал двух принцесс, Читу и Ниту, и посадил их в разные башни N>своего замка. Затем Злобный Дракон подбросил правильную монетку бесконечное число раз. N>Все результаты чётных бросков он сообщил Чите, а все результаты нечётных — Ните. N>Далее Дракон предлагает каждой из принцесс назвать номер N>любого подбрасывания, результат которого ей не известен. N>То есть Чита должна назвать нечётный номер, а Нита — чётный.
N>Если результаты бросков, названных Читой и Нитой, одинаковые, то Злобный Дракон N>дарит каждой принцессе тортик, розового плюшевого зайца и отпускает на свободу. N>Если же результаты бросков отличаются, то Злобный Дракон съедает Читу и Ниту N>с клюквенным вареньем. Дракон обожает принцесс и клюквенное варенье!
N>Принцессы знают о повадках Злобного Дракона и могли заранее до похищения договориться N>о стратегиях. Как им следует себя вести и чему равна вероятность спасения?
Принцесса находит в рассказе дракона бесконечную последовательность, где все четные или не четные(зависит от принцессы) "орлы" и говорит дракону четный или не четный(опять зависит от принцессы) индекс из этой последовательности.
Здравствуйте, nikholas, Вы писали:
N>Злобный Дракон поймал двух принцесс, Читу и Ниту, и посадил их в разные башни N>своего замка. Затем Злобный Дракон подбросил правильную монетку бесконечное число раз. N>Все результаты чётных бросков он сообщил Чите, а все результаты нечётных — Ните. N>Далее Дракон предлагает каждой из принцесс назвать номер N>любого подбрасывания, результат которого ей не известен. N>То есть Чита должна назвать нечётный номер, а Нита — чётный.
N>Если результаты бросков, названных Читой и Нитой, одинаковые, то Злобный Дракон N>дарит каждой принцессе тортик, розового плюшевого зайца и отпускает на свободу. N>Если же результаты бросков отличаются, то Злобный Дракон съедает Читу и Ниту N>с клюквенным вареньем. Дракон обожает принцесс и клюквенное варенье!
N>Принцессы знают о повадках Злобного Дракона и могли заранее до похищения договориться N>о стратегиях. Как им следует себя вести и чему равна вероятность спасения?
Я наверно не понял задачу.
Чита говорит любой нечётный номер, где выпал орёл (она же знает результаты всех нечётных номеров). Нита аналогично говорит любой чётный номер, где тоже выпал орёл. И?
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Если первой отвечает Чита, она называет такой нечетный индекс N, что
последовательность
четный 0
нечетный ?
четный 1.
Нита знает значение по нечетному индексу, и называет N-1 или N+1 в зависимости, 0 там или 1.
Так как Дракон "бесконечно" бросал монетку, возьмём вероятность существования последовательности 0,?,1 за единицу, т.е. спасутся 100%.
N>о стратегиях. Как им следует себя вести и чему равна вероятность спасения?
Чита выбирает такой х, что x*2 -орел, а х*4 — решка
Нита знает что лежит в х, и теперь знает что в x*2 -орел, а х*4 — решка
Здравствуйте, nikholas, Вы писали:
N>Затем Злобный Дракон подбросил правильную монетку бесконечное число раз.
Из фактов о Чаке Норрисе: Чак Норрис досчитал до бесконечности. Дважды.
N>Как им следует себя вести
Перво-наперво надо объявить конкурс, что тот герой, что выкрадет у дракона правильную монету (вещь редкая цены немалой!), сможет по выбору жениться на одной из принцесс.
Если же герои не справятся (или если они уже замужем), тогда принцессам надо заранее самим подбросить какую-нибудь монету и какой стороной та упадёт, ту и использовать в дальнейшем. Потому как судьба.
Интуитивно понятно, что в случае поимки драконом обеим следует сделать одно и тоже. А именно: из результатов сообщённых драконом выбрать максимально длинную последовательность состоящую из одинаковых результатов совпадающих с тем, что им выпал, когда они сами подбрасывали монету. После этого взять позицию близкую к середине выбранной последовательности (там будет бесконечность плюс-минус 1) и назвать её.
N>и чему равна вероятность спасения?
0.9(9)
Я как-то не очень понял условие:
N>Все результаты чётных бросков он сообщил Чите, а все результаты нечётных — Ните.
... N>Далее Дракон предлагает каждой из принцесс назвать номер N>любого подбрасывания, результат которого ей не известен.
... N>Если результаты бросков, названных Читой и Нитой, одинаковые
Как вообще при этих условиях результаты могут быть одиноковые? Ведь все броски, которые не знает Чита — не чётные, а все которые не знает Нита — чётные. То есть их ответы принадлежат непересекающимся множествам и по условию не могут совпасть.
Здравствуйте, nikholas, Вы писали:
N>Принцессы знают о повадках Злобного Дракона и могли заранее до похищения договориться N>о стратегиях. Как им следует себя вести и чему равна вероятность спасения?
Чита находит и называет такой n для которого: f(n-1) — орел, f(n+1) — решка. Нита в свою очередь слышит названный Читой номер n и, если f(n) — орел, называет n-1, если же f(n) — решка, то называет n+1. При длине последовательности, стремящейся к бесконечности, вероятность существования решения стремится к единице.
--
Не можешь достичь желаемого — пожелай достигнутого.
Здравствуйте, rg45, Вы писали:
R>Чита находит и называет такой n для которого: f(n-1) — орел, f(n+1) — решка. Нита в свою очередь слышит названный Читой номер n и, если f(n) — орел, называет n-1, если же f(n) — решка, то называет n+1. При длине последовательности, стремящейся к бесконечности, вероятность существования решения стремится к единице.
Принцессы не знаю ответы друг друга. Т.е. отвечают одновременно.
Здравствуйте, nikholas, Вы писали:
N>Здравствуйте, Буравчик, Вы писали:
Б>>Одна принцесса ищет в "своих" бросках последовательность 01. Озвучивает индекс единицы. Б>>Вторая принцесса смотрит результат броска по этому индексу. Если "ее" бросок равен 1, то он озвучивает тот же индекс, если равен 0, то предыдущий.
N>Они сидят в разных башнях и не слышат ответы друг друга
Тогда на ум приходит только использование того, что маловероятно что монета всегда выпадет одной стороной.
Cтратегия будет "назови номер первой решки в своей последовательности" по прикидке на 3-4 бросках это даст ~70%.
Но на самом деле 0%, бесконечное количество бросков требует бесконечного времени, потому принцессы помрут до того как дадут ответ.
Здравствуйте, nikholas, Вы писали:
N>Принцессы знают о повадках Злобного Дракона и могли заранее до похищения договориться N>о стратегиях. Как им следует себя вести и чему равна вероятность спасения?
А они что-то, кроме результатов бросков, которые им сообщают, знают? Ну, там, ответ другой принцессы, и т. п? Есть какое-то информационное взаимодействие между принцессами?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
E>А они что-то, кроме результатов бросков, которые им сообщают, знают? Ну, там, ответ другой принцессы, и т. п? Есть какое-то информационное взаимодействие между принцессами?
Ну если они друг-другу информацию передают, то задача становится совсем простой и неинтересной.
Интересно — это когда каждой известна только своя независимая последовательность бросков, но тем не менее существуют стратегии с вероятностью спасения существенно выше 50%. Это прямо удивительно неожиданный факт
Здравствуйте, 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
Так что решение явно есть, и смысл в том, что деля ситуацию на 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
Интересно, можно ли превзойти?
Ещё интересно, есть ли оптимальная симметричная стратегия, или двум принцессам нужно разных придерживаться. Пока всё что я нашёл, имело и симметричный вариант стратегии...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
