Kvant Math Problem 343

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m21s
Source on kvant.digital

Problem

In a certain country, the cities are connected by roads. The length of any road is less than $500~\text{км}$, and it is possible to travel from any city to any other city via roads totaling less than $500~\text{км}$. When a single road was closed for repairs, it turned out that it was still possible to travel between any pair of cities using the remaining roads. Prove that this can be done using no more than $1500~\text{км}$.

S. L. Eliseev

Exploration

Model the country by a connected graph. Cities are vertices, roads are edges, and the length of each edge is less than $500$.

The condition that any two cities can be connected by roads of total length less than $500$ means that for every pair of vertices $u,v$, there exists a $u$-$v$ path whose total length is less than $500$.

A road $e$ is closed. After removing $e$, the graph remains connected. We must show that in the new graph any two cities can still be connected by a route of length at most $1500$.

Take arbitrary cities $A$ and $B$. Before the closure there existed an $A$-$B$ path $P$ of length less than $500$.

If $P$ does not use the closed road $e$, nothing needs to be done. The difficulty arises when $P$ uses $e$.

Write $e=XY$. Since removing $e$ leaves the graph connected, there is a path $Q$ from $X$ to $Y$ avoiding $e$.

The original condition applied to the pair $X,Y$ gives a path from $X$ to $Y$ of length less than $500$. Because every road has positive length, any path containing $e$ has length at least the length of $e$, so after deleting $e$ there must still exist an $X$-$Y$ path of length less than $500$. Indeed, if every $X$-$Y$ path of length less than $500$ used $e$, then removing $e$ would destroy all such short paths; but connectivity supplies another path. The question is whether its length can be bounded by $500$.

A better idea is to apply the hypothesis directly after splitting the original path $P$. Let $P$ consist of a segment from $A$ to $X$, then $e$, then a segment from $Y$ to $B$. The total length of $P$ is less than $500$, hence each of those two segments has length less than $500$.

For the pair $X,Y$, the hypothesis gives some path $R$ of length less than $500$. If $R$ avoids $e$, we can replace $e$ by $R$, obtaining a route from $A$ to $B$ of length less than $1500$.

What if every short $X$-$Y$ path uses $e$? Then take such a path $R$. Removing $e$ from $R$ leaves an $X$-$Y$ walk whose remaining part has length less than $500$, because the deleted edge had positive length. That remaining part avoids $e$ and still connects $X$ to $Y$. This is the crucial observation.

Then the new route from $A$ to $B$ consists of the initial segment of $P$, this modified $X$-$Y$ route, and the final segment of $P$. Its length is less than $500+500+500=1500$.

The delicate point is proving the existence of an $X$-$Y$ path avoiding $e$ and shorter than $500$.

Problem Understanding

We are given a connected road network. Every road has length less than $500$ km. Moreover, for any two cities there exists a route of total length less than $500$ km connecting them.

One road $e$ is closed. The remaining network is still connected. We must prove that after this closure, any two cities can still be connected by a route whose total length does not exceed $1500$ km.

This is a Type B problem. We must prove the stated bound.

The core difficulty is to exploit the strong original condition, namely that every pair of cities was connected by a route shorter than $500$ km, and convert it into a uniform bound after one road is removed.

Proof Architecture

For arbitrary cities $A$ and $B$, choose an original $A$-$B$ path $P$ of length less than $500$.

If $P$ avoids the removed road $e$, then the same path remains available and already has length less than $500$.

Assume $P$ uses $e=XY$ exactly once; then $P$ decomposes into an $A$-$X$ segment, the edge $XY$, and a $Y$-$B$ segment, and each outer segment has length less than $500$ because their sum is part of a path shorter than $500$.

There exists an $X$-$Y$ path $R$ of length less than $500$ by the original hypothesis.

If $R$ avoids $e$, it can replace $e$ directly.

If $R$ contains $e$, then deleting the occurrence of $e$ from $R$ leaves an $X$-$Y$ path avoiding $e$ whose length is still less than $500$.

