Kvant Math Problem 464

Verified: yes
Verdicts: PASS + PASS
Solve time: 9m26s
Source on kvant.digital

Problem

On the plane, 1000 squares are given whose sides are parallel to the coordinate axes. Let $M$ be the set of the centers of these squares. Prove that it is possible to mark some of the squares so that each point of the set $M$ belongs to at least one and to at most four marked squares.

A. Plotkin

All-Union Mathematical Olympiad for School Students (XI, 1977, Grade 9)

Exploration

Let each square correspond to its center. A point of $M$ belongs to a square precisely when the center of that square lies within a certain axis-parallel square centered at the given point. Thus the problem can be translated into a finite incidence problem on the set $M$ itself.

A natural idea is to choose squares greedily. Suppose we repeatedly select a square whose center has an extreme coordinate. If we take the square whose center is leftmost among all remaining centers, then every center lying in that square must have $x$-coordinate at least that of its center. Since the square is axis-parallel, any center contained in it lies in a rectangle extending at most half a side length to the right and left of the center. Because there are no remaining centers farther left, the contained centers occupy only the right half of that square.

This suggests a packing bound. If a point $P\in M$ lies in many selected squares, look at the centers of those squares. Since each selected square was chosen when its center was leftmost among the remaining ones, after a square is selected all centers covered by it disappear from further consideration. Hence two selected squares containing $P$ cannot have centers lying in the same quadrant with vertex at $P$. Indeed, if one such center were farther from $P$ in the same quadrant than another, then the earlier selected square would also contain the latter center and would have removed it.

The plane around $P$ has four quadrants. Therefore at most four selected squares can contain $P$.

The remaining task is to make the greedy procedure precise and verify that every point of $M$ is covered. The key step is proving the “at most one center in each quadrant” statement rigorously.

Problem Understanding

We are given $1000$ axis-parallel squares in the plane. Their centers form a set $M$ of $1000$ points. We must choose some of the squares so that every point of $M$ belongs to at least one chosen square and to at most four chosen squares.

This is a Type B problem. We must prove the existence of a suitable selection.

The difficulty is to guarantee simultaneously that every center is covered and that no center is covered too many times. A greedy elimination process seems promising because it naturally guarantees coverage, while the geometry of axis-parallel squares may force a uniform bound on the multiplicity of coverage.

Proof Architecture

First, order the construction greedily: among all centers not yet covered by previously chosen squares, choose the leftmost one and mark its square.

Second, prove that the process ends with every point of $M$ covered, because points are removed only when already covered by a marked square.

Third, fix a point $P\in M$ and consider all marked squares containing $P$.

Fourth, prove that among the centers of these marked squares there cannot be two in the same quadrant with vertex at $P$; if two existed, the earlier chosen square would have contained the later center and would have removed it from further consideration.

Fifth, deduce that there are at most four such centers, one per quadrant, hence at most four marked squares containing $P$.

The most delicate lemma is the fourth one. It requires proving that if two centers lie in the same quadrant relative to $P$ and both corresponding squares contain $P$, then the square centered at the nearer one also contains the farther center.

Solution

For each point $A\in M$, let $Q(A)$ denote the given square whose center is $A$.

We construct a family of marked squares as follows.

Initially all points of $M$ are called active. While active points remain, choose among them the point with smallest $x$-coordinate. Call it $A$. Mark the square $Q(A)$ and delete from the active set every point of $M$ lying in $Q(A)$.

Since at least the point $A$ itself is deleted at each step, the procedure terminates after finitely many steps.

Every point of $M$ is deleted at some stage. A point is deleted only when it lies in a marked square. Hence every point of $M$ belongs to at least one marked square.

It remains to prove that every point of $M$ belongs to at most four marked squares.

Fix a point $P\in M$.

Consider all marked squares containing $P$. Let their centers be

$$A_1,A_2,\dots,A_k.$$

We shall show that $k\le 4$.

Draw through $P$ the horizontal and vertical lines. They divide the plane into four closed quadrants. We prove that at most one of the centers $A_i$ can lie in any given quadrant.

