Maths Olympiad Prep

Library / /4 of 4

Combinatorics Difficulty 6.8 National olympiad Prove it Romania

Fix an integer n6n \ge 6 and consider nn coplanar lines, no two parallel and no three concurrent. These lines split the plane into unbounded polygonal regions and polygons with pairwise disjoint interiors. Two polygons are *non-adjacent* if they do not share a side. Show that there are at least 112(n3)(n2)\frac{1}{12}(n-3)(n-2) pairwise non-adjacent polygons with the same number of sides each.

Cristian Șăvescu

Solution

Consider the obvious geometric plane graph associated with a generic nn-line configuration in a plane (no two lines are parallel and no three are concurrent). This graph has exactly (n2)=12n(n1)\binom{n}{2} = \frac{1}{2}n(n-1) vertices, exactly e=n2e = n^2 edges and exactly f=12n(n+1)+1f = \frac{1}{2}n(n+1)+1 faces.
Let fkf_k be the number of kk-edge faces (faces with exactly kk edges), so f=k=2nfkf = \sum_{k=2}^{n} f_k (no face has more than nn edges). Fix an integer mm in the range 4 through nn, to write
2n2=2e=k=2nkfk=k=2m1kfk+k=mnkfkk=2m1kfk+mk=mnfk=k=2m1kfk+m(fk=2m1fk)=k=2m1(km)fk+mf, \begin{align*} 2n^2 = 2e &= \sum_{k=2}^{n} k f_k = \sum_{k=2}^{m-1} k f_k + \sum_{k=m}^{n} k f_k \ge \sum_{k=2}^{m-1} k f_k + m \sum_{k=m}^{n} f_k \\ &= \sum_{k=2}^{m-1} k f_k + m \left( f - \sum_{k=2}^{m-1} f_k \right) = \sum_{k=2}^{m-1} (k-m) f_k + mf, \end{align*}
so
2n2k=2m1(km)fk+12m(n2+n+2), 2n^2 \geq \sum_{k=2}^{m-1} (k-m)f_k + \frac{1}{2}m(n^2+n+2),
wherefrom
k=2m1(mk)fk12m(n2+n+2)2n2=12((m4)n2+mn+2m). \sum_{k=2}^{m-1} (m-k)f_k \geq \frac{1}{2}m(n^2+n+2) - 2n^2 = \frac{1}{2}((m-4)n^2 + mn + 2m).
Next, write fk=bk+ukf_k = b_k + u_k, where bkb_k and uku_k are the numbers of bounded and unbounded kk-faces, respectively. Thus, bkb_k is the number of kk-gons. Clearly, b2=0b_2 = 0 and k=2nuk=2n\sum_{k=2}^{n} u_k = 2n, so
k=2m1(mk)fk=k=3m1(mk)bk+k=2m1(mk)ukk=3m1(mk)bk+(m2)k=3m1ukk=3m1(mk)bk+(m2)k=2nuk=k=3m1(mk)bk+2(m2)n. \begin{align*} \sum_{k=2}^{m-1} (m-k)f_k &= \sum_{k=3}^{m-1} (m-k)b_k + \sum_{k=2}^{m-1} (m-k)u_k \le \\ &\le \sum_{k=3}^{m-1} (m-k)b_k + (m-2) \sum_{k=3}^{m-1} u_k \le \\ &\le \sum_{k=3}^{m-1} (m-k)b_k + (m-2) \sum_{k=2}^{n} u_k = \sum_{k=3}^{m-1} (m-k)b_k + 2(m-2)n. \end{align*}
Consequently,
k=3m1(mk)bkk=2m1(mk)fk2(m2)n12((m4)n2+mn+2m)2(m2)n==12((m4)n2(3m8)n+2m)=12((m4)nm)(n2), \begin{align*} \sum_{k=3}^{m-1} (m-k)b_k &\ge \sum_{k=2}^{m-1} (m-k)f_k - 2(m-2)n \ge \\ &\ge \frac{1}{2}((m-4)n^2 + mn + 2m) - 2(m-2)n = \\ &= \frac{1}{2}((m-4)n^2 - (3m-8)n + 2m) = \frac{1}{2}((m-4)n - m)(n-2), \end{align*}
so
max(b3,,bm1)12((m4)nm)(n2)(m3)++1=((m4)nm)(n2)(m3)(m2). \max(b_3, \dots, b_{m-1}) \ge \frac{1}{2} \cdot \frac{((m-4)n - m)(n-2)}{(m-3) + \dots + 1} = \frac{((m-4)n - m)(n-2)}{(m-3)(m-2)}.
The coefficient of n2n^2 in the lower bound is maximized at m=5m=5 and m=6m=6, so
max(b3,b4)16(n5)(n2)andmax(b3,b4,b5)16(n3)(n2). \max(b_3, b_4) \ge \frac{1}{6}(n-5)(n-2) \quad \text{and} \quad \max(b_3, b_4, b_5) \ge \frac{1}{6}(n-3)(n-2).

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.