JetLend — оптимальная стратегия перебросов кубика и минимальное N

Условие

Игра: крупье бросает шестигранный кубик, выигрыш = грань × 100 ₽. Если результат не устраивает — можно перебросить, отказавшись от предыдущего. Дано N перебросов. Входная ставка 475 ₽. Найти минимальное N, при котором игра статистически выигрышна (ожидаемый выигрыш > 475 ₽) при оптимальной стратегии.

Решение

Подход — обратное ДП

Стратегия очевидна: переброс делаем, если текущая грань меньше ожидаемого выигрыша при оставшемся числе перебросов.

Обозначим V(k) — ожидаемый выигрыш игры, в которой осталось k перебросов (плюс текущий бросок). При k=0 (нет перебросов): V(0) = 3.5 × 100 = 350 (среднее по кубику).

Для k ≥ 1: после первого броска видим грань f. Если оставить — выиграем 100·f. Если перебросить — ожидаем V(k−1) · 100 (всё то же самое, но с k−1 перебросов осталось).

Оптимально остановиться, если 100·f ≥ 100·V(k−1), то есть f ≥ ⌈V(k−1)⌉.

Рекурсия:

V(k) = E[max(f, V(k−1))]
     = (1/6) · Σ_{f=1..6} max(f, V(k−1))

Расчёт

def V(k):
    if k == 0:
        return 3.5
    prev = V(k - 1)
    return sum(max(f, prev) for f in range(1, 7)) / 6
 
for n in range(0, 8):
    e_win = V(n) * 100
    print(f"N={n}: E[winning] = {e_win:.4f} ₽; profit = {e_win - 475:.4f}")

Результаты:

Минимальный N, при котором ожидаемый выигрыш > 475: N = 3.

Стратегии для каждого N

• N=3: V(2) ≈ 4.667. Оставляем при f ≥ 5, иначе перебрасываем.
• N=2: V(1) = 4.25. Оставляем при f ≥ 5.
• N=1: V(0) = 3.5. Оставляем при f ≥ 4.

Подводные камни

1. «N перебросов» — это N дополнительных бросков сверх первого, или N всего? В стандартной формулировке — N возможных перебросов, всего бросков до N+1. Обычно на собесе уточняйте: автор задачи имел в виду N перебросов, то есть бросков ≤ N+1.
2. Стратегия не «оставлять, если 6» — слишком мало. Оптимум — «оставить, если ≥ V(k−1)».
3. «Статистически выигрышна» = ожидаемый выигрыш строго больше ставки. На больших дистанциях.
4. Округление V. При сравнении f с V(k−1) сравниваем целое (грань) с дробным. f=5 ≥ 4.667 — оставляем. f=4 < 4.667 — перебрасываем.
5. Backward induction — стандартный приём для optimal stopping. Не путать с greedy «перебрасываем, пока не выпадет 6».

Эталонный ответ

Обратное ДП: V(k) = E[max(f, V(k−1))], V(0) = 3.5. При N = 3 ожидаемый выигрыш ≈ 489.8 ₽ > 475 ₽ — это минимальное N для статистически выигрышной игры.