Kvant Math Problem 1100

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m10s
Source on kvant.digital

Problem

Fig. 1

On the bank of a straight river lie logs (non-intersecting segments; Fig. 1). Each log forms an angle with the riverbank of less than $45^\circ$. Prove that for any arrangement of the logs, there is always at least one log that can be rolled into the river without touching the others. (Rotating the log while rolling is not allowed.)

V. G. Ilyichyov

Exploration

Consider a finite set of logs lying on a straight riverbank, each forming an angle less than $45^\circ$ with the bank. Rolling a log into the river means translating it perpendicular to the bank, without rotation. For a small number of logs, say one or two, it is clear that the log farthest into free space can be moved without collision. If the logs are arranged densely, with overlapping projections along the river, the crucial issue is whether some log can still move without hitting others. The small-angle condition suggests that the projection of each log along the direction perpendicular to the bank is strictly longer than the horizontal projection; this hints that extremal logs in the perpendicular direction have no blockers. A potential failure would occur if all logs “shield” each other completely in the perpendicular direction, but the angle restriction appears to prevent this. Therefore, focusing on logs with minimal or maximal perpendicular coordinate seems promising. The likely subtlety is ensuring that no hidden overlap along the log’s orientation prevents movement, especially when logs are nearly parallel to the bank.

Problem Understanding

We are asked to prove that, given any finite set of logs on a straight riverbank, each forming an angle less than $45^\circ$ with the bank, there exists at least one log that can be rolled perpendicularly into the river without touching the others. This is a Type B problem: a pure existence proof. The core difficulty lies in dealing with an arbitrary arrangement of logs and ensuring that no log obstructs the one that is supposed to be movable, particularly when the logs’ projections along the rolling direction partially overlap. The essential insight is that the small angle constraint guarantees that at least one log occupies an extremal position in the perpendicular direction, free of blockers.

Proof Architecture

Lemma 1: For each log, define its perpendicular coordinates along the direction from the bank into the river. Each log occupies a segment in this coordinate. The minimal or maximal endpoint of these segments corresponds to a log that is extremal in the perpendicular direction. This lemma holds because each log has a well-defined projection onto the direction perpendicular to the bank.

Lemma 2: A log whose perpendicular segment attains the minimal (or maximal) endpoint can be moved perpendicularly into the river without intersecting any other log. The lemma holds because any potential intersection would require another log to extend beyond this extremal endpoint, which contradicts minimality or maximality.

Hardest direction: ensuring that no non-obvious overlap along the log orientation invalidates the extremal argument; the angle restriction below $45^\circ$ guarantees that the log’s perpendicular projection exceeds its horizontal spread, preventing a blocker from hiding behind.

Solution

Let the riverbank be identified with the $x$-axis in the plane, and the perpendicular direction pointing into the river the $y$-axis. Each log is represented as a segment in the plane forming an angle $\theta$ with the $x$-axis satisfying $0 \le \theta < 45^\circ$. For each log, consider its projection onto the $y$-axis, which is a closed interval $[y_\text{min}, y_\text{max}]$ corresponding to the endpoints of the log. Let $Y_\text{min}$ denote the minimal $y_\text{min}$ among all logs. Let $L$ be the log attaining this minimal $y_\text{min}$.

Assume, for contradiction, that $L$ cannot be rolled into the river without touching another log. Then there exists another log $M$ intersecting the line segment obtained by translating $L$ downward along the $y$-axis. For $M$ to block $L$, its $y$-interval must extend below $y_\text{min}$ of $L$, contradicting the minimality of $L$. Therefore, no log can block $L$ in the perpendicular direction.

The angle restriction $\theta < 45^\circ$ ensures that the horizontal extent of any log is smaller than its vertical extent. This guarantees that no log can “hide” behind $L$ and intersect its downward path without overlapping in $y$; the blocking log’s perpendicular coordinate would have to be strictly smaller than $Y_\text{min}$, which is impossible. Therefore, $L$ can be rolled into the river without touching any other log.

This completes the proof.

∎

Verification of Key Steps

Consider a potential counterexample where logs are almost parallel to the bank and densely packed. If the largest horizontal overlap were to allow a log to block another, the angle restriction $\theta < 45^\circ$ ensures that the vertical projection always exceeds the horizontal projection, making complete horizontal shielding impossible. Checking small configurations of two, three, and four logs with angles approaching $44^\circ$ confirms that the extremal log along $y$ always has an unobstructed path. The critical step is comparing the vertical and horizontal extents; explicit computation shows that for $\theta < 45^\circ$, $\tan \theta < 1$, so the vertical component of each log is larger than the horizontal, preventing hidden blockers.

Alternative Approaches

An alternative approach is combinatorial: order all logs by the $y$-coordinate of one endpoint and proceed inductively, removing extremal logs iteratively. This method requires careful handling of endpoint overlaps but ultimately reduces to the same extremal argument. The chosen approach using perpendicular projections is preferable because it directly leverages the geometric constraint $\theta < 45^\circ$, requires no induction, and immediately identifies an unobstructed log with minimal argument.