Maths Olympiad Prep

Library / /2 of 18

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 SXS \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 pSXp \in S \setminus X, X{p}X \cup \{p\} is not antiparallelogram. In other words, for any pSXp \in S \setminus X, there are q,r,sXq, 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:
2023k3(k3). 2023 - k \le 3 \binom{k}{3}.
However 3(163)+16=1696<20233\binom{16}{3} + 16 = 1696 < 2023. Thus, k17k \ge 17, and we are done.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.