Перед Вами безводная пустыня длиной 50 км, которую нужно пересечь. На каждый километр пути Вы потребляете 1 литр воды. Вы можете нести на себе запас воды не более чем в 10 литров (больше - слишком тяжело).
В отправной точке есть бесконечный источник воды, а вот в самой пустыне источников воды нет. Впрочем, Вы можете складировать воду в пустыне, и она не будет испаряться (считайте, что у вас есть бесконечный запас невесомых пластиковых бутылок).
Какое минимальное количество воды Вам потребуется, чтобы пересечь пустыню?
Решение
Прежде чем перейти к математическим выкладкам, изложим несколько общих соображений.
Во-первых, благодаря возможности устраивать склады воды в пустыне, мы можем пересечь пустыню любого размера. Можно взять и устроить хранилище на расстоянии в 1 км от начала пустыни и накопить в нём 100500 (т.е. невообразимо много) литров воды, сделав запас воды в нём почти бесконечным. Потом всю эту воду переносим на склад на отметке 2 км, потом 3 км и так далее. Мы совершим слишком много лишних рейсов туда-обратно между хранилищами и затратим на них слишком много воды, но пересечём пустыню любой наперёд заданной длины.
Во-вторых, в поисках оптимальной стратегии мы вряд ли будем иметь больше двух промежуточных хранилищ воды одновременно. Возможно, существует оптимальная стратегия, которая требует одновременного наличия трёх и более хранилищ, но ей всегда будет соответствовать стратегия, дающая такой же результат, но использующая не более двух промежуточных складов воды одновременно.
Например, предположим, что нам откуда-то известна оптимальная стратегия, которая требует, чтобы мы устроили промежуточные опорные пункты на расстоянии L1 и L2 от начала пустыни, а потом ушли вперёд и устроили временный склад воды на отметке L3. Мы не можем просто так оставить неиспользованную воду на отметке L1, т.к. она там пропадёт зря, и мы не выполним условие оптимальности. Поэтому мы должны вернуться к ней с отметки L3 и перенести её куда-то ближе, например L2. Но на эти перемещения мы затратим столько же воды, сколько бы затратили, если бы мы сначала в несколько рейсов перенесли всю воду из L1 в L2, а потом бы пошли вперёд к L3.
Теперь мы готовы начать строить оптимальную стратегию. Как это часто бывает в задачах на оптимальность, проще начать с конца.
Глупо было бы прийти к концу пустыни (т.е. к отметке 50 км), принося с собой запас воды, так как эта вода не будет использована и пропадёт зря. С другой стороны, странно выходить в путь, взяв неполный запас воды. Получается, что в последний свой рейс по пустыне мы должны выходить от отметки 40 км, взяв с собой 10 литров воды - ровно столько, сколько требуется, чтобы пройти последние 10 км.
Даже ёжику понятно, что для того, чтобы на 40-м километре образовался склад на 10 литров воды, эту воду туда нужно принести. Принести её прямо от начала пустыни не получится. Значит, нужен склад где-то на расстоянии $40-x$ км от начала пустыни, с которого мы принесём эти 10 литров, затратив что-то на транспортировку.
Мы не сможем принести 10 литров с предыдущего склада за один рейс. Значит, нам понадобится как минимум три дополнительных рейса по пустыне:
1) Забрали 10 литров со склада на отметке $40-x$ км, принесли их в лагерь на 40-м километре, затратив $x$ литров, и выгрузили $10-2x$.
2) С оставшимися $x$ литрами вернулись назад.
3) Забрали 10 литров, потратили $x$ на дорогу и выгрузили $10-x$.
Чтобы в сумме на 40-м километре набралось 10 литров, должно выполняться соотношение$$
(10-2x) + (10-x) = 10
$$Отсюда легко найти, что $x=10/3$. Другими словами, нам нужен промежуточный склад на отметке $40 - \frac{10}{3} = 36\frac{2}{3}$ км, на котором нам нужно накопить 20 литров воды. Из них 10 литров мы потратим на рейсы туда-обратно-туда, а оставшиеся 10 накопим на последний переход.
Дальше рассуждаем аналогично. 20 литров воды не принести даже за два приёма, поэтому с предыдущего склада придётся сделать 3 рейса "туда" и 2 "обратно". Если он расположен на расстоянии $y$ от отметки $36\frac{2}{3}$, то действовать будем так:
1) Загрузили 10 л, потратили $y$ литров, выгрузили $10-2y$ литров на новый склад.
2) Потратили $y$ литров на дорогу назад.
3) Снова забрали 10 литров, потратили $y$, выгрузили $10-2y$.
4) Потратили $y$ литров на дорогу назад.
5) Забрали 10 литров, потратили $y$ на переход, выгрузили $10-y$.
Наша цель - накопить на отметке $36\frac{2}{3}$ км 20 литров. Поэтому уравнение для $y$ выглядит так:$$
(10-2y) + (10-2y) + (10-y) = 20
$$ $$y = \frac{10}{5} = 2$$То есть нам необходимо промежуточное хранилище воды в точке $34\frac{2}{3}$ км, в котором нужно накопить 30 литров. 10 литров будет потрачено на 5 рейсов туда-сюда, а 20 мы накопим на следующем складе.
Рассуждая аналогично, приходим к выводу, что $n$-й склад должен располагаться на расстоянии $(\frac{10}{1} + \frac{10}{3} + \frac{10}{5} + ... + \frac{10}{2n-1})$ км от конца пустыни. На нём нужно накопить $10n$ литров воды, принеся их с предыдущего склада.
Поскольку ряд $1+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}...$ расходится, то рано или поздно мы окажемся достаточно близко к началу пустыни, чтобы принести достаточно воды на первый из промежуточных складов. Запишем это формально.
Обозначим $S(n) = 1 + \frac{1}{3} + \frac{1}{5} + ... + \frac{1}{2n-1}$. Тогда должен найтись номер $N$, такой что $N = max\{n | 10S(n) \le 50\}$. Найдя этот номер $N$, мы построим промежуточный склад на отметке $50-10S(N)$ км и накопим в нём $10N$ литров воды. Для этого потребуeтся, как мы знаем, $N+1$ рейс "туда" и $N$ рейсов "обратно". Ну а дальше каждый следующий склад строим на расстоянии $S(n+1)-S(n)$ от предыдущего, накапливаем на нём $10n$ литров, и так постепенно продвигаемся вперёд.
Всего нам потребуется $(2N+1)(50-10S(N)) + 10N$ литров воды, чтобы пересечь пустыню.
Здесь уже можно написать программу, чтобы посчитать сумму $S(n)$ и номер $N$ на компьютере. Результаты будут такими:
Буду признателен, если кто-то подскажет удобную асимптотику для $S(n)$. Wolfram Alpha выдаёт нечто, недоступное моему разуму.
Обновлено:
Как совершенно правильно заметил Саша Монаков, для $S(n)$ есть удобная асимптотика:$$
S(n) = 1+\frac{1}{3}+\frac{1}{5}+...+\frac{1}{2n-1} = $$ $$
= \left(1 + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{2n-1} + \frac{1}{2n}\right) - \frac{1}{2}\left(1 + \frac{1}{2} + \frac{1}{3}+...+\frac{1}{n}\right) =$$ $$
= H_{2n}-\frac{1}{2}H_n
\approx \ln(2n)+\gamma - \frac{1}{2}\left(\ln n+\gamma\right) =
\frac{\ln n}{2} + \ln2 + \frac{\gamma}{2}
$$Отсюда
$$ N \approx \left\lfloor \frac{1}{4}e^{L/5-\gamma} \right\rfloor$$Здесь $L$ - длина пустыни в километрах, а $\gamma$ - постоянная Эйлера-Маскерони. Эта оценка позволяет получить ответ для 50 км с точностью до третьего знака после запятой.
В отправной точке есть бесконечный источник воды, а вот в самой пустыне источников воды нет. Впрочем, Вы можете складировать воду в пустыне, и она не будет испаряться (считайте, что у вас есть бесконечный запас невесомых пластиковых бутылок).
Какое минимальное количество воды Вам потребуется, чтобы пересечь пустыню?
Решение
Прежде чем перейти к математическим выкладкам, изложим несколько общих соображений.
Во-первых, благодаря возможности устраивать склады воды в пустыне, мы можем пересечь пустыню любого размера. Можно взять и устроить хранилище на расстоянии в 1 км от начала пустыни и накопить в нём 100500 (т.е. невообразимо много) литров воды, сделав запас воды в нём почти бесконечным. Потом всю эту воду переносим на склад на отметке 2 км, потом 3 км и так далее. Мы совершим слишком много лишних рейсов туда-обратно между хранилищами и затратим на них слишком много воды, но пересечём пустыню любой наперёд заданной длины.
Во-вторых, в поисках оптимальной стратегии мы вряд ли будем иметь больше двух промежуточных хранилищ воды одновременно. Возможно, существует оптимальная стратегия, которая требует одновременного наличия трёх и более хранилищ, но ей всегда будет соответствовать стратегия, дающая такой же результат, но использующая не более двух промежуточных складов воды одновременно.
Например, предположим, что нам откуда-то известна оптимальная стратегия, которая требует, чтобы мы устроили промежуточные опорные пункты на расстоянии L1 и L2 от начала пустыни, а потом ушли вперёд и устроили временный склад воды на отметке L3. Мы не можем просто так оставить неиспользованную воду на отметке L1, т.к. она там пропадёт зря, и мы не выполним условие оптимальности. Поэтому мы должны вернуться к ней с отметки L3 и перенести её куда-то ближе, например L2. Но на эти перемещения мы затратим столько же воды, сколько бы затратили, если бы мы сначала в несколько рейсов перенесли всю воду из L1 в L2, а потом бы пошли вперёд к L3.
Теперь мы готовы начать строить оптимальную стратегию. Как это часто бывает в задачах на оптимальность, проще начать с конца.
Глупо было бы прийти к концу пустыни (т.е. к отметке 50 км), принося с собой запас воды, так как эта вода не будет использована и пропадёт зря. С другой стороны, странно выходить в путь, взяв неполный запас воды. Получается, что в последний свой рейс по пустыне мы должны выходить от отметки 40 км, взяв с собой 10 литров воды - ровно столько, сколько требуется, чтобы пройти последние 10 км.
Даже ёжику понятно, что для того, чтобы на 40-м километре образовался склад на 10 литров воды, эту воду туда нужно принести. Принести её прямо от начала пустыни не получится. Значит, нужен склад где-то на расстоянии $40-x$ км от начала пустыни, с которого мы принесём эти 10 литров, затратив что-то на транспортировку.
Мы не сможем принести 10 литров с предыдущего склада за один рейс. Значит, нам понадобится как минимум три дополнительных рейса по пустыне:
1) Забрали 10 литров со склада на отметке $40-x$ км, принесли их в лагерь на 40-м километре, затратив $x$ литров, и выгрузили $10-2x$.
2) С оставшимися $x$ литрами вернулись назад.
3) Забрали 10 литров, потратили $x$ на дорогу и выгрузили $10-x$.
Чтобы в сумме на 40-м километре набралось 10 литров, должно выполняться соотношение$$
(10-2x) + (10-x) = 10
$$Отсюда легко найти, что $x=10/3$. Другими словами, нам нужен промежуточный склад на отметке $40 - \frac{10}{3} = 36\frac{2}{3}$ км, на котором нам нужно накопить 20 литров воды. Из них 10 литров мы потратим на рейсы туда-обратно-туда, а оставшиеся 10 накопим на последний переход.
Дальше рассуждаем аналогично. 20 литров воды не принести даже за два приёма, поэтому с предыдущего склада придётся сделать 3 рейса "туда" и 2 "обратно". Если он расположен на расстоянии $y$ от отметки $36\frac{2}{3}$, то действовать будем так:
1) Загрузили 10 л, потратили $y$ литров, выгрузили $10-2y$ литров на новый склад.
2) Потратили $y$ литров на дорогу назад.
3) Снова забрали 10 литров, потратили $y$, выгрузили $10-2y$.
4) Потратили $y$ литров на дорогу назад.
5) Забрали 10 литров, потратили $y$ на переход, выгрузили $10-y$.
Наша цель - накопить на отметке $36\frac{2}{3}$ км 20 литров. Поэтому уравнение для $y$ выглядит так:$$
(10-2y) + (10-2y) + (10-y) = 20
$$ $$y = \frac{10}{5} = 2$$То есть нам необходимо промежуточное хранилище воды в точке $34\frac{2}{3}$ км, в котором нужно накопить 30 литров. 10 литров будет потрачено на 5 рейсов туда-сюда, а 20 мы накопим на следующем складе.
Рассуждая аналогично, приходим к выводу, что $n$-й склад должен располагаться на расстоянии $(\frac{10}{1} + \frac{10}{3} + \frac{10}{5} + ... + \frac{10}{2n-1})$ км от конца пустыни. На нём нужно накопить $10n$ литров воды, принеся их с предыдущего склада.
Поскольку ряд $1+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}...$ расходится, то рано или поздно мы окажемся достаточно близко к началу пустыни, чтобы принести достаточно воды на первый из промежуточных складов. Запишем это формально.
Обозначим $S(n) = 1 + \frac{1}{3} + \frac{1}{5} + ... + \frac{1}{2n-1}$. Тогда должен найтись номер $N$, такой что $N = max\{n | 10S(n) \le 50\}$. Найдя этот номер $N$, мы построим промежуточный склад на отметке $50-10S(N)$ км и накопим в нём $10N$ литров воды. Для этого потребуeтся, как мы знаем, $N+1$ рейс "туда" и $N$ рейсов "обратно". Ну а дальше каждый следующий склад строим на расстоянии $S(n+1)-S(n)$ от предыдущего, накапливаем на нём $10n$ литров, и так постепенно продвигаемся вперёд.
Всего нам потребуется $(2N+1)(50-10S(N)) + 10N$ литров воды, чтобы пересечь пустыню.
Здесь уже можно написать программу, чтобы посчитать сумму $S(n)$ и номер $N$ на компьютере. Результаты будут такими:
| Ширина пустыни, км | Необходимый объём воды, л |
|---|---|
| 10 | 10 |
| 20 | 76.73 |
| 30 | 566.29 |
| 40 | 4184.22 |
| 50 | 30917.42 |
Буду признателен, если кто-то подскажет удобную асимптотику для $S(n)$. Wolfram Alpha выдаёт нечто, недоступное моему разуму.
Обновлено:
Как совершенно правильно заметил Саша Монаков, для $S(n)$ есть удобная асимптотика:$$
S(n) = 1+\frac{1}{3}+\frac{1}{5}+...+\frac{1}{2n-1} = $$ $$
= \left(1 + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{2n-1} + \frac{1}{2n}\right) - \frac{1}{2}\left(1 + \frac{1}{2} + \frac{1}{3}+...+\frac{1}{n}\right) =$$ $$
= H_{2n}-\frac{1}{2}H_n
\approx \ln(2n)+\gamma - \frac{1}{2}\left(\ln n+\gamma\right) =
\frac{\ln n}{2} + \ln2 + \frac{\gamma}{2}
$$Отсюда
$$ N \approx \left\lfloor \frac{1}{4}e^{L/5-\gamma} \right\rfloor$$Здесь $L$ - длина пустыни в километрах, а $\gamma$ - постоянная Эйлера-Маскерони. Эта оценка позволяет получить ответ для 50 км с точностью до третьего знака после запятой.
S(n) это же просто прореженный гармонический ряд?
ОтветитьУдалитьS(n) = 1 + 1/2 + ... + 1/(2n-1) + 1/(2n) - 1/2(1 + 1/2 + ... + 1/n) = H_{2n} - 1/2 H_n = ln(2n) + y + o(1) - 1/2(ln(n) + y + o(1)) = ln(n)/2 + ln(2) + y/2 + o(1)
(y - постоянная Эйлера-Маскерони)
Ты прав. Ларчик-то просто открывался. Сейчас обновлю пост.
ОтветитьУдалитьнет доказательства оптимальности. склады можно делать и эквидистантными, увеличивая количество рейсов. Кстати, 10 л можно перенести и за два рейса, и за четыре, и за пять, единственно - тройка ближе к числу е
ОтветитьУдалить