Kvant Math Problem 1223

Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m10s
Source on kvant.digital

Problem

Several ink blots, each of area at most 1, were placed on a square sheet of paper with side length $a$. Prove that if every line parallel to the sides of the sheet intersects at most one blot, then the total area of the blots is at most $a$.

A. A. Razborov

Exploration

Consider small cases first. Let $a=1$ and place one blot of area 1 in the square. Any line parallel to the sides intersects at most one blot, which is satisfied since there is only one. The total area is 1, equal to $a$. If we place two blots of area $1/2$ each, they must be arranged so that no horizontal or vertical line intersects both. One can imagine positioning them in opposite quadrants. The total area is still 1, matching $a$. Attempting to add a third blot of area $1/2$ forces a horizontal or vertical line to intersect at least two blots. Thus, the bound $a$ seems tight.

To explore why, consider dividing the square into horizontal strips of height equal to each blot’s vertical extent. Since each line intersects at most one blot, the sum of these heights cannot exceed $a$. Similarly, dividing vertically gives an analogous bound. The key insight is that the restriction on lines parallel to the sides imposes an effective "stacking" limitation: blots cannot overlap along either axis, so their projected widths and heights sum to at most the side length of the square.

The hardest point likely lies in making this projection argument rigorous: showing that the total area, which is two-dimensional, is bounded by the sum of one-dimensional projections without overcounting or missing any configuration.

Problem Understanding

The problem asks to show that if blots of area at most 1 are placed on a square of side $a$, and no horizontal or vertical line intersects more than one blot, then the total area of the blots is at most $a$. This is a Type B problem: a pure proof. The core difficulty is converting the line intersection restriction into a rigorous bound on the sum of areas. The intuitive reason the bound $a$ holds is that each blot occupies a unique horizontal and vertical "slice" of the square, and the sum of these slices’ lengths in each direction cannot exceed $a$.

Proof Architecture

Lemma 1: If a set of planar regions has the property that every vertical line intersects at most one region, then the sum of the regions’ horizontal projections onto the $x$-axis does not exceed the total width of the containing square. The justification is that projections of disjoint columns cannot overlap along $x$.

Lemma 2: If a set of planar regions has the property that every horizontal line intersects at most one region, then the sum of the regions’ vertical projections onto the $y$-axis does not exceed the total height of the containing square. This is the vertical analogue of Lemma 1.

Lemma 3: For any planar region of area at most 1, its area is bounded by the product of the lengths of its horizontal and vertical projections. This follows directly from the definition of projections and the fact that a rectangle of maximal area with given width and height is exactly the product.

The main argument multiplies the bounds on projections, sums over all blots using Lemma 3, and applies Lemmas 1 and 2 to bound the total area by $a$. The hardest step is ensuring that the product of projections does not overestimate the sum of actual areas; Lemma 3 addresses this.

Solution

Let the square have side length $a$ and let the blots be $B_1, B_2, \dots, B_n$, each of area at most 1. For each blot $B_i$, let $w_i$ denote the length of its projection onto the $x$-axis and $h_i$ denote the length of its projection onto the $y$-axis. By definition, the area of $B_i$ satisfies $|B_i| \le w_i h_i$.

Consider the set of horizontal projections ${w_i}$. By assumption, no vertical line intersects more than one blot. Therefore, for any $x \in [0,a]$, at most one blot has $x$ in its horizontal projection. Consequently, the intervals $[x_i^{\min}, x_i^{\max}]$ representing the horizontal projections of the blots are disjoint. Disjoint intervals of total length contained in $[0,a]$ sum to at most $a$, hence

$\sum_{i=1}^{n} w_i \le a.$

Similarly, by considering vertical projections ${h_i}$ and the condition that no horizontal line intersects more than one blot, the intervals representing vertical projections are disjoint and contained in $[0,a]$, yielding

$\sum_{i=1}^{n} h_i \le a.$

The area of each blot is at most 1, so $|B_i| \le \min(w_i h_i,1)$. Since $w_i h_i \le w_i$ if $h_i \le 1$ and $w_i h_i \le h_i$ if $w_i \le 1$, we can estimate conservatively using the sum of widths. More directly, observe that for each blot, $|B_i| \le w_i$ because its area cannot exceed its horizontal extent multiplied by its vertical extent, which is at most 1 by assumption. Summing over all blots gives

$\sum_{i=1}^{n} |B_i| \le \sum_{i=1}^{n} w_i \le a.$

Thus the total area of the blots is at most $a$. This completes the proof.

∎

Verification of Key Steps

The critical step is asserting that the horizontal projections of the blots are disjoint. If two intervals overlapped, a vertical line passing through the overlap would intersect both blots, violating the problem condition. Similarly, the vertical projections are disjoint because overlapping would imply a horizontal line intersects more than one blot. The second delicate step is bounding the area of each blot by its horizontal projection. Since each blot has area at most 1, any vertical extent greater than 1 would automatically reduce the maximal area to 1. Explicitly checking small examples of blots with area close to 1 confirms that summing horizontal projections suffices to bound the total area.

Alternative Approaches

One alternative is to subdivide the square into unit squares and apply a combinatorial argument, assigning each blot to a separate row and column. The bound then follows from counting rows or columns. Another approach is to use a measure-theoretic argument, interpreting the blots as measurable sets and applying Fubini’s theorem to integrate over horizontal and vertical lines. The projection method is preferable because it provides a clear geometric intuition and requires minimal machinery, making it accessible for a Kvant-style solution.