Kvant Math Problem 550

Verified: no
Verdicts: SKIP + SKIP
Solve time: 9m40s
Source on kvant.digital

Problem

From point $A$ to point $B$, which are $d$ km apart, $n$ cyclists must travel. They have $m$ bicycles available. Each person can walk at a speed of $u~\text{км/ч}$ or ride a bicycle at a speed of $v~\text{км/ч}$. What is the minimum time in which all $n$ cyclists can get from $A$ to $B$? (The time is measured by the arrival of the last person. A bicycle may be left unattended on the road.) Consider the special case: $m=2$, $n=3$.

S. S. Krotov

Exploration

Let the optimal finishing time be $T$. Every person must cover distance $d$. Walking contributes distance at rate $u$, cycling contributes distance at rate $v$.

A first guess is that the bicycles should never travel backward. Since bicycles may be left on the road, any backward transportation wastes bicycle time that could have been used to move somebody forward. The optimal motion should consist entirely of forward movement.

Let $r_i$ be the total time during which the $i$-th person rides a bicycle. Then his travelled distance equals

$$u(T-r_i)+vr_i=uT+(v-u)r_i.$$

Since he reaches $B$,

$$uT+(v-u)r_i=d.$$

Thus every person must have the same riding time

$$r=\frac{d-uT}{v-u}.$$

This is already a strong restriction. The three persons are symmetric in any schedule achieving finishing time $T$.

The two bicycles can be used by at most two riders simultaneously. Hence the total bicycle riding time available during the interval $[0,T]$ is at most $2T$. Since there are three people and each needs riding time $r$,

$$3r\le 2T.$$

Substituting the expression for $r$ gives a lower bound for $T$.

The crucial point is whether this lower bound is attainable. If equality holds, then $3r=2T$. This means the bicycles are occupied during the whole interval $[0,T]$ and every cyclist receives exactly riding time $r$.

A natural schedule is periodic. At every moment exactly two people ride and one walks. During one third of the total time each person is the walker, during two thirds he is a rider. Then each person rides for

$$r=\frac{2T}{3}.$$

Combining this with the distance condition yields a candidate value for $T$.

The step most likely to hide an error is the passage from the inequality $3r\le2T$ to an actual schedule attaining equality. One must verify that the bicycles can indeed be transferred among the three travellers without any idle bicycle time.

Problem Understanding

Three people must travel from $A$ to $B$, a distance $d$. They possess two bicycles. A person walks at speed $u$ and rides at speed $v$, where $v>u$. Bicycles may be abandoned and picked up later. We seek the smallest possible arrival time of the last traveller.

This is a Type C problem. We must determine the minimum possible time and prove that no smaller time can be achieved.

The core difficulty is converting the global limitation of only two bicycles into a sharp lower bound on the completion time and then constructing a schedule that reaches that bound.

The answer should be

$$T_{\min}=\frac{3d}{u+2v}.$$

The reason is that at any moment the total transport capacity equals the sum of the speeds of the three people currently moving. If two ride and one walks, the aggregate speed is $u+2v$. Sharing the bicycles perfectly among the three travellers should allow every person to benefit equally from this total capacity.

Proof Architecture

The first lemma states that if all three travellers finish at time $T$, then each traveller must spend exactly

$$r=\frac{d-uT}{v-u}$$

hours riding.

The second lemma states that the total bicycle riding time of all travellers does not exceed $2T$, because only two bicycles exist.

Combining the first two lemmas yields

$$3r\le2T,$$

which gives the lower bound

$$T\ge\frac{3d}{u+2v}.$$

The final lemma constructs a schedule with completion time exactly $\frac{3d}{u+2v}$ by rotating the bicycles among the three travellers so that at every moment two ride and one walks.

The most delicate point is the construction attaining equality, because it must ensure that each traveller receives exactly $\frac{2T}{3}$ hours of riding while the bicycles are never idle.

Solution

Let $T$ be the time at which the last traveller reaches $B$.

Consider any traveller. Suppose he rides a bicycle for a total time $r$ and walks during the remaining time $T-r$. Since his walking speed is $u$ and his cycling speed is $v$, the total distance travelled by him equals

