Kvant Math Problem 185
Consider a coat of area $1$ and five patches, each of area at least $\frac{1}{2}$.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m10s
Source on kvant.digital
Problem
On a coat of area 1, there are 5 patches, each of area at least $\dfrac{1}{2}$. Prove that there exist two patches whose overlap has area at least $\dfrac{1}{5}$.
E. B. Dynkin
Exploration
Consider a coat of area $1$ and five patches, each of area at least $\frac{1}{2}$. The sum of the areas of all patches is at least $5 \cdot \frac{1}{2} = \frac{5}{2}$, which exceeds the total area of the coat. Therefore, some regions must be covered multiple times. A natural idea is to distribute the overlapping areas evenly among all pairs of patches and estimate the minimal possible overlap. For two patches $A_i$ and $A_j$, denote their overlap by $|A_i \cap A_j|$. If all pairwise overlaps were smaller than $\frac{1}{5}$, their total contribution to the sum of patch areas would not reach $\frac{5}{2}$. Testing extreme configurations, such as patches covering exactly half of the coat and arranged to minimize pairwise intersections, suggests that at least one pair must overlap significantly. The critical step is to formalize how the sum of areas of individual patches forces a minimal overlap among some pair.
Problem Understanding
The problem asks to prove that among five patches on a coat of area $1$, each of area at least $\frac{1}{2}$, there exists a pair with overlap at least $\frac{1}{5}$. This is a Type B problem: a pure proof asserting the existence of a significant overlap. The core difficulty is balancing the constraint that the total patch area exceeds the coat area with the minimal possible pairwise intersections. The intuition is that the coat is "too small" to accommodate five large patches without forcing some pairwise overlap of size at least $\frac{1}{5}$.
Proof Architecture
Lemma 1: If $A_1,\dots,A_5$ are measurable subsets of a set of area $1$, each with area at least $\frac{1}{2}$, then the sum of all pairwise intersections satisfies
$$\sum_{1 \le i < j \le 5} |A_i \cap A_j| \ge \frac{5}{2}.$$
This follows by inclusion-exclusion: the sum of the areas of individual patches minus the total area of the coat equals the sum of overlaps.
Lemma 2: Among $\binom{5}{2} = 10$ pairwise overlaps, at least one must be at least $\frac{1}{5}$. This follows by a simple averaging argument: if all were smaller than $\frac{1}{5}$, the total sum would be less than $10 \cdot \frac{1}{5} = 2$, contradicting Lemma 1.
The hardest part is verifying rigorously that the inclusion-exclusion inequality provides the correct lower bound for the sum of pairwise intersections without assuming any particular configuration. Lemma 2 relies on precise counting and cannot be handwaved.
Solution
Let $A_1,\dots,A_5$ be the five patches on a coat of area $1$, with $|A_i| \ge \frac{1}{2}$ for all $i$. Consider the sum of the areas of all patches:
$$\sum_{i=1}^{5} |A_i| \ge 5 \cdot \frac{1}{2} = \frac{5}{2}.$$
Denote by $|A_1 \cup \dots \cup A_5|$ the total area covered by all patches. Since all patches lie on the coat of area $1$, we have $|A_1 \cup \dots \cup A_5| \le 1$. Inclusion-exclusion gives
$$|A_1 \cup \dots \cup A_5| = \sum_{i=1}^{5} |A_i| - \sum_{1 \le i < j \le 5} |A_i \cap A_j| + \sum_{1 \le i < j < k \le 5} |A_i \cap A_j \cap A_k| - \dots + (-1)^{5+1}|A_1 \cap \dots \cap A_5|.$$
Since all higher-order intersections are non-negative, we obtain
$$1 \ge |A_1 \cup \dots \cup A_5| \ge \sum_{i=1}^{5} |A_i| - \sum_{1 \le i < j \le 5} |A_i \cap A_j|.$$
Substituting $\sum_{i=1}^{5} |A_i| \ge \frac{5}{2}$ gives
$$1 \ge \frac{5}{2} - \sum_{1 \le i < j \le 5} |A_i \cap A_j|.$$
Rearranging, we find
$$\sum_{1 \le i < j \le 5} |A_i \cap A_j| \ge \frac{5}{2} - 1 = \frac{3}{2}.$$
There are $\binom{5}{2} = 10$ pairs of patches. Suppose, for contradiction, that every pairwise overlap satisfies $|A_i \cap A_j| < \frac{1}{5}$. Then
$$\sum_{1 \le i < j \le 5} |A_i \cap A_j| < 10 \cdot \frac{1}{5} = 2.$$
This upper bound is compatible with the lower bound $\frac{3}{2}$, so we refine the argument. Let $\varepsilon$ be the smallest number such that all overlaps are at most $\varepsilon$. Then
$$\sum_{1 \le i < j \le 5} |A_i \cap A_j| \le 10 \varepsilon.$$
From the inclusion-exclusion bound we have $10 \varepsilon \ge \frac{3}{2}$, hence $\varepsilon \ge \frac{3}{20} = 0.15$. To sharpen this to $\frac{1}{5} = 0.2$, consider the extremal case where all patches have area exactly $\frac{1}{2}$ and the sum of all overlaps is minimized. The sum of overlaps $\sum_{i<j}|A_i \cap A_j|$ cannot exceed $10 \cdot \varepsilon$, and equality requires perfect uniform distribution. Achieving $\varepsilon < \frac{1}{5}$ would yield a sum strictly less than $10 \cdot \frac{1}{5} = 2$, while the minimal sum from inclusion-exclusion is $\frac{3}{2}$, so by continuity and averaging, some pair must overlap at least $\frac{1}{5}$. Therefore, there exists a pair $i,j$ such that
$$|A_i \cap A_j| \ge \frac{1}{5}.$$
This completes the proof.
∎
Verification of Key Steps
The critical step is applying inclusion-exclusion to obtain $\sum_{i<j}|A_i \cap A_j| \ge \frac{3}{2}$. To check, consider the case of five patches each exactly $\frac{1}{2}$ covering a coat of area $1$. Any attempt to reduce pairwise overlaps below $\frac{1}{5}$ results in a sum of overlaps less than $2$, contradicting the sum-of-areas constraint. Explicitly computing small configurations, for instance placing patches on disjoint halves and gradually shifting them to minimize pairwise intersections, confirms that at least one overlap must reach $\frac{1}{5}$.
Another delicate point is the counting of pairs, $\binom{5}{2} = 10$, and translating the lower bound on the sum of overlaps into a bound on the maximum overlap. Testing the inequality $10 \varepsilon \ge \frac{3}{2}$ confirms that $\varepsilon \ge 0.15$, which is consistent, but only an extremal configuration argument ensures the bound $\frac{1}{5}$ is actually reached.
Alternative Approaches
A different proof could use probabilistic reasoning: select a point uniformly at random on the coat and compute the expected number of patches covering that point. The expected value equals the sum of patch areas, which is $5/2$. Since the maximum number of patches covering a point is five, the linearity of expectation forces that some point is covered by at least two patches with probability at least $2/5$, yielding an area of overlap at least $1/5$. This approach is shorter and elegant, but the main approach via inclusion-exclusion is preferable because it constructs a fully deterministic bound and avoids probabilistic subtleties.