Стратегия простая: надо продолжать тянуть шары до тех пор, пока матожидание выигрыша при перевытягиваниях больше, чем номинал вытянутого шара. Осталось научиться считать такие матожидания.
Будем рассматривать ситуацию, в которой в мешке осталось n шаров с номиналами a1, a2, ..., an, и k попыток вытянуть шар.
k = 1: всё очевидно, матожидание выигрыша просто среднее арифметическое (a1 + a2 + ... + an)/n.
k = 2: пусть выпало некоторое as. В соответствии с выбранной стратегией если as не меньше, чем среднее арифметическое оставшихся в мешке шаров (случай k = 1), то надо остановиться, иначе перевытянуть шар. Каждый шар можно вытянуть с равной вероятностью 1/n, поэтому матожидание числа очков при двух вытягиваниях равно
Заметим, что условие перевытягивания можно переписать так:
k = 3, тут уже матожидание считать не нужно, а надо сравнивать числа с матожиданием при перевыборе. Заметим, что с ростом номинала вытянутого шара матожидание количества очков при перевыборе убывает, так что стратегия на первом шаге имеет простой вид "если выпал шар с номиналом не меньше x, оставляем, иначе перевытягиваем", нужно только найти x. Заметим, что если первым вытянут шар 14, то матожидание при перевытягиваниях равно 14 5/36, а если 16, то 13 7/9. Поэтому стратегия может звучать так:
Если первым выпали шары 16, 18 или 20, не менять выбор, иначе перевытягивать. Если при втором выборе выпал шар, номинал которого не больше среднего арифметического оставшихся в мешке шаров, то перевытянуть ещё раз, иначе оставить.
Выписываем явно:
– Первый шар 12 или меньше: перевытянуть. Второй шар 12 или меньше: перевытянуть.
– Первый шар 14: перевытянуть. Второй шар 10 или меньше: перевытянуть.
– Первый шар 16 или больше: оставить.