Лига математиков

Пару дней назад @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%.

И это вроде бы совпадает с результатами, которые получили другие люди. Наверное, получилось?