Kvant Math Problem 431

Verified: yes
Verdicts: PASS + PASS
Solve time: 6m37s
Source on kvant.digital

Problem

In a forest there grow trees of cylindrical shape. A lineman needs to string a wire through the forest from point $A$ to point $B$, the distance between which is $l$. Prove that for this purpose it is sufficient for the lineman to have a piece of wire of length $1{,}6l$.

A. Altshuler

Exploration

The trees are vertical cylinders. Since the wire is stretched through the forest from one ground point to another, only the horizontal arrangement of the trunks matters. In a horizontal plane, each tree becomes a circle. The problem asks for a path from $A$ to $B$ avoiding the interiors of all circles.

A shortest admissible path among circular obstacles consists of straight segments and arcs of obstacle boundaries. The length increase comes from replacing portions of the straight segment $AB$ by detours around circles.

Consider first a single circle intersecting the segment $AB$. If the segment enters the circle at $P$ and leaves at $Q$, then the forbidden chord $PQ$ must be replaced by one of the two boundary arcs joining $P$ and $Q$. Let the corresponding central angle be $\theta\le\pi$. The extra length contributed by this replacement is

$$r\theta-2r\sin\frac{\theta}{2}.$$

To obtain a uniform estimate, compare the arc length $r\theta$ directly with the chord length. Since

$$2\sin\frac{\theta}{2}\ge \frac{2}{\pi}\theta \qquad (0\le\theta\le\pi),$$

we get

$$r\theta\le \frac{\pi}{2}\cdot 2r\sin\frac{\theta}{2}.$$

Thus every detour arc is at most $\frac{\pi}{2}$ times the length of the chord it replaces.

The crucial point is whether the chords corresponding to different circles can overlap in a way that destroys additivity. Along the segment $AB$, the intersections with distinct disjoint cylinders are disjoint intervals, because tree trunks do not overlap. Hence the total length of all removed chord pieces does not exceed $l$.

Since $\frac{\pi}{2}<1.6$, this seems sufficient.

The step most likely to hide an error is the passage from one circle to many circles. One must verify that the replaced chord portions are disjoint and that the resulting route can indeed be formed by successively substituting boundary arcs for those portions.

Problem Understanding

We are given two points $A$ and $B$ at distance $l$ in a forest whose tree trunks are circular cylinders. The wire must be run from $A$ to $B$ without passing through any trunk. We must prove that a wire of length $1.6l$ always suffices.

This is a Type B problem. The statement is already specified and must be proved.

The core difficulty is to show that the total extra length caused by going around arbitrarily many cylindrical obstacles is bounded by a fixed multiple of the direct distance $AB$, independent of the number, sizes, and positions of the trees.

Proof Architecture

Lemma 1. For a circle, an arc subtending a central angle $\theta\le\pi$ has length at most $\frac{\pi}{2}$ times its chord length.

The proof uses the inequality $\sin x\ge \frac{2}{\pi}x$ for $0\le x\le \frac{\pi}{2}$.

Lemma 2. If a straight segment intersects several disjoint circles, the portions of the segment lying inside the circles are pairwise disjoint.

The reason is that disjoint circles cannot contain a common point of the segment.

Lemma 3. Replacing, for each intersected circle, the segment portion inside that circle by the shorter boundary arc joining the same endpoints produces a path avoiding all circles.

The replacement is local and the circles are disjoint.

The hardest part is proving that the total length after all replacements is at most $\frac{\pi}{2}l$; this relies on summing the chord lengths removed from $AB$ and using Lemma 2.

Solution

Let the segment $AB$ have length $l$.

If $AB$ does not meet any tree trunk, the wire can be stretched directly from $A$ to $B$, and its length is $l<1.6l$.

Assume now that $AB$ intersects some trunks. Consider one such trunk. In a horizontal plane through the wire, the trunk is represented by a circle. Let $P$ and $Q$ be the points where the segment $AB$ enters and leaves this circle. The portion $PQ$ of the segment lies inside the trunk and cannot be used.

Replace $PQ$ by the shorter of the two arcs of the circle joining $P$ and $Q$. Let $r$ be the radius of the circle and let $\theta\le\pi$ be the central angle corresponding to this arc.

