WikiSort.ru - Не сортированное

Задача исследования

Стратегия, которая помогает увеличить расстояние, которое может проехать джип в задаче исследования пустыни:

• Джип делает ${\displaystyle n}$ поездок, в начале каждой поездки он имеет полный запас топлива. Полный бак обозначим как 100 % или 1, соответствующую дистанцию — 1.
• При первой поездке джип едет на расстояние ${\displaystyle {\frac {1}{2n}}}$ и оставляет там ${\displaystyle {\frac {n-1}{n}}}$ часть топлива, после этого запас топлива станет равным ${\displaystyle {\frac {1}{2n}}}$ , чего достаточно для возвращения на базу.
• При каждой следующей поездке джип, доехав до первой остановки, израсходует ${\displaystyle {\frac {1}{2n}}}$ часть топлива и забирает ${\displaystyle {\frac {1}{2n}}}$ из бочки, таким образом, доехав до первой остановки, джип имеет полный запас топлива, вследствие чего он может продолжать исследование. На обратном пути джип опять забирает ${\displaystyle {\frac {1}{2n}}}$ из бочки, чего достаточно для возвращения на базу.
• Во время второй поездки джип едет к первой остановке и дозаправляется, после чего едет на расстояние 1/(2n − 2) и оставляет на второй остановке (n-2)/(n-1) топлива, после чего запас топлива равен ${\displaystyle {\frac {1}{2n-2}}}$ , чего достаточно, чтобы вернутся к первой стоянке, дозаправиться и вернуться на базу.
• При каждой следующей поездке джип дозаправляется ${\displaystyle {\frac {1}{2n-2}}}$ на прямом пути и таким же количеством на обратном, по аналогии с первой остановкой.
• Джип продолжает исследование, при каждой k-й поездке он создает новую остановку с бочкой топлива на расстоянии ${\displaystyle {\frac {1}{2n-2k+2}}}$ от предыдущей остановки и оставляет там ${\displaystyle {\frac {n-k}{n-k+1}}}$ количество топлива. Для каждой с n — k поездок джип дозаправляется на ${\displaystyle {\frac {1}{2n-2k+2}}}$ количество топлива от k-й бочки на прямом пути и таким-же количеством на обратном пути, чего достаточно, чтобы доехать до стоянки k − 1 и вернуться на базу.

Когда джип едет последний раз, имеется n − 1 бочек с топливом. Последняя бочка имеет 1/2 количества топлива, предпоследняя — 1/3 и так далее до первой бочки, в которой 1/n количества топлива. Имея в виду, что на выезде из базы джип имеет полный запас топлива, в сумме он может преодолеть расстояние

${\displaystyle 1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{n}}=\sum _{k=1}^{n}{\frac {1}{k}}}$

Задача пересечения

Расстояние, пройденное джипом в последней поездке это n-е гармоническое число — H_n. Так как гармоническое число может расти бесконечно, то и длина пути, которую может пройти джип, также может быть бесконечной при условии наличия достаточного количества топлива на базе, но при этом количество бочек для дозаправки будет расти экспоненциально.

Решение задачи пересечения пустыни аналогично решению задачи исследования пустыни, за исключением того, что при последней поездке нет необходимости дозаправляться на обратном пути. На k-й поездке джип оставляет k-ю бочку на дистанции 1/(2n − 2k + 1) от предыдущей остановки и оставляет (2n − 2k − 1)/(2n − 2k + 1) количества топлива. При каждой из последующих n − k − 1 поездок джип дозаправляется 1/(2n − 2k + 1) количеством топлива на k-й остановке на прямом и обратном пути.

Когда джип едет в последний раз, имеется n − 1 бочек с топливом. Последняя имеет 1/3 часть топлива, предпоследняя — 1/5 и так далее, ближайшая имеет 1/(2n − 1) количества топлива. В этом случае джип может проехать

${\displaystyle 1+{\frac {1}{3}}+{\frac {1}{5}}+\cdots +{\frac {1}{2n-1}}=\sum _{k=1}^{n}{\frac {1}{2k-1}}=H_{2n-1}-{\frac {1}{2}}H_{n-1}}$

Отметим, что

${\displaystyle \sum _{k=1}^{n}{\frac {1}{2k-1}}>\sum _{k=1}^{n}{\frac {1}{2k}}={\frac {1}{2}}H_{n}}$

то есть теоретически возможно преодолеть пустыню любого размера, имея достаточно топлива на базе. Как и в предыдущей задаче, требуемое для этого количество топлива растет экспоненциально.