Prove that, if every three consecutive vertices of a convex $n{}$-gon, $n\geqslant 4$, span a triangle of area at least 1, then the area of the $n{}$-gon is (strictly) greater than $(n\log_2 n)/4-1/2.$ Radu Bumbăcea & Călin Popescu
Problem
Source: Stars of Mathematics 2020 (senior level)
Tags: combinatorics, romania
12.12.2021 12:27
Here's the beautiful official solution: For convenience, the area of the $n$-gon will be denoted by $[X_1X_2\ldots X_n],$ and the distance from a point $X$ to the line $YZ$ be denoted by $\text{dist}(X,YZ).$ Let $A_1A_2\ldots A_n$ be a convex $n$-gon such that $[A_iA_{i+1}A_{i+2}]\geq 1$ for all $i;$ as usual, indices are reduced modulo $n$. We will induct on $n$ to show that $[A_1A_2\ldots A_n]>(n\log_2 n)/4-1/2.$ The argument hinges on the two claims below, of which the first is a mere, but useful remark. Claim 1: $[A_iA_{i+1}A_j]\geq 1$ for all $i$ and for all $j\neq i,i+1.$ Proof: By convexity, $\text{dist}(A_j, A_iA_{i+1}) \geq \max \big(\text{dist} (A_{i-1}, A_iA_{i+1}), \text{dist} (A_{i+2}, A_iA_{i+1})\big),$ so we get the desired: \[[A_iA_{i+1}A_j] \geq \max \big([A_{i-1}A_i A_{i+1}], [A_i A_{i+1}A_{i+2})]\big) \geq 1.\]The next claim states that $[A_iA_{i+1}A_j] \geq (n-1)/4$ for some indices $i$ and $j.$ Without loss of generality, we may and will assume that $A_1 A_2 = \max A_i A_{i+1}.$ Write $d_i = \text{dist}(A_i, A_1A_2)$ and let $d_m = \max d_i.$ Claim 2: $[A_1A_2A_m]\geq\max(m-2,n-m+1)/2\geq(n-1)/4.$ Proof: Since each $[A_{i-1}A_iA_{i+1}] \geq 1,$ it is sufficient to show that \[[A_1A_2A_m]\geq\frac{1}{2}\max\bigg(\sum_{i=2}^{m-1}[A_{i-1}A_iA_{i+1}],\sum_{i=m+1}^{n+1}[A_{i-1}A_iA_{i+1}]\bigg).\]By convexity, $0=d_1=d_2<d_3<\cdots<d_{m-1}\leq d_m$ and $d_m\geq d_{m+1}>\cdots>d_n>d_{n+1}=d_{n+2}=0.$ With reference again to convexity, for each $i \neq m,$ the line through $A_i$ and parallel to $A_1A_2$ meets the segment $A_{i-1}A_{i+1}$ at some point $B_i$ so $[A_{i-1}A_iA_{i+1}]$ is equal to $[A_{i-1}A_i B_i] + [A_iA_{i+1}B_i].$ Therefore, for $i$ in the range $2$ through $m-1,$ we have \begin{align*} [A_{i-1}A_iA_{i+1}] &= [A_{i-1}A_iB_i]+[A_iA_{i+1}B_i]=\frac{1}{2}\cdot A_iB_i\cdot (d_i-d_{i-1})+\frac{1}{2}\cdot A_iB_i\cdot (d_{i+1}-d_i)\\ &= \frac{1}{2}\cdot A_iB_i\cdot (d_{i+1}-d_{i-1}) \leq\frac{1}{2}\cdot\max(A_{i-1}A_i,A_iA_{i+1})\cdot (d_{i+1}-d_{i-1})\\ &\leq \frac{1}{2}\cdot A_1A_2\cdot(d_{i+1}-d_{i-1}). \end{align*}Hence, by summing everything up, the latter yields \begin{align*} \sum_{i=2}^{m-1}[A_{i-1}A_iA_{i+1}] &\leq \frac{1}{2}\cdot A_1A_2\cdot\sum_{i=2}^{m-1}(d_{i+1}-d_{i-1})=\frac{1}{2}\cdot A_1A_2\cdot (d_m+d_{m+1})\\ &\leq A_1A_2\cdot d_m=2\cdot [A_1A_2A_m]. \end{align*}Similarly, $[A_{i-1}A_iA_{i+1}]\leq 1/2\cdot A_1A_2\cdot (d_{i-1}-d_{i+1})$ for $i$ in the range $m+1$ through $n+1,$ and we get \[\sum_{i=m+1}^{n+1}[A_{i-1}A_iA_{i+1}]\leq2\cdot [A_1A_2A_m]\]as above. By combining the two previous bounds for $[A_1A_2A_m],$ the proof of claim 2 is concluded. We are now in a position to show that $[A_1A_2\ldots A_n] > (n\log_2 n)/4-1/2$ by induction on $n$. For $3\leq n\leq6,$ write \[[A_1A_2\ldots A_n]=\sum_{i=2}^{n-1}[A_{i-1}A_iA_{i+1}]\]and refer to claim 1, to infer that $[A_1A_2\ldots A_n] \geq n - 2.$ Notice that $n-2>(n\log_2 n)/4-1/2$ for $3\leq n\leq 6.$ Now, assume that $n\geq 7$ and write $[A_1A_2\ldots A_n]=[A_1A_2A_m]+[A_2A_3\ldots A_m]+[A_1A_m\ldots A_n].$ For convenience, include non-degenerate segments as $2$-gons, whose areas are $0=(2\log_2 2)/4-1/2.$ By claim 2, $[A_1A_2A_m]$ is at least $(n-1)/4$ and by claim 1, every three consecutive vertices of the $(m-1)$-gon $A_2A_3\ldots A_m$ span a triangle of area at least 1, so \[[A_2A_3\ldots A_m]\geq\frac{1}{4}(m-1)\log_2(m-1)-\frac{1}{2}\]by the induction hypothesis (equality holds here if and only if $m=3$) and similarly, using claim 1 on $A_1A_m\ldots A_n,$ \[[A_1A_m\ldots A_n]\geq\frac{1}{4}(n+m-2)\log_2(n+m-2)-\frac{1}{2}\](equality holds here if and only if $m=n$). Therefore, by summing the three latter bounds, we get \begin{align*} [A_1A_2\ldots A_n] &\geq\frac{1}{4}(m-1)\log_2(m-1)-\frac{1}{2}+\frac{1}{4}(n+m-2)\log_2(n+m-2)-\frac{1}{2} \\ &= \frac{1}{4}(n-5)+\frac{1}{4}(m-1)\log_2(m-1)+\frac{1}{4}(n-m+2)\log_2(n-m+2) \\ &\geq \frac{1}{4}(n-5)+\frac{1}{4}\cdot 2\cdot \frac{1}{2}(n+1)\log_2\frac{n+1}{2} \quad (f(x)= x\log_2 x, \ x>0, \ \text{is convex}) \\ &=\frac{1}{4}(n+1)\log_2(n+1)-\frac{3}{2}>\frac{1}{4}n\log_2 n-\frac{1}{2} \end{align*}because \begin{align*} (n+1)\log_2(n+1)-n\log_2 n &=\log_2(n+1)+\log_2\bigg(n+\frac{1}{n}\bigg)^n \\ &=\log_2(n+1)+\log_2\bigg(1+n\cdot\frac{1}{n}+\cdots\bigg)>\log_2(n+1)+1 \\ &\geq \log_2(7+1)+1=4. \end{align*}