Из пункта $A$ в пункт $B$, расстояние между которыми равно $d$ км, должны добраться $n$ велосипедистов, у которых имеется $m$ велосипедов. Каждый может идти пешком со скоростью $u~\text{км/ч}$ или ехать на велосипеде со скоростью $v~\text{км/ч}$. За какое наименьшее время все $n$ велосипедистов смогут попасть из $A$ в $B$? (Время считается по последнему прибывшему. Велосипед можно оставлять на дороге без присмотра.) Рассмотрите частный случай: $m=2$, $n=3$.
Разобьём решение задачи М550 на две части. Вначале, исходя из возможностей движения каждой из «точек системы» (каждого велосипедиста) в отдельности, найдём наименьшее время передвижения всей «системы точек». А затем опишем один из возможных способов движения, реализующих это наименьшее время.
Покажем, что в нашей задаче наименьшее время передвижения
$$
t_{\min}=\dfrac dv\cdot\dfrac mn+\dfrac du\cdot\dfrac{n-m}n,
$$
причём каждый из велосипедистов при таком движении проходит расстояние $d\,\dfrac{n-m}n$ пешком (со скоростью $u$), а оставшееся расстояние $d\,\dfrac mn$ проезжает нa велосипеде (со скоростью $v$), и все велосипедисты добираются из $A$ в $B$ одновременно. Действительно, так как каждый из велосипедистов в общей сложности перемещается на расстояние $d$ (из $A$ в $B$), в итоге все $m$ велосипедов проедут путь $m\cdot d$. Если какой-нибудь из велосипедистов проедет на велосипеде путь, больший $d\,\dfrac mn$, то найдётся велосипедист, который проедет на велосипеде путь $d_1\lt d\,\dfrac mn$. Пешком этот велосипедист пройдёт путь $d-d_1$. Полное время движения этого велосипедиста
$$
t_1=\dfrac{d_1}v+\dfrac{d-d_1}u=\dfrac du+d_1{\left(\dfrac1v-\dfrac1u\right)}.
$$
Так как по условию задачи $u\lt v$, а по предположению $d_1\lt d\,\dfrac mn$, для времени $t_1$ получим
$$
t_1\gt\dfrac du+d\,\dfrac mn{\left(\dfrac1v-\dfrac1u\right)}=t_{\min}.
$$
Очевидно, общее время движения группы $T$ (которое засчитывается по последнему прибывшему) будет удовлетворять условию $T\ge t_1\gt t_{\min}$ . Поэтому движение, при котором какой-нибудь велосипедист проезжает на велосипеде не $d\,\dfrac mn$, не будет «оптимальным».
Укажем теперь, как должны вести себя велосипедисты, чтобы общее время передвижения было равно $t_{\min}$. Это удобно сделать с помощью «столбов».
Будем считать, что по дороге на одинаковых расстояниях друг от друга расставлены $n$ столбов: $K_1$, $K_2$, $\ldots$, $K_n$, причём последний столб — в пункте $B$. Способ передвижения состоит в следующем. $m$ велосипедистов садятся на $m$ велосипедов и проезжают вдоль дороги: первый — до столба $K_1$, второй — до столба $K_2$, $\ldots$, $m$-й — до столба $K_m$. После этого они оставляют велосипеды на дороге (у столбов $K_1$, $\ldots$, $K_m$ соответственно) и дальше идут пешком. При этом первый велосипедист доходит до столба $K_{n-m+1}$, второй — до столба $K_{n-m+2}$, $\ldots$, а $m$-й велосипедист доходит до пункта $B$. $n-m$ велосипедистов, которым не достались велосипеды, идут из пункта $A$ пешком. Они последовательно доходят до столбов $K_1$, $\ldots$, $K_{n-m}$, садятся на оставленные там велосипеды и дальше уже едут — до столбов $K_{m+1}$, $K_{m+2}$, $\ldots$, $K_n$ (т. е. «последний» из этих велосипедистов приезжает в пункт $B$). Велосипедист, вначале доехавший до столба $K_1$, а зaтем дошедший до столба $K_{n-m+1}$, садится на стоящий там велосипед (оставленный велосипедистом из первой или из второй группы) и заканчивает своё движение на велосипеде. Велосипедист, вначале доехавший до столба $K_2$, а затем дошедший до столба $K_{n-m+2}$, садится на велосипед, оставленный велосипедистом, доехавшим до этого столба, и также заканчивает своё путешествие на велосипеде. И т. д.
Велосипедисты, которые вначале шли пешком, а потом ехали на велосипедах, оставляют (кроме последнего из них) свои велосипеды у столбов $K_{m+1}$, $\ldots$, $K_{n-1}$ соответственно и заканчивают своё движение пешком. Идущие пешком велосипедисты, начавшие своё движение на велосипедах, «подбирают» оставленные у соответствующих столбов велосипеды, садятся на них и таким образом заканчивают своё движение.
Рис. 1Рис. 2
На рисунке 1 изображены графики перемещения велосипедистов из $A$ в $B$ для случая $m=7$, $n=11$ (по оси абсцисс отмечается время движения, по оси ординат — координата места нахождения). Красные отрезки отвечают перемещениям на велосипедах, синие — перемещениям пешком. Ha этом рисунке выделены графики перемещения одного из выехавших из $A$ и одного из вышедших из $A$ велосипедистов (ломаные $AC_3D_3B$ и $AA_2B_3B$). Из графика видно, что время перемещения каждого велосипедиста равно $t_{\min}$.
Случай $m=2$, $n=3$ проиллюстрирован на рисунке 2: синим цветом изображён график перемещения первого велосипедиста; красным — второго и чёрным — третьего.
