Nineteenth IMAR Mathematical Competition

Consider the obvious geometric plane graph associated with a generic $n$-line configuration in a plane (no two lines are parallel and no three are concurrent). This graph has exactly $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{1}{2}n(n-1)$ vertices, exactly $e=n^2$ edges and exactly $f=\frac{1}{2}n(n+1)+1$ faces. Let $f_k$ be the number of $k$-edge faces (faces with exactly $k$ edges), so $f={\sum }_{k=2}^n{f}_k$ (no face has more than $n$ edges). Fix an integer $m$ in the range 4 through $n$, to write $$\begin{array}{rl}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{array}$$ so $$2n^2\ge \sum _{k=2}^{m-1}(k-m)f_k+\frac{1}{2}m(n^2+n+2),$$ wherefrom $$\sum _{k=2}^{m-1}(m-k)f_k\ge \frac{1}{2}m(n^2+n+2)-2n^2=\frac{1}{2}((m-4)n^2+mn+2m).$$ Next, write $f_k=b_k+u_k$, where $b_k$ and $u_k$ are the numbers of bounded and unbounded $k$-faces, respectively. Thus, $b_k$ is the number of $k$-gons. Clearly, $b_2=0$ and ${\sum }_{k=2}^n{u}_k=2n$, so $$\begin{array}{rl}\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{array}$$ Consequently, $$\begin{array}{rl}\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{array}$$ so $$\max (b_3,\dots ,b_{m-1})\ge \frac{1}{2}\cdot \frac{((m-4)n-m)(n-2)}{(m-3)+\cdots +1}=\frac{((m-4)n-m)(n-2)}{(m-3)(m-2)}.$$ The coefficient of $n^2$ in the lower bound is maximized at $m=5$ and $m=6$, so $$\max (b_3,b_4)\ge \frac{1}{6}(n-5)(n-2)\text{and}\max (b_3,b_4,b_5)\ge \frac{1}{6}(n-3)(n-2).$$