In the plane, there are $n$ points ($n\ge 4$) where no 3 of them are collinear. Let $A(n)$ be the number of parallelograms whose vertices are those points with area $1$. Prove the following inequality: $A(n)\leq \frac{n^2-3n}{4}$ for all $n\ge 4$
Problem
Source: Greece National Olympiad Problem 4
Tags: parallelogram, inequalities, combinatorics
03.03.2018 23:45
Consider all line segments formed by the points and partition them into groups of parallel segments. As no 3 points are collinear, any segment between any two of the points is a side of at most 2 parallelograms of unit area. On the other hand, consider all groups of segments. In each group, the topmost and bottommost segment (if we orient the segment to be horizontal) is a part of at most one parallelogram of unit area, and if there is only one segment it is not a part of any parallelogram. There are at least $n$ groups, as for three consecutive points $X,Y,Z$ on the convex hull of the points there are all lines emanating from $Y$ and $XZ$, no two of which are parallel. Hence, we subtract off $2n$, leaving $2\binom n2-2n=n^2-3n$ segment -- parallelogram pairs. Each parallelogram is a part of 4 of these, yielding the result.
05.03.2018 18:36
Here's a bound that is slightly better, for sufficiently large $n$: Suppose there exists total $k$ such parallelograms. We note some propositions whose proofs are not hard: Each segment can be a side of at most two such parallelograms. Each segment on convex hull can be a side of at most one such parallelograms, and can't be diagonal of any of such parallelogram. Diagonal of any of such parallelogram can't be a side of any other such parallelogram. Each segment can be a diagonal of at most two such parallelograms. So, $k$ parallelograms, each has two diagonals, contributes at least $k$ distinct diagonals. Now, we count the number of pairing $(s,\mathcal{Q})$ where $s$ is a side of $\mathcal{Q}$, which is one of such $k$ parallelogram. Each of $k$ parallelograms has $4$ sides, so there're $4k$ such pairings. On the other hand, $s$ must be one of non-diagonal sides. Suppose the convex hull is a $c$-gon. So, the number of such pairing is at most $2\cdot \left( \binom{n}{2}-k-c\right) +c$. Hence, $$2\cdot \left( \binom{n}{2}-k\right) -c \geqslant 4k\implies \frac{n^2-n-c}{6}\geqslant k\implies \left\lfloor \frac{n^2-n-c}{6}\right\rfloor \geqslant k.$$Since $ \left\lfloor \frac{n^2-n-c}{6}\right\rfloor \leqslant \left\lfloor \frac{n^2-n-3}{6}\right\rfloor \leqslant \frac{n^2-3n}{4}$ is true for all $n\geqslant 4$, we are done.
31.07.2019 14:55
This was the Balkan BMO Shortlist 2017 C3 problem.
02.08.2019 23:30
This was created by me (Silouanos Brazitikos) and the proposed bound was obtained by Demetres Christophides (aka Demetres). The order $O(n^2)$ is optimal.
13.09.2024 05:22
I wonder if we can prove it without "no 3 of them are conlinear".