$$u(T-r)+vr.$$

Since he reaches $B$,

$$u(T-r)+vr=d.$$

Rearranging,

$$uT+(v-u)r=d,$$

hence

$$r=\frac{d-uT}{v-u}.$$

This formula depends only on $T$, not on the traveller. Therefore every traveller must accumulate exactly the same total riding time.

Now sum the riding times of all three travellers. Since there are only two bicycles, at any instant at most two people can ride. During the interval of length $T$, the total amount of bicycle riding time available is at most

$$2T.$$

Since each of the three travellers must ride for time $r$,

$$3r\le2T.$$

Substituting the expression for $r$,

$$3\frac{d-uT}{v-u}\le2T.$$

Multiplying by $v-u$ gives

$$3d-3uT\le2vT-2uT.$$

Hence

$$3d\le(u+2v)T,$$

so every feasible schedule satisfies

$$T\ge\frac{3d}{u+2v}.$$

This proves the required lower bound.

It remains to show that the bound can be attained.

Set

$$T=\frac{3d}{u+2v}.$$

Then

$$r=\frac{d-uT}{v-u} =\frac{d-\frac{3ud}{u+2v}}{v-u} =\frac{2d}{u+2v} =\frac{2T}{3}.$$

Divide the interval $[0,T]$ into three equal parts of length $T/3$.

During the first third, travellers $1$ and $2$ ride while traveller $3$ walks.

During the second third, travellers $2$ and $3$ ride while traveller $1$ walks.

During the final third, travellers $3$ and $1$ ride while traveller $2$ walks.

At the transition moments, each rider leaves his bicycle for the designated next rider. Since bicycles may be left unattended, these transfers are permitted.

Each traveller walks during exactly one of the three intervals, hence for total time

$$\frac{T}{3},$$

and rides during the other two intervals, hence for total time

$$\frac{2T}{3}=r.$$

Consequently each traveller covers distance

$$u\frac{T}{3}+v\frac{2T}{3} =\frac{u+2v}{3}T =d.$$

Thus all three travellers reach $B$ exactly at time $T$.

The lower bound is attained, so the minimum possible completion time is

$$\boxed{\frac{3d}{u+2v}}.$$

Equality holds when the bicycles are used continuously and are rotated among the three travellers so that each traveller rides for two thirds of the total time.

Verification of Key Steps

The first delicate step is the formula for the riding time. Starting from distance balance,

$$u(T-r)+vr=d,$$

one obtains

$$uT+(v-u)r=d.$$

The coefficient of $r$ is $v-u$, not $v$ and not $u$. An algebraic mistake here changes the entire optimization.

The second delicate step is the inequality $3r\le2T$. The quantity $3r$ is the sum of all riding times, not the elapsed time. Since two bicycles may be ridden simultaneously, the available riding resource over time $T$ equals $2T$. Replacing $2T$ by $T$ would incorrectly treat the bicycles as a single shared object.

The third delicate step is the attainment of equality. The condition $3r=2T$ requires every bicycle to be occupied at every instant. In the proposed schedule, exactly two travellers ride throughout each third of the interval. Hence the total riding time supplied is

$$2\cdot\frac{T}{3} + 2\cdot\frac{T}{3} + 2\cdot\frac{T}{3} = 2T,$$

which matches the theoretical maximum. No bicycle time is lost.

Alternative Approaches

A different approach uses average speed. Let $R$ be the sum of the distances travelled by the three people. Since each must travel distance $d$,

$$R=3d.$$

At any instant the total rate at which this sum can increase is at most $u+2v$, because at most two people can ride while the third walks. Therefore after time $T$,

$$3d=R\le(u+2v)T,$$

which immediately yields

$$T\ge\frac{3d}{u+2v}.$$

To attain equality, one again rotates the bicycles so that at every moment two people ride and one walks. Then the total rate of increase of $R$ is constantly $u+2v$, and after time $\frac{3d}{u+2v}$ each traveller has accumulated exactly distance $d$.

The main proof is preferable because it explains not only the lower bound but also the precise structure of every optimal schedule: each traveller must ride for exactly two thirds of the total time.