The arc length equals $r\theta$, while the chord length equals

$$|PQ|=2r\sin\frac{\theta}{2}.$$

For $0\le x\le \frac{\pi}{2}$, the graph of $\sin x$ lies above the chord joining $(0,0)$ and $\left(\frac{\pi}{2},1\right)$, hence

$$\sin x\ge \frac{2}{\pi}x.$$

Substituting $x=\frac{\theta}{2}$ gives

$$2r\sin\frac{\theta}{2} \ge 2r\cdot\frac{2}{\pi}\cdot\frac{\theta}{2} = \frac{2r\theta}{\pi}.$$

Therefore

$$r\theta\le \frac{\pi}{2}|PQ|.$$

Thus the detour arc is at most $\frac{\pi}{2}$ times as long as the chord it replaces.

Perform this replacement for every trunk intersected by $AB$. Since different trunks are disjoint cylinders, the corresponding circles are disjoint. Consequently the portions of $AB$ lying inside different circles are pairwise disjoint. Denote these portions by

$$P_1Q_1,\dots,P_nQ_n.$$

Their total length satisfies

$$\sum_{i=1}^{n}|P_iQ_i|\le |AB|=l.$$

The resulting route consists of the parts of $AB$ lying outside all circles together with the chosen boundary arcs. Its length $L$ is therefore

$$L = \left(l-\sum_{i=1}^{n}|P_iQ_i|\right) + \sum_{i=1}^{n}\text{(arc}_i\text{)}.$$

Using the estimate from Lemma 1,

$$L \le \left(l-\sum_{i=1}^{n}|P_iQ_i|\right) + \frac{\pi}{2}\sum_{i=1}^{n}|P_iQ_i|.$$

Hence

$$L = l+ \left(\frac{\pi}{2}-1\right) \sum_{i=1}^{n}|P_iQ_i| \le l+ \left(\frac{\pi}{2}-1\right)l = \frac{\pi}{2}l.$$

Since

$$\frac{\pi}{2}\approx1.5708<1.6,$$

we obtain

$$L<1.6,l.$$

Thus a piece of wire of length $1.6l$ is always sufficient.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the inequality

$$r\theta\le \frac{\pi}{2}\cdot 2r\sin\frac{\theta}{2}.$$

Setting $x=\frac{\theta}{2}$ reduces it to

$$x\le \frac{\pi}{2}\sin x.$$

At $x=0$ both sides are $0$, and at $x=\frac{\pi}{2}$ both sides are $\frac{\pi}{2}$. The concavity of $\sin x$ on $[0,\frac{\pi}{2}]$ places the graph above the chord joining these endpoints, yielding exactly the required inequality.

The second delicate step is the estimate

$$\sum |P_iQ_i|\le l.$$

A careless argument might count overlapping chord portions twice. This cannot occur because each $P_iQ_i$ is the intersection of $AB$ with a particular circle, and disjoint circles have disjoint interiors. Hence the intervals $P_iQ_i$ on the segment $AB$ are pairwise disjoint. Their total length is therefore at most the length of the whole segment.

The third delicate step is the construction of the final route. Replacing each forbidden chord portion by the corresponding boundary arc leaves the endpoints of that portion unchanged. Since the replacements occur on disjoint subintervals of $AB$, the modified pieces fit together into a continuous path from $A$ to $B$ that never enters the interior of any circle.

Alternative Approaches

A shortest admissible path among circular obstacles is a classical obstacle-avoidance path. Such a path consists of straight segments and boundary arcs tangent to the circles. One may estimate its length directly by projecting all straight segments onto the line $AB$ and comparing every circular arc with its projection. The same inequality between arc length and chord length leads to the factor $\frac{\pi}{2}$.

Another approach uses convex geometry. The union of all trunks intersecting the segment $AB$ cuts from $AB$ a collection of disjoint intervals. Replacing each interval by the corresponding boundary arc of the obstacle contributes at most a factor $\frac{\pi}{2}$ relative to the removed interval. Summing these local estimates immediately yields the global bound $\frac{\pi}{2}l<1.6l$. This approach is preferable because it reduces the problem to a single elementary inequality for a circle and avoids any discussion of shortest paths.