Kvant Math Problem 494

Let the square be partitioned into a regular grid of $n \times n$ congruent squares, each of side length $1/n$.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 9m50s
Source on kvant.digital

Problem

Inside a square of side 1, $n^2$ points are located. Prove that there exists a polygonal line containing these points whose length is less than

  1. $3n$;
  2. $2n$.

A. Tartakovsky, 10th grade student

Exploration

Let the square be partitioned into a regular grid of $n \times n$ congruent squares, each of side length $1/n$. Every point lies in one such cell.

A natural way to build a polygonal line passing through all points is to assign each point a “representative structure” (such as its cell center), and then connect these representatives in a controlled order. The difficulty is to ensure that every point lies on the constructed polyline while keeping the total length small.

For the weaker bound $3n$, a single sweep through vertical strips suggests itself. Each strip has width $1/n$, so horizontal motion can be controlled, while vertical motion can be organized within strips.

For the stronger bound $2n$, the key idea is to decouple the geometry into two contributions: short “links” from each point to a structured skeleton (cell centers), and a controlled traversal of that skeleton. The delicate issue is ensuring that the sum of all such link lengths remains linear in $n$ and does not scale like $n^2$.

The central insight is that assigning each point to its cell center makes each “attachment segment” extremely short, of order $1/n$, while the traversal of all cell centers in a snake-like Hamiltonian path of the grid contributes another linear term in $n$.

Problem Understanding

This is a Type C problem: we must show the existence of a polygonal line through $n^2$ arbitrary points in the unit square whose length is bounded above first by $3n$, and then by $2n$.

The object to construct is a single broken line containing all points, not necessarily without self-intersections. The main difficulty is to control total length uniformly over all configurations of points.

The final bounds are

$\boxed{3n} \quad \text{and} \quad \boxed{2n}.$

The intuition is that the unit square can be decomposed into $n^2$ small regions of diameter $O(1/n)$, and a global ordering of these regions yields a path of total length $O(n)$.

Proof Architecture

The proof of the first bound constructs a vertical strip decomposition into $n$ strips and builds a path visiting all points by traversing strips sequentially, ordering points within each strip by increasing $y$-coordinate, and estimating separately vertical motion inside strips and horizontal jumps between strips.

The proof of the second bound constructs an $n \times n$ grid and uses cell centers as intermediate vertices. Each point is connected to its cell center, producing a total attachment length bounded by a sum of distances from points to centers. Then all centers are traversed in a Hamiltonian “snake” path whose length is controlled by adjacency in the grid.

The most delicate step is the second estimate, where one must ensure that summing $n^2$ short segments of length $O(1/n)$ still yields $O(n)$ total length, and that the traversal of grid centers contributes another linear term.

Solution

For the first bound, partition the unit square into $n$ vertical strips of width $1/n$. Label them $S_1,\dots,S_n$ from left to right. In each strip $S_k$, list the points it contains in increasing order of their $y$-coordinates, and connect consecutive points in this order by straight segments. If $S_k$ and $S_{k+1}$ are consecutive strips, connect the last point in $S_k$ to the first point in $S_{k+1}$.

Within a fixed strip, every segment connecting two points has vertical length at most $1$, so the total vertical variation inside each strip is at most $1$. Since there are $n$ strips, the total vertical contribution does not exceed $n$.

Each transition between strips involves a horizontal displacement between two points in adjacent strips, and any such horizontal distance is at most $1/n$. There are at most $n-1$ such transitions, so the total horizontal contribution is less than $1$.

The total length of the polygonal line is therefore less than $n+1$, which implies it is strictly less than $3n$ for all positive integers $n$. This establishes the first bound.

For the second bound, partition the square into $n^2$ equal subsquares of side $1/n$, and denote their centers by $C_{ij}$ for $1 \le i,j \le n$. Each point lies in exactly one subsquare.

For each point $P$, let $C(P)$ denote the center of its subsquare. Connect $P$ to $C(P)$ by a straight segment. Since the farthest point in a square of side $1/n$ from its center is a vertex, the distance satisfies

$|PC(P)| \le \frac{\sqrt{2}}{2n}.$

Summing over all $n^2$ points, the total length of these attachment segments is at most

$n^2 \cdot \frac{\sqrt{2}}{2n} = \frac{\sqrt{2}}{2}n.$

Next construct a polygonal line visiting all centers $C_{ij}$ in a snake order: traverse the first row left to right, then move down one step, traverse the next row right to left, and continue alternately. Consecutive centers in this ordering lie in adjacent subsquares sharing a side, so their distance is exactly $1/n$. Since there are $n^2-1$ transitions between centers, the total length of this traversal is

$\frac{n^2-1}{n} < n.$

Concatenating the attachment segments and the snake traversal yields a polygonal line containing all points, since each point lies on the segment connecting it to its cell center, which is part of the constructed path.

The total length is therefore less than

$\frac{\sqrt{2}}{2}n + n < 2n,$

since $\frac{\sqrt{2}}{2} < 1$.

This completes the construction for the second bound.

Verification of Key Steps

The first delicate point is the estimate inside vertical strips. The argument relies on the fact that within each strip the total vertical variation of a monotone ordering in $y$ is bounded by the height of the square, which is $1$, since telescoping sums of consecutive $y$-differences collapse to the difference between maximum and minimum $y$ in the strip.

The second delicate point is the bound on point-to-center distances. The farthest distance from a point in a square of side $1/n$ to its center is achieved at a vertex, giving Euclidean distance $\sqrt{(1/2n)^2+(1/2n)^2}=\sqrt{2}/(2n)$.

The third delicate point is the total attachment cost. Each point contributes independently exactly one segment to its cell center, so no overcounting occurs, and summing over all $n^2$ points yields a linear bound in $n$.

The fourth delicate point is the traversal of centers. Adjacent subsquare centers differ by exactly $1/n$ in one coordinate and $0$ in the other, so Euclidean distance is $1/n$, and the snake ordering uses exactly $n^2-1$ such steps.

Alternative Approaches

An alternative proof of the $3n$ bound can be obtained by sorting points by $x$-coordinate and connecting consecutive points, then bounding horizontal displacement by the diameter of the square and vertical displacement by partitioning the range of $y$-coordinates into controlled increments.

A different approach to the $2n$ bound avoids cell centers and instead constructs a hierarchical clustering of points, repeatedly merging nearby points into trees of controlled total length, then connecting cluster representatives in a global traversal. This yields a similar linear bound but requires more elaborate bookkeeping than the grid-center method, which isolates geometry into two transparent contributions.