Задача с финала Яндекса на Middle Аналитика
Эту задачу также часто дают и в других компаниях. Давайте разберём этот баян 😎

Условие
Дан правильный шестигранный игральный кубик. Его можно бросить не более трёх раз и в любой момент остановиться. Как действовать, чтобы матожидание числа, выпавшего в последнем броске, было максимальным?

Решение
Будем решать задачу "с конца"
1) Если сейчас третий бросок, выбора бросать дальше или остановиться нет

Матожидание числа, которое выпадет на третьем броске E3 = (1 + 2 + 3 + 4 + 5 + 6)/6 = 3.5, так как каждое значение на кубике выпадает с равной вероятностью, равной 1/6

2) Если сейчас второй бросок

Допустим выпало число X, тогда есть 2 варианта:
- остановиться на X
- продолжить и на третьем броске получить матожидание 3.5

Значит нам выгодно остановиться на втором броске, если значение X ≥ 3.5. Для кубика это X = 4, 5, 6.

Посчитаем матожидание для двух последних бросков, с учётом нашего правила (останавливаемся на втором броске, если значение X ≥ 3.5)
- Вероятность того, что выпадут значения 4, 5, 6 равна 1/2 → их среднее (4 + 5 + 6)/3 = 5
- Вероятность того, что выпадут значения 1, 2, 3 равна 1/2 → в этом случае бросаем игральный кубик в третий раз. В среднем на третьем броске нам выпадает 3.5

E2 = (4 + 5 + 6)/3 * 1/2 + E3 * 1/2 = 5 * 1/2 + 3.5 * 1/2 = 4.25

3) Если сейчас первый бросок

Допустим выпало число Y, тогда есть 2 варианта:
- остановиться на Y
- продолжить и на втором броске получить матожидание 4.25

Значит нам выгодно остановиться на первом броске, если значение Y ≥ 4.25. Для кубика это Y = 5, 6

Наконец-то, посчитаем матожидание для числа, выпавшего в последнем броске, с учётом наших правил (останавливаемся на первом броске, если значение Y ≥ 4.25; останавливаемся на втором броске, если значение X ≥ 3.5)
- Вероятность того, что выпадут значения 5, 6 равна 1/3 → их среднее (5 + 6)/2 = 5.5
- Вероятность того, что выпадут значения 1, 2, 3, 4 равна 2/3 → в этом случае бросаем игральный кубик во второй раз. В среднем для двух последних бросков мы получаем значение 4.25

E1 = (5 + 6)/2 * 1/3 + E2 * 2/3 = 5.5 * 1/3 + 4.25 * 2/3 = 4.67

Оптимальная стратегия такая:
– после первого броска оставляем только 5 или 6
– если решили бросить второй раз, то теперь оставляем 4, 5, 6
– если дошёл до третьего раза, берем что выпало
При такой тактике матожидание финального значения 4.67, что выше 3.5 у одиночного броска

@ProdAnalysis