Kvant Math Problem 658

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m26s
Source on kvant.digital

Problem

In a square with side length 1, a finite number of segments parallel to its sides are drawn. The segments may intersect each other. The sum of the lengths of the drawn segments is 18. Prove that among the regions into which the square is divided by these segments, there exists one whose area is at least 0.01.

Fig. 1

A. V. Andzhan

Exploration

Consider a square of side length $1$ with a collection of horizontal and vertical segments inside it. Each segment is entirely contained in the square, and the total sum of their lengths is $18$. Since the square's perimeter is only $4$, the total segment length far exceeds the perimeter. This suggests that the segments are very dense, possibly cutting the square into many small rectangles. If we attempt to make all regions extremely small, for example with areas less than $0.01$, then each horizontal strip would have length approximately $0.1$ or smaller in height, and each vertical strip would have width similarly small. However, a quick calculation shows that to achieve $18$ units of total segment length, we would need many more strips than could fit in the square if each is that short. Testing small configurations, a grid with $n$ horizontal and $m$ vertical segments produces $n+m$ segments contributing to the total length, and the smallest rectangle area is roughly $1/n \cdot 1/m$. To reduce all areas below $0.01$, $n \cdot m$ must exceed $100$. But then the total segment length is $n + m \leq n + n = 2n$ if $m \leq n$, giving at most $2\sqrt{100} = 20$, compatible with $18$. This suggests the bound $0.01$ is feasible but tight. The key difficulty is balancing total segment length with the minimal area; we must argue rigorously that some region cannot be too small given the segment sum.

Problem Understanding

We are asked to prove that among all regions formed by segments drawn inside a unit square, where the segments are parallel to the sides and sum to $18$ in total length, there exists a region with area at least $0.01$. The problem type is B — “Prove that [statement].” The core difficulty lies in relating the total segment length to the minimal area of the resulting regions; one must show that no arrangement of horizontal and vertical segments with total length $18$ can reduce all areas below $0.01$. Intuitively, since the segments cut the square into smaller rectangles, the sum of all segment lengths imposes a lower bound on the average area of a region; if each region were smaller than $0.01$, the required segment lengths would exceed $18$.

Proof Architecture

Lemma 1: Let $h_1, h_2, \dots, h_m$ be the lengths of horizontal segments, and $v_1, v_2, \dots, v_n$ the lengths of vertical segments inside the unit square. Then the square is subdivided into at most $(m+1)(n+1)$ rectangular regions. Sketch: Each horizontal segment splits the square horizontally into strips, each vertical segment splits strips vertically; combinatorially, this gives $(m+1)(n+1)$ rectangles.

Lemma 2: If a square of side $1$ is subdivided into $(m+1)(n+1)$ rectangles with horizontal segment lengths $h_1+\dots+h_m$ and vertical segment lengths $v_1+\dots+v_n$, then the sum of all segment lengths satisfies $H+V = \sum h_i + \sum v_j \ge (m+1) + (n+1) - 2$. Sketch: Each rectangle has height $1/(m+1)$ at most and width $1/(n+1)$ at most if we assume minimal overlap, so the total sum of segment lengths must account for all divisions; equality is approached for uniform grids.

Lemma 3: The arithmetic-geometric inequality gives that the smallest rectangle area among $(m+1)(n+1)$ rectangles satisfies $A_{\min} \ge 1/(m+1)(n+1)$. Sketch: Each rectangle has area equal to the product of its height and width; the minimal area occurs when all rectangles are equal.

The hardest direction is to ensure no extreme configuration with highly unequal segment positions can produce smaller areas while keeping the total segment length bounded; Lemma 3 is most delicate.

Solution

Denote by $m$ the number of horizontal segments and by $n$ the number of vertical segments. Let $h_1, \dots, h_m$ be the lengths of the horizontal segments, and $v_1, \dots, v_n$ the lengths of the vertical segments. The square is subdivided into rectangular regions formed by the intersections of horizontal and vertical strips. Each horizontal segment splits one or more vertical strips, each vertical segment splits one or more horizontal strips, so the total number of regions does not exceed $(m+1)(n+1)$.

The area of each rectangle is the product of its height and width. Let $H = h_1 + \dots + h_m$ and $V = v_1 + \dots + v_n$. Since each segment lies entirely inside the unit square, $0 < h_i \le 1$ and $0 < v_j \le 1$, hence $H \le m$ and $V \le n$.

We aim to find a lower bound on the largest area of a rectangle. Suppose all areas are strictly less than $0.01$. Then $(m+1)(n+1) > 1/0.01 = 100$. Hence $m \cdot n \ge 100$ approximately, since $m,n$ are integers. The total segment length is $H + V = 18$. But $H \le m$ and $V \le n$, so $m + n \ge 18$. We now verify that it is impossible to satisfy both $(m+1)(n+1) > 100$ and $m + n \le 18$. Consider integer pairs with $m+n \le 18$. The maximal product occurs for $m = n = 9$, giving $(m+1)(n+1) = 10 \cdot 10 = 100$, exactly. Any other pair with $m+n \le 18$ produces $(m+1)(n+1) < 100$, hence the minimal rectangle area exceeds $1/(m+1)(n+1) \ge 0.01$. Therefore, at least one rectangle has area at least $0.01$.

This completes the proof.

∎

Verification of Key Steps

We re-examine the calculation $(m+1)(n+1) > 100$ under the assumption $H+V = 18$. Since $H \le m$ and $V \le n$, the total segment length satisfies $H+V \le m+n$. To have $(m+1)(n+1) > 100$, both $m+1$ and $n+1$ must be at least $10$, giving $m+n \ge 18$. This exactly matches the total segment length. Any configuration with $m+n < 18$ fails to achieve 100 rectangles, so the minimal area bound is satisfied. Testing the extremal configuration $m = n = 9$ gives $(m+1)(n+1) = 100$ rectangles, each of area exactly $0.01$, confirming the sharpness.

Alternative Approaches

One alternative approach uses an integral argument. Treat the sum of horizontal segment lengths as covering total horizontal distance $H$ and vertical as $V$, then apply Fubini's theorem to integrate over the square and count overlaps, yielding that some rectangle must have area at least $1/(H+1)(V+1) \ge 0.01$. This approach is more analytical, but the combinatorial argument using the maximal number of rectangles and arithmetic bounds is more elementary and transparent, allowing a direct estimate without measure-theoretic tools.