Maths Olympiad Prep

Library / Rioplatense Mathematical Olympiad /6 of 41

Rioplatense Mathematical Olympiad

Geometry Difficulty 5.5 AIME, harder Prove it Argentina

A set of points is called antiparallelogram if no four of them are the vertices of a parallelogram. Given a set SS of 20232023 points on the plane, no three of them on the same line, prove that there is a subset of SS containing 1717 points which is antiparallelogram.

Solution

We run a greedy algorithm to find an antiparallelogram set XX contained in SS. Set X=∅X = \emptyset to start. In each step, verify if there are points in S∖XS \setminus X that can be incorporated to XX while keeping it antiparallelogram. If so, choose any one of those points, add it to XX, and repeat. Else, the algorithm stops. At the end we have an antiparallelogram set XX with kk points such that for any point p∈S∖Xp \in S \setminus X, X∪{p}X \cup \{p\} is not antiparallelogram. In other words, for any p∈S∖Xp \in S \setminus X, there are q,r,s∈Xq, r, s \in X such that p,q,r,sp, q, r, s are the vertices of a parallelogram. But notice that for any q,r,sq, r, s there are exactly 33 such pp's, so the following inequality must hold:
2023−k≤3(k3). 2023 - k \le 3 \binom{k}{3}.
However 3(163)+16=1696<20233\binom{16}{3} + 16 = 1696 < 2023. Thus, k≥17k \ge 17, and we are done.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.