GeometryDifficulty 7.9National olympiad, round 2Prove it
Show that there is an absolute constant c<1 with the following property: whenever P is a polygon with area 1 in the plane, one can translate it by a distance of 1001 in some direction to obtain a polygon Q, for which the intersection of the interiors of P and Q has total area at most c.
[i]Linus Hamilton[/i]
Solution
1. Initial Setup and Definitions: - Let P be a polygon with area 1. - Define the function f(v)=1−∣P∩(P+v)∣ for a translation vector v. - We aim to show that there exists a constant c<1 such that for some translation vector v with ∣v∣=1001, the area of the intersection of P and its translation Q=P+v is at most c.
2. **Subadditivity of f: - Claim:** f(u+v)≤f(u)+f(v) for any vectors u and v. - Proof: f(u+v)=1−∣P∩(P+u+v)∣=∣P∣−∣P∩(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). This proves the subadditivity of f. ■
3. Reduction to Smaller Translations: - For some ε>0 and a vector u with ∣u∣≤501, if f(u)>ε, we can find vectors v1 and v2, both with ∣v1∣=∣v2∣=1001, such that u=v1+v2. - By the subadditivity of f, we have: f(u)≤f(v1)+f(v2). If f(u)>ε, then f(v1)+f(v2)>ε, implying that at least one of f(v1) or f(v2) is greater than 2ε.
4. Main Lemma: - Lemma: Let S be a finite subset of Z+, and n∈Z+. Then n1a=1∑n∣S∖(S+a)∣≥2min{∣S∣,n}. - Proof: - Consider the number of pairs (i,j) such that 0<j−i≤n, i∈S, and j∈/S (call such pairs *good*). - Let k=min{∣S∣,n} and let a1<a2<…<ak be the k greatest elements of S. - For each ai, the number of good pairs (ai,u) is at least n−(k−i). - Summing over all k elements, we get: i=1∑k(n−(k−i))=nk−2k(k−1)=2k(2n−k+1)≥2nk. - Thus, the number of good pairs is at least 2nk, proving the lemma. ■
5. Approximation by a Grid: - Grid the plane so that a 1×1 square is divided into a 50N×50N grid, where N is very large. - Define rows and columns as *weird* if they have at most N cells and *normal* otherwise. - Consider three cases: 1. If weird rows have at least 49N2 cells, translating the polygon rightward by Nk for some k will subtract an area of at least 249N2 cells. 2. If there are at least 49N normal rows, translating by Nk for some k will subtract an area of at least 49N⋅2N cells. 3. If neither of the above cases holds, the number of cells in normal columns is at most 2450N2+o(N2), which contradicts the total number of cells being 2500N2+o(N).
6. Conclusion: - The problem is solved for ε<500049, implying c≥1−2ε>1−1000049.
The final answer is c≥1−1000049.
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.