Задача о 50-ти мотоциклистах

Есть 50 мотоциклистов. У каждого мотоцикла есть бак объёмом 10 литров. Расход бензина: 1 л / 10 км.

Какое максимальное расстояние может проехать хотя бы один мотоцикл?

Здесь все числа условны. Мотоциклистов может быть не 50, бак может быть другого объёма и расход также другой. Это только лишь параметры, на конкретные значения которых не нужно закладываться. Нужно вывести общую формулу.

Пояснение

Если все мотоциклисты будут ехать до тех пор, пока баки у них не опустеют, то проедут они 100 км. Это очевидно.

Но по условию задачи речь идёт о максимальном расстоянии, которое может проехать один мотоцикл. Это значит, что можно переливать бензин из бака в бак. Мотоциклы, у которых не осталось бензина, прекращают ехать, но дальше едут те, у которых бензин ещё есть.

Вопрос тут, конечно, в том, как оптимизировать распределение бензина в баках, чтобы проехать максимальное расстояние.

И ещё одно условие для любителей формальностей: все мотоциклы едут только своим ходом, не на прицепе и т.п.

Первое решение

Например, если все мотоциклы проедут 50 км, то у каждого останется полбака бензина. Значит, можно слить бензин от одной половины мотоциклов другой половине. Останутся 25 мотоциклов с полным баком, которые могут проехать ещё 50 км. Потом надо повторить операцию слива.

У нас получается последовательность количества мотоциклов: 50, 25, 12, 6, 3, 1, это примерно 300 километров. Учтите, что здесь возникает ситуация, когда мотоциклов нечётное количество и поделить их пополам не выйдет. Поэтому должны быть решения получше.

Стратегия

Все мотоциклы можно рассматривать как один коллективный бак объёмом 500 л.

Коллективный бак тратит на своё перемещение столько топлива, сколько мотоциклов участвует в нём. Т.е. если мотоциклов 50, расход будет 50 литров на 10 км.

Следовательно, оптимальной стратегией будет избавляться от лишних мотоциклов как можно скорее.

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

Как только в одном мотоцикле остаётся столько топлива, чтобы распределить его поровну на все оставшиеся мотоциклы, надо это делать и удалять один мотоцикл.

Решение

Построим логическую последовательность:

1. 50 мотоциклов проезжают расстояние, на которое затрачивается 1/50 бака. При этом у каждого мотоцикла остаётся 49/50 бака. Если бак одного мотоцикла распределить на 49 остальных, получим 49 мотоциклов с полным баком и один с пустым. Он выбывает.
2. 49 мотоциклов проезжают расстояние, на которое затрачивается 1/49 бака. При этом у каждого мотоцикла остаётся 48/49 бака. Если бак одного мотоцикла распределить на 48 остальных, то получим 48 мотоциклов с полным баком и один с пустым. Он выбывает.

Далее легко построить остаток этой последовательности:

N мотоциклов проезжают расстояние, на которое затрачиваются 1/N бака. Это расстояние равно (C / N) / R * D км, где C это вместимость бака, R и D – расход R литров на D км.

Необходимо сложить все расстояния для количества мотоциклов от N до 1. Я сделал это в цикле:

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

Поиграть с параметрами можно здесь:

https://onecompiler.com/php/3z3ajpcbg

Ну а бонус-баллы получат те, кто смогут вывести формулу без цикла :)

Вся подборка задач: