Skip to main content
OlympiadHQ

Browse · MathNet

Print

Rioplatense Mathematical Olympiad

Argentina geometry

Problem

A set of points is called antiparallelogram if no four of them are the vertices of a parallelogram. Given a set of points on the plane, no three of them on the same line, prove that there is a subset of containing points which is antiparallelogram.
Solution
We run a greedy algorithm to find an antiparallelogram set contained in . Set to start. In each step, verify if there are points in that can be incorporated to while keeping it antiparallelogram. If so, choose any one of those points, add it to , and repeat. Else, the algorithm stops. At the end we have an antiparallelogram set with points such that for any point , is not antiparallelogram. In other words, for any , there are such that are the vertices of a parallelogram. But notice that for any there are exactly such 's, so the following inequality must hold: However . Thus, , and we are done.

Techniques

Combinatorial GeometryColoring schemes, extremal arguments