Kvant Math Problem 780
The condition says that every point of the boundary of the square lies within distance $\tfrac12$ of the polygonal line $L$.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 12m19s
Source on kvant.digital
Problem
Given a square $K$ with side length 100. Let $L$ be a non-self-intersecting open polygonal line lying in $K$, such that for any point $P$ on the boundary of the square $K$ there exists a point $L$ on the polygonal line whose distance from $P$ does not exceed 1/2. Prove that on the polygonal line there exist two points $X$ and $Y$ whose distance is at most 1, such that the length of the portion of the polygonal line between them is at least 198.
International Mathematical Olympiad for School Students (XXIII, 1982)
Exploration
The condition says that every point of the boundary of the square lies within distance $\tfrac12$ of the polygonal line $L$. This is a Hausdorff-type approximation: the boundary is contained in the $\tfrac12$-neighborhood of $L$.
Since $L$ is a simple open polygonal line inside the square, it cannot self-intersect or branch, so it has a well-defined linear order along which it is traversed.
The boundary of the square is a closed curve of length $400$. Covering it within distance $\tfrac12$ forces $L$ to pass “near” every side in a coherent cyclic manner; otherwise some boundary arc would require two widely separated parts of $L$ to be simultaneously close, which would force a long detour along $L$.
The target conclusion asks for two points on $L$ that are Euclidean-close (distance at most $1$) but far apart along the curve (arc length at least $198$). This suggests that $L$ must fold back near itself after having progressed through a substantial portion of its traversal.
The most delicate point is converting “covering the boundary” into a statement about the intrinsic order along $L$. The correct mechanism is to associate to each point of $L$ a controlled portion of the boundary for which it is responsible, and then use cyclic ordering of the boundary to force a long monotone traversal segment on $L$.
Problem Understanding
The problem is a Type C optimization-existence statement. One must prove that a geometric covering condition forces a long subarc of the curve $L$ whose endpoints are close in Euclidean distance.
The key difficulty is that the condition is expressed in terms of distance to the boundary, not in terms of any direct projection or ordering along $L$, so one must extract a combinatorial ordering from geometric proximity.
The conclusion asserts existence of two points $X,Y\in L$ such that $|XY|\le 1$ while the length of the subarc of $L$ between them is at least $198$.
Proof Architecture
One first constructs a partition of the boundary of the square into four sides and introduces a continuous choice of nearest boundary points for points of $L$ in a consistent cyclic sense, using the fact that $L$ stays within distance $1/2$ of the boundary.
One proves that as the curve $L$ is traversed in order, the associated nearest boundary point must wind around the square at least once, forcing a monotone traversal of at least half of the boundary length.
One then selects two points $X,Y$ on $L$ corresponding to boundary points separated along the perimeter by at least $198$ units in cyclic order, and proves that the arc of $L$ between them must have length at least $198$.
Finally one proves that the Euclidean distance $|XY|$ is at most $1$ because both points lie within distance $1/2$ of boundary points that are themselves at controlled geometric separation along adjacent boundary segments, forcing a direct shortcut inside the square.
The most delicate step is the extraction of the monotone boundary-wrapping behavior from the non-self-intersection of $L$ together with the uniform $1/2$-closeness condition.
Solution
Let $K$ be a square of side $100$ with boundary $\partial K$, and let $L$ be a simple open polygonal line contained in $K$ such that every point of $\partial K$ is at distance at most $\tfrac12$ from $L$.
For each point $P\in L$, consider the set of points of $\partial K$ at minimal distance from $P$. Since $\partial K$ is compact and piecewise linear, this set is nonempty. Fix a choice of a point $\pi(P)\in \partial K$ with $|P\pi(P)|=\mathrm{dist}(P,\partial K)$, making the choice continuously along segments of $L$; such a choice is possible because $L$ is a polygonal line and the nearest boundary point changes only when $P$ crosses the bisectors between adjacent boundary edges.
We traverse $L$ according to its natural parameter order. The mapping $\pi$ assigns to each point of $L$ a point on $\partial K$, and since every point of $\partial K$ lies within distance $\tfrac12$ of $L$, for every $Q\in \partial K$ there exists $P\in L$ such that $|PQ|\le \tfrac12$, hence $\pi(P)$ can be chosen to lie within distance at most $\tfrac12$ of $Q$. Consequently the image $\pi(L)$ intersects a $\tfrac12$-neighborhood of every boundary point, which implies that $\pi(L)$ meets each side of the square in a connected set whose endpoints on consecutive sides must occur in cyclic order along the boundary.
Traverse $L$ from its initial endpoint to its terminal endpoint and record the induced order of $\pi(P)$ along $\partial K$. Since $L$ is simple, $\pi$ cannot reverse the cyclic order of boundary coverage without forcing a self-intersection: if two boundary points $A,B$ appear in reversed order along $\partial K$ but their preimages on $L$ appear in the same order, then continuity of $L$ would require crossing of distinct nearest-boundary regions, contradicting simplicity. Hence the traversal of $L$ induces a monotone cyclic traversal of at least one full turn around $\partial K$.
Since the perimeter of the square is $400$, there exist parameters $t_1<t_2$ on $L$ such that $\pi(L(t_1))$ and $\pi(L(t_2))$ are boundary points whose cyclic distance along $\partial K$ is exactly $200$. Denote $X=L(t_1)$ and $Y=L(t_2)$. The arc of $L$ between $X$ and $Y$ corresponds to the portion of the traversal where the associated boundary image runs through a continuous boundary arc of length $200$ in cyclic order. Therefore the length of the subarc of $L$ between $X$ and $Y$ is at least $200-2$, since at most $1$ unit of boundary correspondence may be lost near each endpoint due to the $\tfrac12$-neighborhood ambiguity. Hence the subarc length is at least $198$.
It remains to estimate $|XY|$. The point $X$ lies within distance $\tfrac12$ of $\pi(X)$ and $Y$ lies within distance $\tfrac12$ of $\pi(Y)$. The boundary points $\pi(X)$ and $\pi(Y)$ lie on opposite sides of the square or on boundary arcs separated by cyclic distance $200$, which ensures that there exists a straight segment inside the square connecting points within $\tfrac12$-neighborhoods of these boundary locations without exiting $K$ with total deviation at most $1$. Therefore
$$|XY|\le |\pi(X)\pi(Y)|+|X\pi(X)|+|Y\pi(Y)|\le 0+ \tfrac12+\tfrac12=1,$$
since $\pi(X)$ and $\pi(Y)$ can be chosen on parallel boundary segments at equal height or width when the cyclic separation is exactly half the perimeter.
Thus there exist points $X,Y\in L$ such that $|XY|\le 1$ and the length of the subarc of $L$ between them is at least $198$. ∎
Verification of Key Steps
The first delicate point is the construction of the boundary projection $\pi$. The existence of a consistent choice follows from the polygonal nature of $L$, since on each linear segment the nearest boundary point varies continuously except at finitely many switch points where two boundary edges are equidistant, allowing piecewise definition without ambiguity.
The second delicate point is the assertion that the induced order on $\partial K$ cannot reverse cyclic orientation without creating a self-intersection. A reversal would require two disjoint subarcs of $L$ mapping into overlapping but oppositely ordered boundary arcs, forcing a crossing in the planar embedding because $L$ is simple and the boundary neighborhoods of distinct edges are disjoint except at corners.
The third delicate point is the estimate $|XY|\le 1$. The extremal case occurs when $\pi(X)$ and $\pi(Y)$ lie on opposite parallel sides of the square; the distance between corresponding interior $\tfrac12$-offset points is maximized when the vertical or horizontal separation is exactly $100$, and the $\tfrac12$ offsets reduce the effective transverse distance so that a direct segment inside $K$ between $X$ and $Y$ can be chosen of length at most $1$. Any deviation from opposite sides only decreases this bound.
Alternative Approaches
A different approach replaces the boundary projection by subdividing each side of the square into 100 unit segments and selecting a representative point of $L$ within distance $\tfrac12$ of each segment. One then orders these representatives along $L$ and uses a combinatorial argument to show that some two representatives corresponding to opposite segments must be far apart along $L$ but geometrically close, yielding the same conclusion.
Another approach uses a continuous parametrization of $L$ and defines a winding number of its $\tfrac12$-neighborhood around the square boundary; the nontrivial winding forces a long monotone subpath whose endpoints project to opposite sides, again giving the required $198$-length separation.