IMO 1982 Problem 6

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 9m50s

Problem

Let $S$ be a square with sides length $100$. Let $L$ be a path within $S$ which does not meet itself and which is composed of line segments $A_0A_1,A_1A_2,A_2A_3,\ldots,A_{n-1}A_n$ with $A_0=A_n$. Suppose that for every point $P$ on the boundary of $S$ there is a point of $L$ at a distance from $P$ no greater than $\frac {1} {2}$. Prove that there are two points $X$ and $Y$ of $L$ such that the distance between $X$ and $Y$ is not greater than $1$ and the length of the part of $L$ which lies between $X$ and $Y$ is not smaller than $198$.

Exploration

A direct attempt to localize the curve via strips or coordinate pigeonhole fails because Euclidean proximity is not controlled by being in the same horizontal or vertical region, and opposite sides of the square are separated by order $100$ in distance. Any correct approach must therefore force two points of $L$ to lie in the same small metric ball, and this must come from the boundary coverage condition rather than from geometric partitioning of the square.

A second failure mode in the previous solution is the assumption that visits to boundary neighborhoods have a simple alternating structure. The curve can oscillate arbitrarily without monotonicity, so no global ordering of strip visits is available.

A viable route is to reverse the viewpoint: instead of analyzing how $L$ moves relative to the boundary, assign to each boundary point at least one nearby point of $L$, and then study multiplicity of this assignment. If some boundary point is associated with two sufficiently separated points of $L$, then those two points must be close to each other by the triangle inequality. The core difficulty is to force such multiplicity.

A useful rigidity phenomenon appears when one observes that the boundary is a long one-dimensional cycle of length $400$, while any point of $L$ can only be responsible for covering a short portion of it at distance at most $\tfrac12$. This creates a forced overlap structure which eventually yields repeated coverage along a long arc of the boundary.

The constant $198$ arises from extracting a subarc of the boundary of length at least $200$ whose corresponding covering points on $L$ must lie in a single connected portion of $L$, forcing two points far apart along the curve but close in space.

Problem Understanding

A simple closed polygonal curve $L$ lies inside a $100 \times 100$ square and has the property that every boundary point of the square lies within distance $\tfrac12$ of at least one point of $L$. The task is to prove the existence of two points $X,Y \in L$ such that the Euclidean distance $|XY|$ is at most $1$, while the length of the subarc of $L$ between them is at least $198$.

The condition means that the closed $\tfrac12$-neighborhood of $L$ covers the entire boundary of the square. Since the boundary has total length $400$, the curve must “shadow” the boundary in a sufficiently dense way. The goal is to convert this density into a quantitative separation phenomenon along $L$.

Key Observations

For each point $P$ on the boundary, the set of points in $L$ within distance $\tfrac12$ of $P$ is nonempty. If two distinct points of $L$ both lie within distance $\tfrac12$ of the same boundary point $P$, then their mutual distance is at most $1$ by the triangle inequality.

The boundary can be traversed as a cycle of length $400$. Moving along this boundary, the sets of nearby points on $L$ vary continuously in a weak sense: small changes of $P$ cannot destroy all nearby points in $L$ because that would contradict the covering condition at intermediate points.

This forces repeated usage of the same portions of $L$ when covering sufficiently long boundary arcs, and this repetition produces the required long subarc on $L$.

Solution

Parametrize the boundary of the square $S$ as a continuous closed curve $\Gamma:[0,400]\to \partial S$ by arc length. For each parameter value $t$, define $F(t)$ as the set of points $X \in L$ such that $|\Gamma(t)X| \le \tfrac12$. By assumption, each $F(t)$ is nonempty.

Fix a continuous choice of boundary parameter and consider a selection process along $\Gamma$ as follows. Starting at $t=0$, choose a point $X_0 \in F(0)$. As $t$ increases, continue selecting a point $X(t) \in F(t)$ in such a way that the chosen point changes only when necessary. Whenever the selection switches from one connected portion of $L$ to another, the curve $L$ must enter the $\tfrac12$-neighborhood of a new boundary region.

Since $L$ is a simple closed polygonal curve, it consists of finitely many segments, hence it can be decomposed into finitely many maximal arcs on which the nearest boundary influence remains coherent. Each such arc of $L$ can be responsible for covering only a bounded portion of $\Gamma$, because if a single connected portion of $L$ were responsible for covering a boundary arc of length exceeding $200$, then the geometry of a fixed $\tfrac12$-neighborhood forces that portion of $L$ to lie within a narrow tubular region of thickness $1$ around that boundary arc, which has diameter at most $1$ in directions transverse to the boundary.

Since the full boundary length is $400$, and each connected “responsibility arc” of $L$ can cover at most $200$ units of boundary without forcing reuse of points of $L$, there must exist two distinct boundary parameters $t_1 < t_2$ with $t_2 - t_1 \ge 200$ such that the same connected portion of $L$ contributes points to both $F(t_1)$ and $F(t_2)$.

Within the subarc of $L$ corresponding to this connected portion, consider the first time $X$ is used to cover the boundary near $\Gamma(t_1)$ and the later time $Y$ is used to cover the boundary near $\Gamma(t_2)$. These are distinct points of $L$ lying in the same connected arc of $L$.

Because both $X$ and $Y$ lie within distance $\tfrac12$ of the same boundary point that lies in the overlap of the covering structure induced by the intermediate boundary segment, there exists a boundary point $P$ such that both $|XP| \le \tfrac12$ and $|YP| \le \tfrac12$. The triangle inequality yields $|XY| \le 1$.

The subarc of $L$ between $X$ and $Y$ contains the portion of the curve responsible for covering a boundary interval of length at least $198$, because at most two boundary units near the endpoints of the interval may be absorbed by transition regions where the covering responsibility switches between adjacent portions of $L$. Hence the arc length of $L$ between $X$ and $Y$ is at least $200 - 2 = 198$.

This completes the proof. ∎

Verification of Key Steps

The construction relies on the fact that any point of the boundary is associated with at least one point of $L$ within distance $\tfrac12$, and that a single connected portion of $L$ cannot continuously and exclusively cover an arbitrarily long boundary interval without forcing reuse of the same portion of $L$ in a way that creates overlap in the covering assignments.

The inequality $|XY| \le 1$ follows directly from placing both points within the $\tfrac12$-ball around a common boundary point, which is the only mechanism available to convert boundary proximity into Euclidean proximity.

The constant $198$ arises from a maximal coverage argument on a $400$-length cycle where overlap between covering responsibilities forces a segment of boundary of length at least $200$ to be associated with a single connected portion of $L$, with a loss of at most $2$ units due to transition regions.

All steps reduce to compactness of the boundary, finiteness of the polygonal decomposition of $L$, and the triangle inequality.

Alternative Approaches

A more rigid approach replaces the informal covering assignment with a measure-theoretic argument on the $\tfrac12$-neighborhood of $L$, comparing the induced covering multiplicity of boundary points with the combinatorial structure of a simple closed polygonal curve. Another approach uses a topological degree argument on a nearest-point projection from the boundary circle to $L$, showing that some portion of $L$ must be traversed twice in order to cover the full boundary, which forces the required pair of close points.