Решение. 50 байкеров (#105)
Ответ: 100 x (1 + 1/2 + … + 1/50) ~= 450 [км]
Решение
Для обобщения положим, что n — количество мотоциклов, x — ёмкость топливного бака в километрах.
Обозначим f(n) то максимальное расстояние, на которое можно уехать на одном мотоцикле, если изначально их было n штук. Из условия задачи мы знаем, что f(1) = x.
1. Ясно, что первые x/n км должны проехать все n мотоциклов. Действительно, пусть мы оставили один мотоцикл раньше, то есть все мотоциклы израсходовали менее 1/n ёмкости своего бака. Тогда n мотоциклов суммарно израсходуют < 1 бака. В этой ситуации бензобак выбранного мотоцикла невозможно опустошить за счёт переливания по бакам оставшихся (n-1) мотоциклов. То есть «пропадёт» часть бензина, на который можно было бы проехать далее.
2. Как только мотоциклы проедут x/n км, ровно 1 бак израсходуется. Следовательно, путём переливания по другим бакам его можно будет опустошить. Для максимального продвижения колонны это переливание нужно сделать именно на отметке x/n, так как суммарный расход бензина в этом случае уменьшится (будет двигаться меньшее количество мотоциклов).
Таким образом, получаем рекуррентное соотношение:
f(n) = f(n — 1) + x/n, где n >= 1 и f(1) = x
Из этого соотношения находим:
f(n) = x (1 + 1/2 + … + 1/n)
В частности, для n = 50, x = 100 [км]
f(50) = 100 (1 + 1/2 + … + 1/50) ~= 450 [км]
Замечание. Ответ выражается через частичную сумму гармонического ряда, который, как известно, растёт как логарифм:
При больших n имеет смысл рассматривать более простую эквивалентную функцию:
Из неё в частности вытекает, насколько неэффективно увеличивать количество мотоциклов для увеличения максимального пути. Например, при n=50 для увеличения пути в 2 раза нужно:
- в 2 раза увеличить ёмкость топливного бака у каждого мотоцикла, или
- в 50 раз увеличить количество байкеров (итого нужно 2500)
