Решение задачи 2. Стохастический Баше

Условие задачи

Вася и Петя отлично умеют анализировать Баше-подобные игры, поэтому они решили несколько разнообразить игровой процесс.

Сначала Вася называет некоторое число 50<N<100. На стол кладётся N спичек.

Далее при помощи обычного игрального кубика (с числами от 1 до 6 на гранях) выбрасываются три числа: a, b и c (2 или 3 из них могут оказаться равными).

Игроки по очереди берут из стопки a, b или c спичек. Проигрывает тот, кто не может сделать ход.

Какое число нужно назвать Васе, чтобы максимизировать свои шансы на выигрыш, если первым будет ходить Петя?

Решение

Как находить выигрышные позиции для конкретного набора допустимых ходов, подробно описывается в соответствующей статье. Для решения данной задачи требуется построить таблицу выигрышных и проигрышных позиций для всех возможных наборов (a, b, c).

Таких наборов будет 41. Расчёты очень удобно производить в Экселе.

Теперь, т.к. Вася ходит вторым, для каждого числа спичек N складываем вероятности тех раскладов (a,b,c), при которых эта позиция будет проигрышной.

Оказывается, что больше всего шансов проиграть будет у Пети, делающего первый ход, если игра начнётся с 72 спичек. В этом случае Вася выиграет в среднем 7 партий из 9.

Если бы Вася ходил первым, ему надо называть число 59 – в такой позиции игрок, делающий первый ход выиграет в 185 случаях из 216.

Интересно, что если бы не было ограничения на число N, Вася мог бы гарантировать себе победу, назвав число 10080. В этом случае для любых наборов допустимых ходов (a,b,c) игрок, делающий ход вторым, выигрывает.

Для игрока, делающего первый ход при любых тройках допустимых ходов выигрышной будет позиция 3239.