Как далеко вы сможете доставить груз на N грузовиках

У вас есть парк из 50 грузовиков. Каждый из них полностью заправлен и может проехать 100 км. Как далеко с их помощью вы можете доставить определенный груз? Что будет, если в вашем распоряжении N грузовиков?

Не все понимают сразу о чем речь: территориально это место,  где нет никаких заправочных станций. Единственное место, где можно здесь найти горючее – это топливные баки грузовиков. Пересесть из грузовика в гибридный легковой автомобиль Prius нельзя. Бросить грузовик без топлива, где бы это ни случилось, и без водителя – в порядке вещей. И единственное, что здесь важно, – доставить как можно дальше ценный груз.

Топлива хватит, чтобы отправить каждый из 50-ти  грузовиков на расстояние 100 км, то есть  на расстояние 50*100 = 5000 км. Но возможно ли считать 5000 км ответом? Нет, если только у вас нет способа, позволяющего телепортировать топливо из бака одного грузовика в другой. Вспомните, что каждый грузовик полностью заправлен и пока топливо не израсходовано, добавить его нельзя.

Начните с простого шага. Представьте, что у вас не 50 грузовиков, а всего один. Загружайте его, залезайте в кабину и отправляйтесь в путь. Через 100 км путь для вас закончится.

Теперь предположим, что у вас есть два грузовика. Загружаете первый и 100 км  можете ни о чем не думать. Но потом? Сможет ли вам помочь второй грузовик? Нет. Он на расстоянии 100 км от вас.  Ему придется следовать за вами, так что его бак закончится через те же 100 км.

Может быть, первому грузовику следовало бы взять второй на буксир? Когда первый грузовик останется без топлива, можно переложить груз во второй грузовик, бак которого полон, и двигаться дальше. Да, хорошо, еще 100 км.

И насколько далеко в такой сцепке сможет проехать первый грузовик? Вряд ли 100 км. Ему придется тащить вес вдвое больше обычного. Законы физики говорят, что в лучшем случае он проедет только половину прежнего расстояния. В реальной жизни расход топлива на 1 км  пути для более тяжелого транспортного средства повышается более резко, чем вес.

А если посмотреть иначе? Пусть два грузовика отправляются в путь одновременно, каждый сам по себе. Через 50 км баки у каждого будут наполовину пустые, но один бак вы можете заполнить доверху. Перелейте топливо из одного бака в другой. Оставьте пустой грузовик и проезжайте на заполненном доверху баке еще 100 км. Пройденное суммарное расстояние составит 150 км. В отличие от буксировки, здесь нет теоретического ограничения, и такой подход в полной мере может быть использован на практике.

При трех грузовиках вариант с буксировкой ставится под сомнение,  а вот идея с переливанием топлива по-прежнему работает отлично. Отправьте сразу три грузовика. Пусть они остановятся на трети пути расстояния в 100 км, то есть после того, как проедут примерно 33.33 км. В каждом баке осталось 2/3 топлива. Перелейте топливо из одного грузовика в баки двух других – они снова полны доверху. Затем отправьте в путь эти два грузовика. Мы уже знаем, что максимальное расстояние для них составит 150 км. Если добавить к этому пути первые 33.33 км, то общее расстояние будет чуть больше 183 км.

Закономерность становится очевидной. Один грузовик может проехать 100 км. Второй грузовик позволяет увеличить общий путь на 100/2 = 50 км. Третий грузовик увеличивает общий путь на 100/3 км. Четвертый грузовик добавляет 100/4 км. Для N грузовиков общее расстояние составит:  100*(1/1+1/2+1/3+1/4+1/5+…1/N)

Дробная часть в этом случае известна как гармонический ряд. Сумму членов гармонического ряда можно легко рассчитать. Если N равно 50, сумма этой прогрессии 4.499… Умножьте ее на 100 км, и вы увидите, что, имея в своем распоряжении 50 грузовиков, вы сможете доставить груз на 449.9 км.

При увеличении N сумма возрастает. При достаточном количестве грузовиков вы можете отвезти груз куда захотите. Однако с увеличением N расстояние увеличивается очень медленно, а эффективность использования энергии становится очень низкой. Тысячный грузовик добавит лишь 1/100 км к общему расстоянию перевозки груза (но при этом загрязнит атмосферу выбросами диоксида углерода точно так же, как и все остальные машины). Миллионный грузовик увеличит весь путь всего на несколько сантиметров.

Приведенный выше ответ имеет право на жизнь. Есть ли другой? Есть, если можно перевозить топливо, и если груз не очень тяжелый.

В вопросе говорится о грузовиках, которые предназначены для перевозок крупных и тяжелых грузов. Предположим, у вас грузовики марки  GMC или Ford. Собственный вес такого полностью заправленного и оборудованного автомобиля – порядка 2250 кг. Он сконструирован так, чтобы безопасно перевозить такой тяжелый груз, если только вы не транспортируете упакованный арахис или сахарную «вату».

Бак грузовика вмещает около 30 галлонов топлива, этот объем эквивалентен примерно 120 литрам.

Ключевой вопрос: весит ли топливо меньше, чем сам грузовик? Меньше, поскольку 200/5000 составляет 1/25 веса грузовика без груза, но заправленного.

Было бы глупо буксировать или везти грузовик весом 2250 кг, когда вас интересует только 120 литров топлива в его баке. Не лучше ли везти топливо в кузове грузовика вместе с доставляемым грузом. (Может быть, вы сможете найти емкости для топлива или снять топливные баки с других грузовиков и использовать их как такие емкости.) Грузовик может перевезти топливо, эквивалентное полной заправке 25 грузовиков при условии, что полезный груз весит немного.

Это означает, что один такой грузовик может перевезти половину топлива парка, состоящего из 50 машин. Он может проехать 25*100 или 2500 км. Однако, вряд ли он это сделает, потому что перевозимый груз сократит это расстояние. Тем не менее, будем считать, что такой вариант позволит ему проехать порядка 1500 км. Это более чем в три раза превышает 450 км при варианте перелива топлива и требует всего лишь одного грузовика и одного водителя.

Разбор взят из книжки «Are You Smart Enough to Work at Google?».