Maths Olympiad Prep

Library / /251 of 520

Combinatorics Difficulty 6.4 National olympiad Prove it

Let n4n \geq 4 points in the plane, no three of them are collinear. Prove that the number of parallelograms of area 1, formed by these points, is at most n23n4\frac{n^{2}-3 n}{4}.

Solution

Fix a direction in the plane. We cannot have three points in the same line parallel to the direction so suppose that in that direction there are kk pairs of points, each pair belonging to a parallel line to the fixed direction. Then there are at most k1k-1 parallelograms of area 1 formed by these kk pairs of points.
Summing over all directions we get that the number of parallelograms of area 1 are at most (n2)s\binom{n}{2}-s where ss is the number of different directions. But in that way we count every parallelogram two times, so the that the number of parallelograms of area 1 is at most (n2)s2\frac{\binom{n}{2}-s}{2}. We will prove that sns \geq n. Indeed, taking the convex hull of the nn points, let xx be a point on the boundary of the convex hull. Because the convex hull has at least three points on its boundary, we can take two points which are neighbors of xx in the convex hull, say y,zy, z these points. Then every segment starting from xx has different direction from yzy z. So we have at least n1+1=nn-1+1=n different directions. So the number of parallelograms is at most (n2)n2=n23n4\frac{\binom{n}{2}-n}{2}=\frac{n^{2}-3 n}{4}.

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.