Пару дней назад @Kojiec9 упомянул эту задачку в своем комментарии #comment_213151850 и мне подумалось, что я могу ее решить, не подглядывая в решения и не прибегая к рекуррентным формулам. Сразу сделаю оговорку, что мои знания математики заканчиваются на уровне школьной программы.
Итак, для того, чтобы узнать вероятность утери лапы, нам нужно знать количество исходов, когда Михаил лишился конечности, и общее количество всех исходов.
Каждую экспедицию енота Михаила за едой можно представить в виде разряда пятиричного числа:
- разряд "0" это "не нашел ничего" (20%)
- разряды "1", "2", "3", "4" это "что-то нашел" (80%)
В такой записи количество всех исходов:
total(L) = 5 ** L
Для удобства представления будем считать, что самая хронологически последняя вылазка находится в самом левом разряде записи. Тогда есть три варианта грамматики конфигураций:
- "00" X* - Михаил отгрыз себе лапу
- "0" X* - Михаил сохранил себе лапу
- X* - Михаил сохранил себе лапу
где X := ("1" | "2" | "3" | "4") "0"?
или в развернутом виде X := "1" | "10" | "2" | "20" | "3" | "30" | "4" | "40"
Дневник Михаила можно генерировать пошагово слева направо, где мы начинаем с желаемого исхода, и затем каждый шаг дописываем один из конституэнтов X:
00
001
0010
002
0020
003
0030
004
0040
0011
00110
0012
00120
...
Каждые S шагов генерации порождают суффиксы длиной от S (xxxx...) до 2*S (x0x0x0x0...),
где количество исходов для каждой длины L составляет:
runlen(L, S) = (2 ** (2 * S)) * C(S, L - S),
где C(n, k) = binomial(n, k) = n! / (k! * (n - k)!)
Но нас интересуют дневники, задаваемые не количеством шагов генерации, а итоговой фиксированной длиной, поэтому давайте преобразуем одно в другое.
На количество исходов фиксированной длины L оказывают влияние дневники с количеством шагов от ceil(L/2) до L включительно.
Значит, для фиксированной длины L количество суффиксов составляет:
fixlen(L) = sum(runlen(L, i) | i ← [ceil(L/2) .. L])
Линия судьбы Михаила может оборваться в любой момент, и чем раньше это произойдет, тем больше итоговых исходов займет эта ветка реальности. Если Михаил отгрызает себе лапу в день N, то это один исход, но если он делает это днем раньше, в N - 1, это соответствует уже пяти итоговым исходам.
Количество негативных исходов для суффикса длины не более L:
cumloss(L) = sum(fixlen(i) * (5 ** (L - i)) | i ← [0 .. L])
Количество негативных исходов для журнала длиной не более N дней:
loss(N) = cumloss(N - 2)
Итоговая вероятность утраты лапы на протяжении N дней:
beznogim(N) = loss(N) / total(N)
Если развернуть все функции, то получим одно монстрообразное выражение со сложностью O(1) по памяти и O(N**2) по времени:
beznogim(N) = sum(
sum(
(2 ** (i * 2)) * (i! / ((j - i)! * (2 * i - j)!))
| i ← [ceil(j / 2) .. j]
) * (5 ** (N - j - 2))
| j ← [0 .. N - 2]
) / (5 ** N)
Это можно преобразовать в код на, скажем, Python: https://pastebin.com/raw/Jfv0SKea
Для 250 дней вероятность Михаилу остаться на обочине истории (т.е. без лапы) составляет
5526226584677559509852960627995789914573481301128790556689672699135872514940708834066090771669469477712415378994712507503302194376238615272432632063692049752184707376064494905 исходов из
5527147875260444560247265192192255725514240233239220086415170220907898754023953317101764802222264464998750268125535784702076863325972445883937922417317167855799198150634765625
или 99.9833315372%.
Сохранит лапу Михаил в 921290582885050394304564196465810940758932110429529725497521772026239083244483035674030552794987286334889130823277198774668949733830611505290353625118103614490774570270720 случаях,
т.е. 0.016671241556%.
И это вроде бы совпадает с результатами, которые получили другие люди. Наверное, получилось?
