- Добро пожаловать на Лингвофорум.
Автор RawonaM
- августа 14, 2011, 23:23Цитата: Квас от августа 14, 2011, 23:18Это не я издеваюсь. Это диофант издевается, откуда Бод взял задачу. Там написано «Вес: 1 сложность: 1 класс: 8-10». WTF???
Издеваетесь? Высшая математика какая-то.
Более того, там же написано, что взято из http://projecteuler.net/ .
Что является:
ЦитироватьProject Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve.
Инсайты нужны, оказывается. Надо бы найти там эту задачу и посмотреть ее рейтинг. Хотя конечно если ее классифицировать как задачу по программированию, то это действительно для первого класса.
Автор Bhudh
- августа 14, 2011, 23:21[Цитата: Квас]
Высшая математика какая-то.
[/Цитата]
Высшая математика какая-то.
[/Цитата]
Автор Квас
- августа 14, 2011, 23:18Издеваетесь? Высшая математика какая-то.
Автор RawonaM
- августа 14, 2011, 23:17Цитата: Квас от августа 14, 2011, 23:14Чего это?
Ну вы, блин, даёте. (Чешет репу.)
![:-\](https://lingvoforum.net/Smileys/default/sm_confused.gif ":-\")
У вас есть более простое решение?Автор Квас
- августа 14, 2011, 23:14Ну вы, блин, даёте. (Чешет репу.)
Автор RawonaM
- августа 14, 2011, 23:07Цитата: Bhudh от августа 14, 2011, 23:03Я тот же скрипт на питоне гонял, там еще три-четыре цифры.
У svarogʼа на один digit точнее.
А они лишнее, ибо нам нужно матожидание выигрышей, для этого достаточно шесть цифр.
Автор Bhudh
- августа 14, 2011, 23:03У svarogʼа на один digit точнее.
Автор RawonaM
- августа 14, 2011, 23:03Voilá!
Автор RawonaM
- августа 14, 2011, 22:45Значит, выше была аппроксимация, а теперь попробуем посчитать точно.
По формуле отсюда: (wiki/en) Dice#Probability
Вероятность выпадения суммы k на n костях с s гранями:
![[tex]F_{s,n}(k)=\frac{1}{s^n}\sum_{i=0}^{\left \lfloor \frac{k-n}{s} \right \rfloor} (-1)^i {n \choose i} {k-si-1 \choose n-1}[/tex]](https://latex.codecogs.com/png.latex?F_{s,n}(k)=\frac{1}{s^n}\sum_{i=0}^{\left \lfloor \frac{k-n}{s} \right \rfloor} (-1)^i {n \choose i} {k-si-1 \choose n-1} "F_{s,n}(k)=\frac{1}{s^n}\sum_{i=0}^{\left \lfloor \frac{k-n}{s} \right \rfloor} (-1)^i {n \choose i} {k-si-1 \choose n-1}")
А поэтому, для олиных костей:
![[tex]F_{8,6}(k)=\frac{1}{8^6}\sum_{i=0}^{\left \lfloor \frac{k-8}{6} \right \rfloor} (-1)^i {6 \choose i} {k-8i-1 \choose 6-1}[/tex]](https://latex.codecogs.com/png.latex?F_{8,6}(k)=\frac{1}{8^6}\sum_{i=0}^{\left \lfloor \frac{k-8}{6} \right \rfloor} (-1)^i {6 \choose i} {k-8i-1 \choose 6-1} "F_{8,6}(k)=\frac{1}{8^6}\sum_{i=0}^{\left \lfloor \frac{k-8}{6} \right \rfloor} (-1)^i {6 \choose i} {k-8i-1 \choose 6-1}")
А для диминых костей:
![[tex]F_{12,4}(k)=\frac{1}{12^4}\sum_{i=0}^{\left \lfloor \frac{k-4}{12} \right \rfloor} (-1)^i {4 \choose i} {k-12i-1 \choose 4-1}[/tex]](https://latex.codecogs.com/png.latex?F_{12,4}(k)=\frac{1}{12^4}\sum_{i=0}^{\left \lfloor \frac{k-4}{12} \right \rfloor} (-1)^i {4 \choose i} {k-12i-1 \choose 4-1} "F_{12,4}(k)=\frac{1}{12^4}\sum_{i=0}^{\left \lfloor \frac{k-4}{12} \right \rfloor} (-1)^i {4 \choose i} {k-12i-1 \choose 4-1}")
И вероятность выигрыша:
![[tex]\sum_{i=6}^{48}\sum_{j=4}^{i-1}F_{8,6}(i) F_{12,4}(j)[/tex]](https://latex.codecogs.com/png.latex?\sum_{i=6}^{48}\sum_{j=4}^{i-1}F_{8,6}(i) F_{12,4}(j) "\sum_{i=6}^{48}\sum_{j=4}^{i-1}F_{8,6}(i) F_{12,4}(j)")
что в принципе одно и то же, что и ![[tex]\sum_{i=0}^{\infty}\sum_{j=0}^{i-1}F_{8,6}(i) F_{12,4}(j)[/tex]](https://latex.codecogs.com/png.latex?\sum_{i=0}^{\infty}\sum_{j=0}^{i-1}F_{8,6}(i) F_{12,4}(j) "\sum_{i=0}^{\infty}\sum_{j=0}^{i-1}F_{8,6}(i) F_{12,4}(j)")
Достаточно подставить все и посчитать. Можно воспользоваться Максимой.
По формуле отсюда: (wiki/en) Dice#Probability
Вероятность выпадения суммы k на n костях с s гранями:
А поэтому, для олиных костей:
А для диминых костей:
И вероятность выигрыша:
Достаточно подставить все и посчитать. Можно воспользоваться Максимой.
Автор RawonaM
- августа 14, 2011, 16:56Вспомнил про эту задачу. Попробуем с новыми силами и знаниями.
Обозначим случайную величину X — сумма костей Оли.
Обозначим случайную величину Y — сумма костей Димы.
Оля выигрывает, если X-Y>0. Т.к. у нас миллион раундов, то можно считать, что распределение нормальное (по центральной предельной теореме).
Найдем матожидание и дисперсию X-Y.
E[X]=6·4.5=26
E[Y]=4·6.5=27
E[X-Y]=E[X]-E[Y]=1
Дисперсия одного кубика:
![[tex]Var(X_i)=\sum_{i=1}^8\frac18(i-4.5)^2=5.25[/tex]](https://latex.codecogs.com/png.latex?Var(X_i)=\sum_{i=1}^8\frac18(i-4.5)^2=5.25 "Var(X_i)=\sum_{i=1}^8\frac18(i-4.5)^2=5.25")
![[tex]Var(Y_i)=\sum_{i=1}^{12}\frac1{12}(i-6.5)^2=\frac{143}{12}[/tex]](https://latex.codecogs.com/png.latex?Var(Y_i)=\sum_{i=1}^{12}\frac1{12}(i-6.5)^2=\frac{143}{12} "Var(Y_i)=\sum_{i=1}^{12}\frac1{12}(i-6.5)^2=\frac{143}{12}")
Дисперсия суммы (кубики независимы):
Var(X)=6·5.25=31.5
Var(Y)=4·143/12=143/3
Var(X-Y)=Var(X)+Var(Y)=31.5+143/3=475/6~79.16666
Выходит X-Y ~ W = N(1,475/6).
Нам нужно найти P{X-Y>0}, но т.к. мы приближаем дискретную целую величину непрерывной, то сделаем поправку и посчитаем P{W≥0.5}.
По таблице нормального распределения высчитываем:
P{W≥0.5}~1-0.47759~0.52241
Что дает примерно тот же результат, полученный выше в лоб:
Вопрос кто из нас больше округлял, компьютер или приближение к нормальной величине
Чтобы узнать ожидаемое количество выигрышев просто умножаем вероятность на миллион, т.е. это 522 тысячи с чем-то.
Цитата: Bhudh от мая 20, 2011, 22:49Цитата: http://diofant.ru/problem/1786Оля и Дима играют в кости.
У Оли шесть костей в форме октаэдра, и грани каждой из них занумерованы числами от 1 до 8.
У Димы четыре кости в форме додекаэдра, и грани каждой из них занумерованы числами от 1 до 12.
В каждом туре игроки бросают все свои кости по одному разу. Побеждает тот, у кого сумма выпавших очков больше. При равенстве фиксируется ничья.
Каково математическое ожидание количества побед Оли после миллиона туров?
Обозначим случайную величину X — сумма костей Оли.
Обозначим случайную величину Y — сумма костей Димы.
Оля выигрывает, если X-Y>0. Т.к. у нас миллион раундов, то можно считать, что распределение нормальное (по центральной предельной теореме).
Найдем матожидание и дисперсию X-Y.
E[X]=6·4.5=26
E[Y]=4·6.5=27
E[X-Y]=E[X]-E[Y]=1
Дисперсия одного кубика:
Дисперсия суммы (кубики независимы):
Var(X)=6·5.25=31.5
Var(Y)=4·143/12=143/3
Var(X-Y)=Var(X)+Var(Y)=31.5+143/3=475/6~79.16666
Выходит X-Y ~ W = N(1,475/6).
Нам нужно найти P{X-Y>0}, но т.к. мы приближаем дискретную целую величину непрерывной, то сделаем поправку и посчитаем P{W≥0.5}.
По таблице нормального распределения высчитываем:
P{W≥0.5}~1-0.47759~0.52241
Что дает примерно тот же результат, полученный выше в лоб:
Цитата: svarog от июня 19, 2011, 15:27
Итого $OlyaWins = 0.522008753117221
Вопрос кто из нас больше округлял, компьютер или приближение к нормальной величине
Чтобы узнать ожидаемое количество выигрышев просто умножаем вероятность на миллион, т.е. это 522 тысячи с чем-то.