Досуги

После нескольких экскурсов по головоломкам я приглашаю читателей в другое путешествие - поездку по пустыне. Задача, о которой пойдет речь, в общем-то, хорошо известна специалистам. Она считается вполне серьезной, и ее исчерпывающего решения не найдено до сих пор, хотя шансы есть у всех. В англоязычных источниках она обычно приводится в следующем виде:

Небольшой пикап находится в пустыне около склада горючего, содержащего N полных бочек бензина вместимостью по 50 галлонов каждая. (Для справки: один галлон в США примерно равен 3,78 литра, а в Великобритании несколько больше - 4,55 литра.) Бак пикапа, который сейчас пуст, вмещает 10 галлонов, при этом одного галлона бензина хватает на 10 миль пути. Пикап может перевозить только одну бочку горючего (пустую или полную).

Спрашивается, как далеко можно уехать от начальной точки?

Обсуждение

Ясно, что если бочка одна, то ее хватит на 500 миль пути. А что, если бочек две (иначе говоря, есть 100 галлонов топлива)? В этом случае правильной стратегией будет такая:

1) сначала отвезти одну бочку на 100 миль, оставить ее там, залить полный бак и вернуться обратно;

2) погрузить вторую бочку и довезти ее до первой;

3) отвезти первую бочку еще на какое-то расстояние и снова вернуться ко второй бочке;

4) погрузить вторую бочку, доехать до оставленной первой (в этот момент должно остаться топлива как раз на то, чтобы заполнить и бочку, и бак);

5) отправиться дальше - с полным запасом топлива можно проехать еще 600 миль.

При этом предполагается, что бензин нельзя оставлять просто на дороге вне бочек, а никаких дополнительных емкостей тоже нет.

Несложный подсчет показывает, что "какое-то расстояние" равно 100/3=33,33 мили, при этом на этапах 1) и 2) мы истратим 30 галлонов, а на этапах 3) и 4) еще 10 галлонов. Соответственно, на этапе 5) останутся как раз необходимые нам 60 галлонов (50 в бочке и 10 в баке). Всего, таким образом, можно проехать 100+100/3+600=733,33 мили.

Задача 1

Какое расстояние можно проехать, имея вначале 3 бочки (150 галлонов) бензина?

Задача 2

А четыре бочки (200 галлонов)?

Задача 3

А теперь попробуйте догадаться, какой может быть общая формула для расстояния, которое может пройти пикап, если вначале есть N бочек.

Решения задач 1-3

1. Сначала все три бочки надо перевезти на 60 миль (это требует пяти поездок туда/обратно, и на эти поездки уйдет 5х6=30 галлонов).

Потом две из трех бочек нужно два раза перевезти на 100 миль вперед (еще шесть поездок, 6х10=60 галлонов). Наконец, с запасом 60 галлонов пикап оказывается в 260 милях от точки старта, после чего делает финишный рывок на 600 миль.

2. Если идея решения предыдущей задачи понятна, то эта задача тоже не должна вызвать затруднений. Заметим, что перевозка X бочек всегда требует (2X-1) поездок, при этом для перевозки их на расстояние 10хL миль уйдет (2X-1)хL галлонов бензина. Сначала все 4 бочки надо перевезти на расстояние 200/7 (20 галлонов). Потом три бочки перевозятся в общей сложности на 120 миль вперед (еще 5 поездок, 60 галлонов), для дальнейшей перевозки оставляются уже только две бочки - их мы отвозим еще на 200 миль (снова 60 галлонов). Наконец, последние 60 галлонов снова позволяют проделать 600-мильный финишный участок. Постарайтесь понять, почему именно такое решение будет наилучшим.

3. Само собой напрашивается следующее предположение: на каждый этап, кроме самого первого, в оптимальном решении уходит ровно 60 галлонов бензина. Таких этапов ровно N-1, а на первом этапе надо израсходовать весь остальной бензин.

