Яблоки Шахерезады
Через пустыню проходит единственная дорога, на которой расположены $n > 100$ поселений. Каждую неделю Синбад ведет караван, который отвозит в поселения яблоки и продает их. Он посещает деревни по очереди и в каждой назначает свою цену (он не обязательно посещает все поселения). Кроме Синбада ни у кого не хватает смелости, чтобы пойти в пустыню. Спрос на яблоки в каждом из поселений составляет $q=10-p$. В пустыне очень жарко, поэтому после первого поселения яблоки начинают гнить. Во время перехода между каждыми двумя поселениями половина остатка яблок портится и пропадает. Пусть Синбад везет груз яблок в 10 кг. Сколько яблок он продаст в каждом поселении и какие цены он назначит, если он максимизирует выручку?
Решение
Задача формулируется как $\sum_{i=1}^N (10-q_i)q_i\to \max $ при $\sum_{i=1}^N 2^{i-1}q_i=10$ и $q_i\geq 0$. Зафиксируем все $q_i$ кроме двух соседних, и прооптимизируем выбор между ними. Тогда если $q_i+2q_{i+1}\leq 2.5$, то $q_{i+1}=0$. Но тогда $q_4=q_5=\ldots=0$. Тогда продаём в трёх деревнях, для них получаем $q_1=\frac{80}{21},q_2=\frac{55}{21},q_3=\frac{5}{21}$