Maths Olympiad Prep

Library / /498 of 520

Geometry Difficulty 7.9 National olympiad, round 2 Prove it

Show that there is an absolute constant c<1c < 1 with the following property: whenever P\mathcal P is a polygon with area 11 in the plane, one can translate it by a distance of 1100\frac{1}{100} in some direction to obtain a polygon Q\mathcal Q, for which the intersection of the interiors of P\mathcal P and Q\mathcal Q has total area at most cc.

[i]Linus Hamilton[/i]

Solution

1. Initial Setup and Definitions:
- Let P\mathcal{P} be a polygon with area 11.
- Define the function f(v)=1P(P+v)f(\vec{v}) = 1 - |\mathcal{P} \cap (\mathcal{P} + \vec{v})| for a translation vector v\vec{v}.
- We aim to show that there exists a constant c<1c < 1 such that for some translation vector v\vec{v} with v=1100|\vec{v}| = \frac{1}{100}, the area of the intersection of P\mathcal{P} and its translation Q=P+v\mathcal{Q} = \mathcal{P} + \vec{v} is at most cc.

2. **Subadditivity of ff:
-
Claim:** f(u+v)f(u)+f(v)f(\vec{u} + \vec{v}) \leq f(\vec{u}) + f(\vec{v}) for any vectors u\vec{u} and v\vec{v}.
- Proof:
f(u+v)=1P(P+u+v)=PP(P+u+v)=P(P+u+v)=P(P+u)+(P(P+u))(P+u+v)P(P+u)+(P+u)(P+u+v)=f(u)+f(v). \begin{aligned} f(\vec{u} + \vec{v}) &= 1 - |\mathcal{P} \cap (\mathcal{P} + \vec{u} + \vec{v})| \\ &= |\mathcal{P}| - |\mathcal{P} \cap (\mathcal{P} + \vec{u} + \vec{v})| \\ &= |\mathcal{P} \setminus (\mathcal{P} + \vec{u} + \vec{v})| \\ &= |\mathcal{P} \setminus (\mathcal{P} + \vec{u})| + |(\mathcal{P} \cap (\mathcal{P} + \vec{u})) \setminus (\mathcal{P} + \vec{u} + \vec{v})| \\ &\leq |\mathcal{P} \setminus (\mathcal{P} + \vec{u})| + |(\mathcal{P} + \vec{u}) \setminus (\mathcal{P} + \vec{u} + \vec{v})| \\ &= f(\vec{u}) + f(\vec{v}). \end{aligned}
This proves the subadditivity of ff. \blacksquare

3. Reduction to Smaller Translations:
- For some ε>0\varepsilon > 0 and a vector u\vec{u} with u150|\vec{u}| \leq \frac{1}{50}, if f(u)>εf(\vec{u}) > \varepsilon, we can find vectors v1\vec{v_1} and v2\vec{v_2}, both with v1=v2=1100|\vec{v_1}| = |\vec{v_2}| = \frac{1}{100}, such that u=v1+v2\vec{u} = \vec{v_1} + \vec{v_2}.
- By the subadditivity of ff, we have:
f(u)f(v1)+f(v2). f(\vec{u}) \leq f(\vec{v_1}) + f(\vec{v_2}).
If f(u)>εf(\vec{u}) > \varepsilon, then f(v1)+f(v2)>εf(\vec{v_1}) + f(\vec{v_2}) > \varepsilon, implying that at least one of f(v1)f(\vec{v_1}) or f(v2)f(\vec{v_2}) is greater than ε2\frac{\varepsilon}{2}.

4. Main Lemma:
- Lemma: Let SS be a finite subset of Z+\mathbb{Z}^+, and nZ+n \in \mathbb{Z}^+. Then
1na=1nS(S+a)min{S,n}2. \frac{1}{n} \sum_{a=1}^n |S \setminus (S + a)| \geq \frac{\min \{|S|, n\}}{2}.
- Proof:
- Consider the number of pairs (i,j)(i, j) such that 0<jin0 < j - i \leq n, iSi \in S, and jSj \notin S (call such pairs *good*).
- Let k=min{S,n}k = \min \{|S|, n\} and let a1<a2<<aka_1 < a_2 < \ldots < a_k be the kk greatest elements of SS.
- For each aia_i, the number of good pairs (ai,u)(a_i, u) is at least n(ki)n - (k - i).
- Summing over all kk elements, we get:
i=1k(n(ki))=nkk(k1)2=k(2nk+1)2nk2. \sum_{i=1}^k (n - (k - i)) = nk - \frac{k(k-1)}{2} = \frac{k(2n - k + 1)}{2} \geq \frac{nk}{2}.
- Thus, the number of good pairs is at least nk2\frac{nk}{2}, proving the lemma. \blacksquare

5. Approximation by a Grid:
- Grid the plane so that a 1×11 \times 1 square is divided into a 50N×50N50N \times 50N grid, where NN is very large.
- Define rows and columns as *weird* if they have at most NN cells and *normal* otherwise.
- Consider three cases:
1. If weird rows have at least 49N249N^2 cells, translating the polygon rightward by kN\frac{k}{N} for some kk will subtract an area of at least 49N22\frac{49N^2}{2} cells.
2. If there are at least 49N49N normal rows, translating by kN\frac{k}{N} for some kk will subtract an area of at least 49NN249N \cdot \frac{N}{2} cells.
3. If neither of the above cases holds, the number of cells in normal columns is at most 2450N2+o(N2)2450N^2 + o(N^2), which contradicts the total number of cells being 2500N2+o(N)2500N^2 + o(N).

6. Conclusion:
- The problem is solved for ε<495000\varepsilon < \frac{49}{5000}, implying c1ε2>14910000c \geq 1 - \frac{\varepsilon}{2} > 1 - \frac{49}{10000}.

The final answer is c14910000c \geq 1 - \frac{49}{10000}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.