Например, при N=5 для первого этапа должно остаться 250-4х60=10 галлонов бензина, поэтому на этом этапе удастся проехать расстояние 100/9=11,11. А всего при этом удастся проехать расстояние (600/7 + 600/5 + 600/3 + 600/1) + 100/9.

Задача 4 (первый сюрприз)

Сразу скажу, что предположение, сделанное в решении третьей задачи, верно для N=5 и N=6, но неверно для всех больших значений N. Легко понять почему: ведь уже при N=7 вначале имеется не 6х60 галлонов, а всего лишь 7х50=350. Какой же все-таки будет лучший результат для N=7?

И вот тут, оказывается, мы уже вплотную подошли к вопросам, на которые точных и исчерпывающих ответов не знает пока никто. Занимательная задачка о пикапе, такая простая с виду, вызвала лет десять назад целую волну серьезных математических статей. Причем многие из авторов искренне считали, что задача ими уже решена. А на самом деле они всего лишь продвигали пикапчик немного дальше…

Ответ к задаче 4

Для 7 бочек (350 галлонов), по-видимому, лучшей является такая последовательность действий:

1. Перевезти 6 бочек на 500/11 (50 галлонов).

2. Перевезти 5 бочек на 600/9 (60 галлонов).

3. Перевезти 4 бочки на 600/7 (60 галлонов).

4. Перевезти 3 бочки на 600/5 (60 галлонов).

5. Перевезти 2 бочки на 600/3 (60 галлонов).

6. Проехать с 1 бочкой 600/1 (60 галлонов).

Итого: 500/11 + 600/9 + 600/7 + 600/5 + 600/3 + 600/1 = 1117,83 мили.

Теперь может показаться, что необходимая поправка к предположению уже найдена: на нескольких первых этапах надо перевозить не все бочки, а на одну бочку меньше (здесь - шесть вместо семи). При этом на каждый из этих этапов вроде бы надо расходовать всего 50 галлонов. Тогда на последние 5 этапов останется ровно 300 галлонов - как раз по 60 на каждый этап. Однако и здесь не все так гладко.

Задача 5 (второй сюрприз)

При N=8 (400 галлонов) решение задачи о пикапе, основанное на описанном только что алгоритме, позволяет проехать 1156,30 мили. А на самом деле существует лучший способ, при котором удается покрыть расстояние 1157,23 мили - почти на целую милю больше.

Попробуйте отыскать этот способ самостоятельно, не заглядывая в ответ.

Ответ к задаче 5

1. Перевезти 7 бочек на 100/3 (43,33 галлона).

2. Перевезти 6 бочек на 1700/33 (56,66 галлона).

Таким образом, вместо расстояния 500/13 + 500/11 = 83,91 мили на этих двух этапах 6 бочек перевезены на 100/3 + 1700/33 = 84,84 мили.

Вот и выигрыш в дистанции! Ну а все следующие этапы требуют по 60 галлонов бензина в обоих вариантах решения.

Послесловие

Мне так и не удалось найти в Интернете каких-либо общих формул для решения задачи о пикапе. Но странно не это. Очень часто бывает, что, когда чистые математики заходят в тупик, на выручку им приходят программисты, использующие вместо точных формул всевозможные методы оптимизации перебора вариантов - например, динамическое программирование. К сожалению, в этой задаче такой взаимопомощи пока не произошло. Даже непонятно почему, ведь задача имеет самое непосредственное отношение к планированию процессов, а эта отрасль софта ныне бурно развивается.

Возможно, все дело в том, что интересы "чистых программистов" лежат далеко от занимательных задач? Ну а поскольку читатели "Компьютерры" довольно часто просят меня давать побольше упражнений для любителей программировать, я это делаю с удовольствием и всегда надеюсь, что кто-нибудь преуспеет в их решении.

У меня появилась своя страничка в Интернете: http://come.to/knop.

Приходите в гости!