We are given $2021$ points on a plane, no three of which are collinear. Among any $5$ of these points, at least $4$ lie on the same circle. Is it necessarily true that at least $2020$ of the points lie on the same circle?
Problem
Source: Baltic Way 2021, Problem 9
Tags: combinatorics, combinatorics proposed
x3yukari
17.11.2021 03:30
We claim the answer is yes. Define an "adequate" arrangement of points as one that satisfies the given condition that at least $4$ out of any $5$ points lie on the same circle. Define a "rotary" arrangement of $n$ points as one that has at least $n-1$ points lying on the same circle.
Notice that if we remove a point from an adequate arrangement, it remains adequate. So suppose there exists an adequate, non-rotary arrangement of $2021$ points. By continually removing points from the arrangement, it follows that there must exist an adequate, non-rotary arrangement of $7$ points.
Case 1: $4$ points are cyclic, and the other $3$ points do not lie on the same circle. Let the four cyclic points be $p_1, p_2, p_3, p_4$ and the non-cyclic points be $q_1, q_2, q_3.$
We take cases of $5$ points starting from those that contain $q_1, q_2, q_3.$
Consider $q_1, q_2, q_3, p_1, p_2.$ Then we consider the case where $q_1, q_2, q_3, p_1$ are cyclic. From here the cases with $q_1, q_2, q_3, p_1, p_3$ and $q_1, q_2, q_3, p_1, p_4$ are also satisfied.
Consider $q_1, q_2, q_3, p_2, p_3.$ Then we consider the case where $q_1, q_2, q_3, p_2$ are cyclic. From here the case with $q_1, q_2, q_3, p_2, p_4$ is also satisfied.
It remains to consider $q_1, q_2, q_3, p_3, p_4.$ We can't have all three $q$ points and a $p$ point be cyclic because we already have two intersections of the circumcircle of $q$ defined by $p_1$ and $p_1$ so we only have to consider WLOG that $q_1, q_2, p_3, p_4$ are cyclic. (Note that this case is considering one of the $p$ on each of the two intersections of the circumcircle of the three $q$ with the circumcircle of $p.$)
But now consider $q_1, q_3, p_1, p_3, p_4.$ We can verify that for any selection of four points, the circumcircle of three is already defined, and the fourth point lies on a different circle (also already defined). Moreover, the two intersections of the circles on which the fourth point could lie are already defined by a different point, either $q_2$ or $p_2.$
We go back to the case considering $q_1, q_2, q_3, p_2, p_3.$ We now consider WLOG if $q_1, q_2, p_2, p_3$ are cyclic. Then we consider $q_1, q_2, q_3, p_2, p_4,$ and since two circles have at most two intersections, we need to have two different $q$ points cyclic, so WLOG we consider if $q_1, q_3, p_2, p_4$ are cyclic. Similarly for $q_1, q_2, q_3, p_3, p_4$ we consider $q_2, q_3, p_2, p_4$ cyclic (since we're considering that we only consider one intersection of the circumcircle of the three $q$ with the circumcircle of $p,$ namely, $p_1.$) But now we consider $p_1, p_2, p_3, q_2, q_3.$ We can again verify (similarly to the previous case) that it is impossible to have any four of these points concyclic based on how we defined them in this case.
Finally, we consider the case where we do not consider any intersection of the circumcircles of $q$ and $p.$ But notice that there are $6$ necessary pairs of points $p$ that need to be concyclic with two $q.$ For every pair of $q,$ there are at most two corresponding pairs of $p$ such that the two pairs are concyclic; otherwise there would be more than four points (note that since three points define a circle, the location of the fourth concyclic point is defined by the second intersection of the circumcircle of all $p$ and the circumcircle of the pair of the $q$ and the chosen $p$). Thus for every one of the three pairs of of $q$ there are exactly two corresponding pairs of $p,$ with four different endpoints in total, such that the two pairs are concyclic. But also note that as we shrink or expand the circle through two points, the two intersections of the circle travel along the circle in the same direction, and thus the lines connecting the two corresponding pairs of $p$ never intersect. Thus we can consider the diagonals of the convex quadrilateral $p_1p_2p_3p_4,$ which intersect, and since for each pair of $q,$ there are two corresponding pairs of $p$ that don't share endpoints and whose segments connecting each pair do not intersect, we have a contradiction.
Case 2: $5$ points are cyclic, and the other $2$ points do not lie on the same circle. Let the four cyclic points be $p_1, p_2, p_3, p_4, p_5$ and the non-cyclic points be $q_1, q_2.$
Consider $q_1, q_2, p_1, p_2, p_3.$ Notice that if we consider both $q$ in the five points, they both necessarily have to be in the concyclic four points, because we defined neither as concyclic with all three of the chosen $p.$ So WLOG assume $q_1, q_2, p_1, p_2$ are concyclic. Now consider $q_1, q_2, p_3, p_4, p_5.$ WLOG assume $q_1, q_2, p_3, p_4$ are concyclic. But now consider $q_1, q_2, p_1, p_3, p_5.$ Since the second intersections of the circumcircles of $q_1q_2p_1$ and $q_1q_2p_3$ are already defined, and $q_1q_2p_5$ cannot pass through either of them due to this as well, we have a contradiction.
So there cannot exist an adequate, non-rotary arrangement of $7$ points and thus there cannot exist an adequate, non-rotary arrangement of $2021$ points. Thus any adequate arrangement of $2021$ points must have $2020$ points lying on the same circle, which indeed is adequate, so we're done.
btw, I hope all of you who took the AMC B's today in the US did well~ <3
phoenixfire
04.07.2022 17:19
Let $\omega$ be a circle with 4 points say $A, B, C, D$. We use the following lemma: If $P, Q$ are points we on $\omega$ then $A, B, P, Q$ and $C, D, P, Q$ are concyclic.
Consider $A, B, C, P, Q,$ 4 of these must be concyclic. If $P, Q$ both do not lie in this circle implies they belong to $\omega$ implying a contradiction. Thus WLOG let $A B P Q$ be concyclic. Then consider $A, C, D, P, Q$. Again the circle must include both $P Q$. And $A$ cannot be the of the points implying $C, D, P, Q$ are concyclic.
If $\omega$ contains only $A, B, C, D$ then by the lemma for any other points $E$ and $F$, $A B E F$ and $C D E F$ are concyclic. However, we have only 3 points $F$ for a fixed $E$. This is because $E$ and two of $A, D, C, D$ are concyclic on one circle and the other two are concyclic on another circle. And $\binom{4}{2}=6$ implying that we have only $3$ possible partitions of $\{A,B,C,D\}$ into two sets of two elements. Clearly, as $2021>5+3$, we have a contradiction.
By above we have more than 4 points on $\omega$. Now if $\omega$ contains a fifth point $E$ along with $A, B, C, D$, assume that we have points $R,S$ not on $w$. Then by our lemma $ABRS$ and $CDRS$ are concyclic. Similarly, $ABRS$ and $CERS$ are cyclic. This cannot be possible as $A, B, C$ do not lie on the circumcircle of triangle $ERS$. Thus we have at most one point not on $\omega$ implying that we have at most $2020$ points on it.
This solution shows that for a general $n \geq 9$, the answer is $n-1$.
arzhang2001
01.09.2022 15:17
Yes . It's true . Because if exist 7 point like $A,B,C,D,F,G,H$ such that if we choose 5 if them then all of them doesn't belong to a circle and $ABCD$be cyclic . So Now we can conclude we can choose 5 of them such that problem conditions be wrong .(why?) So there is no 7 point like this . And you can see if we haven't atleast a circle which contain $n-1$ of them we have contradiction.