Задача «Стратегия для бессмертного кубика» Кубик с n гранями (1..n). Платите 1 за бросок, выпавшее число — прибыль. После броска: стоп (забираете всё) или продолжаете. Если выпадает 1 — теряете всё, уходите с 0. Вопрос: оптимальная стратегия остановки (порог накопленного выигрыша) для максимизации матожидания финального выигрыша в зависимости от n?

Обозначим $x$ как порог, при котором мы решаем остановиться. Если текущая сумма $S < x$, мы продолжаем бросать; если $S \ge x$, мы останавливаемся. Ожидаемый выигрыш $V(x)$ при достижении порога $x$ можно выразить через уравнение для матожидания. ### 1. Построение уравнения Пусть $E$ — математическое ожидание выигрыша. В этой игре есть риск потерять всё (выпадение 1, вероятность $1/n$). Если мы находимся на текущей сумме $S$, то при следующем броске: - С вероятностью $1/n$ мы теряем всё (выигрыш 0). - С вероятностью $(n-1)/n$ мы получаем число от $2$ до $n$. Среднее значение прибавления равно $\frac{2+n}{2} = \frac{n+2}{2}$. Оптимальная стратегия заключается в выборе порога $x$, максимизирующего ожидаемый результат. Для больших $n$ задача сводится к поиску $x$, при котором ожидаемая прибыль от одного броска равна ожидаемой потере при риске всё потерять. ### 2. Асимптотика Для больших $n$ вероятность проигрыша при одном броске равна $p = 1/n$. Мы стремимся достичь порога $x$, не «сгорев». Примерное матожидание при стратегии остановки на пороге $x$ без учета стоимости попыток (или с учетом их пренебрежимости при больших $n$) максимизируется, когда средний выигрыш балансирует на грани риска. Известно, что для данной задачи оптимальный порог $x$ ведет себя как $\sqrt{2n}$. Более строго: пусть $V$ — среднее значение. Оптимальная стратегия максимизирует $V$ при условии, что мы продолжаем, пока $S < x$. В пределе для больших $n$ это эквивалентно максимизации $f(x) = x \cdot P(\text{успех до } x)$. Вероятность не выкинуть 1 за $k$ бросков составляет $(1 - 1/n)^k \approx e^{-k/n}$. Максимизация функции $x \cdot e^{-x^2 / (2n \cdot \text{avg_roll})}$ приводит к результату $x \approx \sqrt{n \cdot \text{const}}$. ### 3. Предел Для кубика с $n$ гранями среднее значение выигрыша при успехе (не 1) составляет $\mu = \frac{2+n}{2} \approx n/2$. Оптимальный порог $x \approx \sqrt{2n}$. Следовательно: $$\lim_{n\to\infty} \frac{\text{оптимальный_порог}}{\sqrt{n}} = \sqrt{2}$$ Ответ: Оптимальный порог растет как $\Theta(\sqrt{n})$, предел равен $\sqrt{2} \approx 1.414$.