Разбор задачи с собеседования про перебрасывание 20-гранного кубика

Напомню суть задачи. Первый игрок бросает 20-гранную кость и при желании может один раз ее перебросить. Второй игрок бросает 10-гранную кость один раз. Побеждает большее число; при равенстве – ничья. Когда первому игроку стоит перебрасывать кость, чтобы максимизировать шанс победы?

Всего возможно 10*20 = 200 сценариев:

{(1,1), (1,2), ..., (1,10); (2,1), (2,2), ... (2,10); ...; (10,10); (11,10); …; (20,10)}

Первый игрок выигрывает в 19+18+...+10 = 145 сценариях:

{(2,1), (3,1), ..., (20,1), (3,2), (4,2), ..., (20,2), ..., (11,10), ..., (20,10)}

Тогда вероятность выигрыша первого игрока при броске 145 / 200 = 0.725

И дальше рассуждаем. Если первому игроку выпало 1, то вероятность выигрыша, если не перебрасывать, равна 0. Если перебросить – 0.725.

Аналогично с остальными вариантами:

2 -> 1/10 -> 0.725 3 -> 2/10 -> 0.725 ... 8 -> 7/10 -> 0.725 9 -> 8/10 -> 0.725 10 -> 9/10 -> 0.725 11+ -> 1 -> 0.725

Получается, что 8 - самое большое значение, при котором в случае переброса мы повышаем вероятность на победу. А значит нужно перебрасывать, если выпало от 1 до 8 включительно.

В качестве бонуса: общая вероятность выигрыша при такой стратегии равна:

8/20 * 29/40 + 1/20 * 8/10 + 1/20 * 9/10 + 10/20 * 1 = 0.875.

А больше задач с собеседований и их разборы ищи по хештегу: #задачиссобеседований