2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 3, 4, 5, 6, 7
 
 Re: Чита, Нита и Дракон
Сообщение17.02.2019, 10:27 
Заслуженный участник


26/05/14
981
waxtep, проверьте меня, пожалуйста.

148 побед на этой диаграмме (а значит 178 на полной):
Код:
        1 0 1 0 1 0   1 0   1 0 1 0 1 0
        0 1 1 0 0 1   1 0   0 1 1 0 0 1
        0 0 0 1 1 1   1 0   0 0 0 1 1 1
        0 0 0 0 0 0   0 1   1 1 1 1 1 1
                                       
        0 2 0 1 1 2   0 3   0 2 0 1 1 2
                                       
1000 0  X X X X - X   X X   X X X X - X
0100 2  X X X X X -   - X   X X X X X -
1100 0  X X X - X X   X X   X X X - X X
0010 1  X X - X X X   - X   X X - X X X
1010 1  - X X X X X   X X   - X X X X X
0110 2  X - X X X X   - X   X - X X X X
                           
1110 0  X - X - X -   X X   X - X - X -
0001 3  X X X X X X   X X   - - - - - -
                           
1001 0  X X X X - X   X -   X X X X - X
0101 2  X X X X X -   - -   X X X X X -
1101 0  X X X - X X   X -   X X X - X X
0011 1  X X - X X X   - -   X X - X X X
1011 1  - X X X X X   X -   - X X X X X
0111 2  X - X X X X   - -   X - X X X X


waxtep, термин симметричная вы понимаете правильно. Я боюсь это уведёт нас в сторону, но вы упомянули двойственную задачу: найти стратегию с минимальным числом совпадений. Я думаю что это более сложная задача. Например: для "максимальной" задачи всегда находились симметричные решения, для "минимальной" это не так.

 Профиль  
                  
 
 Re: Чита, Нита и Дракон
Сообщение17.02.2019, 14:49 
Аватара пользователя


07/01/16
1426
Аязьма
slavav в сообщении #1376574 писал(а):
148 побед на этой диаграмме (а значит 178 на полной):
Ах елочки зелёные, ну конечно! Задача для $n+1$ монет это четыре задачи для $n$ монет, плюс небольшой хвостик. Чуть-чуть до этого своим умом не дошел :-) И понятно, почему у нас ответы расходятся - я перечисляю выборы для лексикографически упорядоченных исходов, а Вы их группируете

-- 17.02.2019, 15:38 --

waxtep в сообщении #1376608 писал(а):
а Вы их группируете
Точнее, порядок разрядов используете противоположный; в общем, чтобы перейти от Ваших обозначений к моим (нумерация с единицы и начинаем с $0001$, а не с $1000$), надо вычесть номер броска из четырех (в общем случае из $n$). В моих обозначениях симметричная стратегия тогда действительно будет $(4,2,4,3,3,2,4,1,4,2,4,3,3,2)$

 Профиль  
                  
 
 Re: Чита, Нита и Дракон
Сообщение17.02.2019, 17:34 
Аватара пользователя


07/01/16
1426
Аязьма
Угу. То есть, получается, существуют стратегии, обеспечивающие для числа спасительных исходов $S_n$ при $n$ бросков у каждой стороны следующее:$$\begin{cases}
S_{2m}=4S_{2m-1}+2\\
S_{2m+1}=4S_{2m}+4\\
S_1=2
\end{cases}$$Предел вероятности спасения у такой штуки действительно $0.7$

 Профиль  
                  
 
 Re: Чита, Нита и Дракон
Сообщение17.02.2019, 17:42 


05/09/16
11469
waxtep в сообщении #1376641 писал(а):
Предел вероятности спасения у такой штуки действительно $0.7$
То есть это все-таки оценка снизу (при бесконечном количестве бросков существует стратегия с вероятностью победы не менее $0,7$), или есть какие-то соображения, по которым лучших стратегий (на большом количестве бросков) не существует?

 Профиль  
                  
 
 Re: Чита, Нита и Дракон
Сообщение17.02.2019, 18:22 
Заслуженный участник


26/05/14
981
Замкнутые формулы для конечных стратегий:
$N_k = \frac{7\cdot4^k - 2 (-1)^k}{10} - 1$,
$D_k = 4^k$,
$\varepsilon_k = \frac{5 + (-1)^k}{5\cdot4^k}$.
$\varepsilon_k = \frac{7}{10} - \frac{N_k}{D_k}$.

Идея была следующая: построить последовательность конечных стратегий с этими свойствами. Предположим что найдется $s_k$ с вероятностью больше $\frac{N_k}{D_k}$, тогда из неё можно построить стратегию $s_{k-1}$ с вероятностью больше $\frac{N_{k-1}}{D_{k-1}}$ (это ещё надо придумать как). По индукции придти к противоречию.

 Профиль  
                  
 
 Re: Чита, Нита и Дракон
Сообщение18.02.2019, 00:39 
Аватара пользователя