Assume, for contradiction, that two centers $A$ and $B$ of marked squares containing $P$ lie in the same quadrant. Since both squares contain $P$, if their side lengths are $2a$ and $2b$, respectively, then

$$|x_P-x_A|\le a,\qquad |y_P-y_A|\le a,$$

and

$$|x_P-x_B|\le b,\qquad |y_P-y_B|\le b.$$

Without loss of generality, suppose that the square $Q(A)$ was marked earlier than $Q(B)$.

Because $A$ and $B$ lie in the same quadrant with vertex at $P$, the coordinate differences from $P$ have the same signs. Also, $A$ was active when chosen, whereas $B$ survived until a later stage. Since the algorithm always chooses the active point with smallest $x$-coordinate, we have

$$x_A<x_B.$$

Assume for definiteness that $A$ and $B$ are in the northeast quadrant of $P$; the other quadrants are identical. Then

$$x_P\le x_A<x_B,\qquad y_P\le y_A,\ y_P\le y_B.$$

From $P\in Q(A)$ we obtain

$$x_A-a\le x_P\le x_A+a, \qquad y_A-a\le y_P\le y_A+a.$$

Since $x_B\ge x_P$, we get

$$x_B-x_A \le x_P+a-x_A \le a.$$

Likewise,

$$y_B-y_A \le y_P+a-y_A \le a.$$

Therefore

$$|x_B-x_A|\le a,\qquad |y_B-y_A|\le a.$$

This means exactly that the point $B$ lies in the square $Q(A)$.

When $Q(A)$ was marked, every active point of $M$ lying in $Q(A)$ was deleted. Since $B\in Q(A)$, the point $B$ would have been deleted at that moment and could never later be chosen as the center of a marked square. This contradiction proves that no two centers of marked squares containing $P$ can lie in the same quadrant.

There are only four quadrants. Hence among the centers of marked squares containing $P$ there is at most one center in each quadrant. Consequently

$$k\le 4.$$

Thus every point of $M$ belongs to at least one and to at most four marked squares.

This completes the proof.

∎

Verification of Key Steps

The crucial geometric step is the implication that if $A$ and $B$ lie in the same quadrant relative to $P$, and both corresponding squares contain $P$, then $B\in Q(A)$ whenever $x_A<x_B$.

Take the northeast case. From $P\in Q(A)$,

$$x_P-x_A\le a,\qquad y_P-y_A\le a.$$

Because $x_A<x_B$ and $x_B\ge x_P$,

$$x_B-x_A=(x_B-x_P)+(x_P-x_A)\le 0+(a)=a.$$

Similarly,

$$y_B-y_A\le a.$$

Both coordinate differences are bounded by the half-side length of $Q(A)$, which is exactly the condition $B\in Q(A)$.

A careless argument might claim merely that $A$ is “closer” to $P$ than $B$. That is not required and need not be true. The proof uses only coordinate inequalities and the fact that the centers are in the same quadrant.

Another delicate point is the use of the greedy rule. The contradiction requires $x_A<x_B$. This follows because $A$ was selected earlier and, at that moment, both $A$ and $B$ were active. The algorithm always chooses the active point with smallest $x$-coordinate. Without this rule, the bound of four would not follow.

Finally, coverage is guaranteed because a point leaves the active set only when it lies in a marked square. Every point is eventually deleted since the process ends only when no active points remain.

Alternative Approaches

The argument may be reformulated in graph-theoretic language. Create a directed graph on $M$ by connecting a center $A$ to every center lying in $Q(A)$. Repeatedly choose a vertex of minimum $x$-coordinate among the remaining vertices and delete its entire out-neighborhood. The selected vertices form a dominating set. The geometric part of the proof shows that, for any fixed point $P$, selected vertices whose squares contain $P$ form an antichain with respect to the four quadrant orders around $P$, yielding size at most four.

Another viewpoint uses four partial orders, one for each quadrant. For a fixed point $P$, centers of marked squares containing $P$ are pairwise incomparable in the same order because earlier selections eliminate later comparable centers. Since every center belongs to one of four quadrant classes, at most four marked squares can contain $P$. The greedy geometric proof is preferable because it avoids introducing order-theoretic terminology and keeps the incidence argument entirely elementary.