$60$ points lie on the plane, such that no three points are collinear. Prove that one can divide the points into $20$ groups, with $3$ points in each group, such that the triangles ( $20$ in total) consist of three points in a group have a non-empty intersection.
Problem
Source: 2019 China TST Test 4 P3
Tags: combinatorics, geometry, combinatorial geometry
30.03.2019 19:58
The idea is to locate a point $P$ for which, when we draw any line $l$ through $P$, there are at most $20$ more of the $60$ points on one side of $l$ than on the other side (where we don't include points on $l$ in either case). In this way, if we "radar-label" the $60$ points in clockwise order by $P_1, P_2, \cdots, P_{60}$ around $P$ (if two points are on the same ray from $P$, then just label them in whatever order we want), then the triangles $P_iP_{i+20}P_{i+40}$, for $i = 1, 2, \cdots, 20,$ all contain $P.$ Therefore, it suffices to show that such a point $P$ exists. To do this, we will use Helly's theorem. For any unit vector $v,$ we will define the set $S_v$ as follows. Let's consider the direction of $v$ as "up," and consider $S_v$ to be the set of all points in the plane which are strictly higher than the $41$st highest point among the $60$ points (so that $S_v$ doesn't contain the horizontal line through this $41$st highest point). It suffices since these sets are all convex to show that any three $S_v$'s have a common point, for all three unit vectors $v.$ This follows by straightforward casework (hard without diagram, oops). $\square$
28.03.2020 20:55
Why do such lines exist?
07.07.2024 15:50
One of the nice problems by Yijun Yao, it has some relationship with Tverberg's theorem or Radon's theorem in 2D. The key is Helly Theorem. Let $n=20.$ We consider the all $\binom{3n}{2n+1}$ polygons with $2n+1$ vertex. It is obvious that each three of them have a common point. So by Helly Thm there exists a point $P$ inside every polygon. Now note that for every straight line passing $P,$ at most $2n$ points are in the same half plane. Otherwise there are $2n+1$ points that doesn't include $P,$ contradiction! Now label the points clockwise $A_1,\ldots ,A_{3n},$ and take triangle $A_iA_{n+i}A_{2n+i},$ its convex hull includes $P,$ so we are done.$\Box$