07/01/16
1426
Аязьма
slavav в сообщении #1376574 писал(а):
Я боюсь это уведёт нас в сторону, но вы упомянули двойственную задачу: найти стратегию с минимальным числом совпадений. Я думаю что это более сложная задача. Например: для "максимальной" задачи всегда находились симметричные решения, для "минимальной" это не так.
Но для двойственной задачи ("xor-дракона", когда принцессы должны выбрать разные исходы их бросков, чтобы спастись), похоже, тот же предел для вероятности; по крайней мере, для $n=2,3,4$ это так. Вычислительная трудность для несимметричных стратегий растет с $n\cdot2^{3n}$ до $n^2\cdot2^{4n}$, для маленьких $n$ все еще обозримо; хочу попробовать, ну, наверное, уже ближе к следующим выходным.
wrest в сообщении #1376644 писал(а):
То есть это все-таки оценка снизу
Нет, я имел в виду, что, скорее всего, это наилучшие стратегии, правда, доказывать, как выше предлагает slavav не пытался, ограничился наглядными соображениями "вот четыре блока для задачи меньшего размера, вот внешний контур, вот "крест" посередине"...

-- 18.02.2019, 01:12 --

(эксельное баловство с картинкой :-))

Симметричная стратегия для $n=4$:

Изображение

Из правого нижнего угла подбирается дракон, косичка одной из принцесс уже в его пасти; голова другой принцессы (с косичкой) - в левой части картинки

 Профиль  
                  
 
 Re: Чита, Нита и Дракон
Сообщение21.02.2019, 00:20 
Аватара пользователя


07/01/16
1426
Аязьма
waxtep в сообщении #1376781 писал(а):
Вычислительная трудность для несимметричных стратегий растет с $n\cdot2^{3n}$ до $n^2\cdot2^{4n}$, для маленьких $n$ все еще обозримо;
Это я конечно очень погорячился, правильно $n^{2^n}\cdot2^{2n}\rightarrow n^{2\cdot2^n}\cdot2^{2n}$. "Столько ему не съесть", это же рост с $10^{236}$ до $10^{467}$ для $n=8$, как это можно полностью перебрать даже для симметричной задачи?! :shock: :shock: :shock:

 Профиль  
                  
 
 Re: Чита, Нита и Дракон
Сообщение21.02.2019, 10:43 


05/09/16
11469
То есть, все-таки, доказательства что предел вероятности победы при оптимальной стратегии равен $0,7$, вот именно доказательства -- нет?

 Профиль  
                  
 
 Re: Чита, Нита и Дракон
Сообщение21.02.2019, 10:55 
Заслуженный участник


26/05/14
981
wrest в сообщении #1377478 писал(а):
То есть, все-таки, доказательства что предел вероятности победы при оптимальной стратегии равен $0,7$, вот именно доказательства -- нет?
Такого доказательства нет. Как только оно появится, задача будет решена полностью.

-- 21.02.2019, 11:14 --

mihaild в обсуждении на OpenDataScience предъявил бесконечную симметричную стратегию с вероятностью $\frac{7}{10}$:
Цитата:
Бьем последовательность на тройки.
Выбираем первую тройку, в которой не все результаты одинаковые.
Называем число "начальная позиция тройки" + `{'HHT': 1, 'HTH': 2, 'HTT': 2, 'THH': 0, 'THT': 1, 'TTH': 0}`
Если у обеих принцесс номер выбранной тройки совпадает - то вероятность победы $\frac{5}{6}$, иначе - $\frac{1}{2}$.
Вероятность того, что номера выбранных троек совпадают - $\frac{3}{5}$.
Итого вероятность победы $0.7$

 Профиль  
                  
 
 Re: Чита, Нита и Дракон
Сообщение26.01.2020, 01:05 


25/01/20
1
Стратегию для 4 бросков монеты ( 2 на каждую принцессу) я понял, а вот какая должна быть стратегия для 6, 8, 10...
Для 2 стратегия такая, если у одного выпадают О,О или О,Р то он выбирает номер первого броска в последовательности второго ( если у него чёт - то 1, если нечёт то 2), а если Р,Р или Р,О - то номер второго.
Когда у нас всего 6 бросков( по 3 на принцессу), то вариантов выпадения у каждого по 8, как мы должны их распределить? Так же на 2 варианта ( 1 или 2) или на 3?

З.Ы. И есть ли смысл, если задача найти стратегию, при которой шанс победы больше 0.5, для этого достаточно смотреть только на первые 4 броска. ( Да далее шанс победы выше, но задача же решена)

 Профиль  
                  
 
 Re: Чита, Нита и Дракон
Сообщение26.01.2020, 01:13 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
KrimsN в сообщении #1436942 писал(а):
Так же на 2 варианта ( 1 или 2) или на 3?
На три. Чуть выше есть конкретный пример как это сделать.
KrimsN в сообщении #1436942 писал(а):
если задача найти стратегию, при которой шанс победы больше 0.5
Кто вам это сказал? Задача - максимизировать вероятность победы. И пока что очень похоже на то что для этого нужна вся бесконечная последовательность (если оптимальная вероятность $0.7$, а на это похоже, то точно конечного числа бросков не хватит).

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 101 ]  На страницу Пред.  1 ... 3, 4, 5, 6, 7

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group