Kvant Math Problem 110

The black cells form a finite set.

kvantmathematicsolympiad

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

Problem

On an infinite sheet of graph paper, $N$ cells are colored black. Prove that it is possible to cut out a finite number of squares from the sheet such that the following two conditions are satisfied:

  1. all black cells lie within the cut-out squares;
  2. in any cut-out square $K$, the area of black cells is at least $\dfrac{1}{5}$ and at most $\dfrac{4}{5}$ of the area of $K$.

G. V. Rosenblum

All-Union School Mathematics Olympiad (V)

Exploration

The black cells form a finite set. Hence all of them are contained in some sufficiently large square whose sides follow the grid lines. Let a square contain $b$ black cells and have area $s$.

The condition required for a final square is

$$\frac15 s \le b \le \frac45 s.$$

If a square contains too many black cells, then it must be small relative to the number of black cells. If it contains too few, then it is too large.

A natural idea is to start from a very large square containing all black cells and repeatedly subdivide. Since the black cells are finite in number, a sufficiently large square containing them all has density $b/s$ arbitrarily small, hence less than $1/5$.

Suppose a square has density below $1/5$. If its side length is even, divide it into four equal subsquares. The average density of the four subsquares equals the density of the whole square. Consequently, if every subsquare had density at least $1/5$, then the whole square would also have density at least $1/5$. Therefore at least one subsquare still has density below $1/5$.

This suggests constructing a family of low density squares. Choose a low density square containing all black cells and repeatedly replace it by a low density subsquare that still contains at least one black cell. Since each step halves the side length, the process must stop. The terminal square has density below $1/5$, but none of its four children has density below $1/5$ together with a black cell.

The crucial point is to understand what happens to the children of such a terminal square. Every child containing a black cell must then have density at least $1/5$. Since the parent has density below $1/5$, the total black area in the parent is less than one fifth of the parent area. Hence among the four children at most three can contain black cells. A child without black cells may simply be discarded. The children containing black cells already satisfy the lower bound $1/5$; the upper bound $4/5$ is automatic because the parent density is below $1/5$, so no child can have density exceeding $4/5$? This is false. A child could be completely black.

Thus the previous idea is insufficient.

The upper bound suggests a symmetric treatment. Instead of following only sparse squares, consider squares whose density is either below $1/5$ or above $4/5$ and subdivide them. A square with density in the desired interval is accepted. If a square has density below $1/5$, at least one child containing black cells also has density below $1/5$. If a square has density above $4/5$, at least one child has density above $4/5$ because otherwise the average density of the four children would be at most $4/5$.

Starting from a large sparse square containing all black cells, recursively subdivide every bad square. Since the number of black cells is finite, a square of area $1$ is either white or black; a black unit square has density $1$, a white one density $0$. Following a chain of bad squares containing black cells, side lengths strictly decrease. The process must terminate.

The terminal accepted squares should cover all black cells. The remaining issue is proving that every terminal square has density between $1/5$ and $4/5$. The recursive rule already guarantees this: subdivision continues exactly while density lies outside the interval. Finite termination must still be justified.

The finite termination seems to follow from the fact that every chain containing a given black cell reaches a unit cell after finitely many halvings. Since there are only finitely many black cells, only finitely many squares ever arise.

Problem Understanding

We are given finitely many black unit cells on an infinite square grid. We must cut out finitely many squares whose sides follow the grid lines so that every black cell lies in one of the chosen squares and, in each chosen square, the proportion of black area is between $\frac15$ and $\frac45$.

This is a Type B problem. The task is to prove the existence of a suitable collection of squares.

The core difficulty is to construct the squares simultaneously satisfying both density bounds. A square that is too sparse must be refined, but a square that is too dense must also be refined. The proof must show that repeated refinement eventually stops and yields only squares with densities in the required interval.

Proof Architecture

Let a square be called good if the fraction of its area occupied by black cells lies between $\frac15$ and $\frac45$, and bad otherwise.

The first lemma states that if a square has density less than $\frac15$ and contains a black cell, then one of its four equal subsquares containing a black cell also has density less than $\frac15$; this follows from averaging.

The second lemma states that if a square has density greater than $\frac45$, then one of its four equal subsquares has density greater than $\frac45$; this also follows from averaging.

The third lemma states that every descending chain of bad squares obtained by repeated subdivision is finite; side lengths are halved at each step, and once unit cells are reached no further subdivision is possible.

The final step constructs a subdivision tree starting from a sufficiently large sparse square containing all black cells and subdividing every bad square. The leaves are good squares or white unit cells. The good leaves cover all black cells.

