Авито Middle: оптимальная стратегия на 2N-гранном кубике

Условие

Бросаете кубик с 2N гранями (значения 1..2N равновероятны). После первого броска можно:

1. Забрать сумму $, равную выпавшему числу.
2. Перебросить (второй бросок отклонять нельзя).

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

Решение

Стратегия

Если первый бросок = k, перебрасываем тогда и только тогда, когда k < E[бросок].

E[2N-гранный] = (1 + 2N) / 2 = N + 0.5.

То есть перебрасываем при k ≤ N, оставляем при k ≥ N+1.

Ожидание

Пусть стратегия: «оставить, если k ≥ N+1; иначе перебросить».

E = P(k ≥ N+1) × E[k | k ≥ N+1] + P(k ≤ N) × E[2-й бросок]
  = (N/2N) × ((N+1) + (N+2) + ... + 2N) / N + (N/2N) × (N + 0.5)
  = 1/2 × (3N + 1)/2 + 1/2 × (N + 0.5)
  = (3N + 1)/4 + (N + 0.5)/2
  = (3N + 1 + 2N + 1) / 4
  = (5N + 2) / 4

Проверка для 2N = 6 (стандартный кубик)

N = 3, E = (15 + 2)/4 = 17/4 = 4.25.

Простая arifметика подтверждает: оставлять 4, 5, 6; перебрасывать 1, 2, 3:

E = (4 + 5 + 6)/6 + (3/6)·3.5 = 15/6 + 1.75 = 2.5 + 1.75 = 4.25.

Для 2N = 2 (двусторонний)

N = 1, E = 7/4 = 1.75.

Перебрасывать 1, оставлять 2: 1/2 × 2 + 1/2 × 1.5 = 1 + 0.75 = 1.75.

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

1. На 2N+1-гранном (нечётное N) сравнение становится строгим vs нестрогим. Здесь по условию чётные грани.
2. Если бы можно было перебросить и второй раз — задача рекурсивна, ответ другой.
3. «Стратегия» определяется одним порогом — это потому что бросок i.i.d.

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

Перебрасывайте при k ≤ N (значения ≤ среднего); ожидание прибыли = (5N + 2)/4. Для обычного 6-гранного — 4.25.