О коротких путях

Пролетала тут мимо задачка: https://avva.livejournal.com/3656270.html?style=mine
Дана игра: Алиса и Боб вместе бросают одну честную монету 100 раз. Каждый раз, когда выпадают подряд два орла (ОО), Алиса получает очко. Когда выпадает ОР, Боб получает очко. Побеждает (в игре) тот, у кого больше очков после 100 бросков.

Игра, кстати, не совсем тривиальная: хотя суммарно по всем играм Алиса и Боб получат строго поровну очков, но уже среди всех игр по 3 броска (а их 8), Алиса 1 раз победит с перевесом в 2 очка и 1 раз победит с перевесом в 1 очко (итого 2 победы в игре), а Боб 3 раза победит с перевесом в 1 очко (итого 3 победы в игре)

И было предложено соревнование: кто сможет быстрее перебрать все возможные игры из 100 бросков и точно подсчитать, в скольких из них побеждает Алиса, а в скольких - Боб.

Народ уже начал было расчехлять особо шустрые перебиралки ( Read more... )

x-post: https://livelight.livejournal.com/664401.html