The lemma most likely to fail under scrutiny is the finiteness argument. One must show not merely that each chain is finite, but that only finitely many squares are created in total.

Solution

Choose a square $S_0$ whose sides lie on grid lines, whose side length is a power of $2$, and which contains all black cells. Since the number of black cells is $N$, we may choose $S_0$ so large that

$$\frac{N}{\operatorname{area}(S_0)}<\frac15.$$

Thus $S_0$ is bad, with density below $\frac15$.

For any square $Q$, denote by

$$d(Q)=\frac{\text{black area in }Q}{\operatorname{area}(Q)}$$

its density.

Call a square good when

$$\frac15\le d(Q)\le\frac45.$$

Otherwise call it bad.

Starting from $S_0$, perform the following procedure. Whenever a bad square has side length greater than $1$, divide it into its four equal subsquares. Continue this operation for every bad square obtained.

Consider first a square $Q$ with $d(Q)<\frac15$. Let its four children be $Q_1,Q_2,Q_3,Q_4$. Since

$$d(Q)=\frac{d(Q_1)+d(Q_2)+d(Q_3)+d(Q_4)}4,$$

the density of the parent is the average of the densities of the children. If every child containing a black cell had density at least $\frac15$, then every nonwhite child would contribute at least $\frac15$ and every white child would contribute $0$, so the average could not be less than $\frac15$ unless all black cells disappeared. Therefore every black cell lying in $Q$ belongs to a descendant square obtained by continuing the subdivision.

Now consider a square $Q$ with $d(Q)>\frac45$. If all four children had density at most $\frac45$, then their average would also be at most $\frac45$, contradicting $d(Q)>\frac45$. Hence at least one child has density greater than $\frac45$.

Thus every bad square containing a black cell has at least one bad child containing that black cell.

We next prove that every descending chain

$$Q_0\supset Q_1\supset Q_2\supset\cdots$$

of bad squares is finite. At each step the side length is halved. Since the side length of $S_0$ is a power of $2$, after finitely many halvings we arrive at a unit cell. A unit cell has density either $0$ or $1$. White unit cells contain no black cell and need not be subdivided. Black unit cells contain a black cell but have side length $1$, so no further subdivision is possible. Hence no infinite chain exists.

Since the depth of the subdivision tree is bounded by the number of halvings needed to reach side length $1$, and each node has at most four children, the whole tree contains only finitely many squares.

Let $\mathcal L$ be the set of leaves of this finite tree. Every leaf is either a good square or a white unit cell. Indeed, a leaf that is not a white unit cell cannot be bad, because every bad square of side length greater than $1$ is subdivided.

Every black cell belongs to some leaf. A leaf containing a black cell cannot be a white unit cell. Therefore every black cell belongs to a good leaf.

Discard all white unit cells from $\mathcal L$. The remaining leaves are finitely many squares. They still contain all black cells, and each of them satisfies

$$\frac15\le d(Q)\le\frac45.$$

Hence the required finite collection of squares exists.

This completes the proof.

∎

Verification of Key Steps

The averaging argument for sparse squares requires care. Let $Q$ have density below $\frac15$. The density of $Q$ equals the arithmetic mean of the densities of its four children because each child has one quarter of the area of $Q$. If all children had density at least $\frac15$, their average would be at least $\frac15$, contradicting the hypothesis. Hence at least one child has density below $\frac15$.

The corresponding argument for dense squares is dual. If $d(Q)>\frac45$ and every child had density at most $\frac45$, then the average density of the children would be at most $\frac45$, forcing $d(Q)\le\frac45$. Thus some child must also have density above $\frac45$.

The finiteness proof depends on choosing the initial square with side length a power of $2$. Then every subdivision again produces grid aligned squares. After exactly $m$ halvings, where $2^m$ is the side length of the initial square, every descendant has side length $1$. Without this observation one could incorrectly argue that repeated subdivision merely tends toward unit size rather than actually reaching it after finitely many steps.

Alternative Approaches

A different proof proceeds by selecting all maximal squares whose density lies in the interval $\left[\frac15,\frac45\right]$. Starting from a very large sparse square containing all black cells, one follows every branch of repeated subdivision until the density first enters the desired interval. The first square on each branch with acceptable density is chosen. Maximality guarantees that these chosen squares are disjoint and cover all black cells.

The recursive tree construction used above is preferable because it avoids discussing maximal elements and directly produces the required finite family as the leaves of a finite subdivision process. The density conditions arise automatically from the stopping rule.