The hardest point is the last lemma, because one must justify carefully that removing the edge $e$ from a short $X$-$Y$ path still yields an $X$-$Y$ connection.

Solution

Let the closed road be $e=XY$. Consider any two cities $A$ and $B$.

By the hypothesis of the problem, before the closure there existed a route from $A$ to $B$ whose total length was less than $500$ km. Fix such a route and denote it by $P$.

If $P$ does not contain the road $e$, then $P$ is still available after the closure. Its length is less than $500$ km, hence certainly less than $1500$ km. Thus only the case when $P$ contains $e$ requires consideration.

Since the length of $P$ is less than $500$ km and every road has positive length, the route $P$ cannot traverse the road $e$ more than once. Write

$$P=P_1\cup e\cup P_2,$$

where $P_1$ is the part from $A$ to $X$ and $P_2$ is the part from $Y$ to $B$.

The lengths of $P_1$ and $P_2$ are each less than $500$ km, because both are subpaths of a path whose total length is less than $500$ km.

Apply the original hypothesis to the pair of cities $X$ and $Y$. There exists an $X$-$Y$ path $R$ of length less than $500$ km.

If $R$ does not contain the road $e$, then after the closure we may travel from $A$ to $X$ along $P_1$, then from $X$ to $Y$ along $R$, and finally from $Y$ to $B$ along $P_2$. The total length is

$$\ell(P_1)+\ell(R)+\ell(P_2)<500+500+500=1500.$$

It remains to treat the case when $R$ contains the edge $e$.

Since $R$ is an $X$-$Y$ path, the edge $e=XY$ can occur in it only once. Removing this edge splits $R$ into two parts. One part starts at $X$ and ends at $Y$, because the endpoints of the removed edge are exactly $X$ and $Y$. Hence the remainder of $R$ is an $X$-$Y$ path avoiding $e$.

Its length is strictly smaller than the length of $R$, therefore it is still less than $500$ km.

Denote this new path by $R'$. After the closure of $e$, the route

$$P_1\cup R'\cup P_2$$

connects $A$ and $B$, and its length satisfies

$$\ell(P_1)+\ell(R')+\ell(P_2) < 500+500+500 = 1500.$$

Since $A$ and $B$ were arbitrary, every pair of cities can be connected after the closure by a route of length less than $1500$ km. In particular, they can be connected using no more than $1500$ km.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the claim that a path of total length less than $500$ cannot use the edge $e$ more than once. Every road has positive length. If a path traversed $e$ twice, it would contain a cycle. Deleting that cycle would produce a shorter path between the same endpoints. Hence a shortest or simple representative may be assumed to contain $e$ at most once, and the decomposition into $P_1$, $e$, and $P_2$ is legitimate.

The second delicate step is the construction of an $X$-$Y$ path avoiding $e$ and still shorter than $500$. Suppose the short path $R$ contains $e$. Because $R$ is a path, the edge $XY$ appears exactly once. Writing

$$R=X \rightsquigarrow X \to Y \rightsquigarrow Y,$$

the portions before and after the edge have endpoints $X$ and $Y$ respectively. Removing the edge leaves a direct connection from $X$ to $Y$. Its length equals $\ell(R)-\ell(e)$, which is strictly less than $\ell(R)<500$.

The third delicate step is the final estimate. The route after closure consists of three pieces. Each piece has length less than $500$. Summing these inequalities gives a total length strictly less than $1500$. No hidden overlap or cancellation is required.

Alternative Approaches

One may phrase the argument entirely in graph-theoretic language. Let $d(u,v)$ denote the minimum path length in the original graph. The hypothesis states that $d(u,v)<500$ for all vertices $u,v$. For a removed edge $e=XY$, every original $A$-$B$ path of length less than $500$ either survives unchanged or can be decomposed at the occurrence of $e$. Replacing that occurrence by an alternative $X$-$Y$ path of length less than $500$ yields an $A$-$B$ path of length less than $1500$ in the modified graph.

The presented proof is preferable because it avoids introducing distance notation and works directly with concrete paths. The replacement of the deleted edge by a short $X$-$Y$ route is the essential idea, and the proof exposes it transparently.