Determine whether there exist $100$ disks $D_2,D_3,\ldots ,D_{101}$ in the plane such that the following conditions hold for all pairs $(a,b)$ of indices satisfying $2\le a< b\le 101$: If $a|b$ then $D_a$ is contained in $D_b$. If $\gcd (a,b)=1$ then $D_a$ and $D_b$ are disjoint. (A disk $D(O,r)$ is a set of points in the plane whose distance to a given point $O$ is at most a given positive real number $r$.)
Problem
Source: Czech-Polish-Slovak Match 2019 P5
Tags: combinatorics
17.07.2019 15:10
Since the disks corresponding to the prime numbers needn't contain any other disks, we may as well make them points. Now consider the 5 point-disks \(D_2,D_3,D_5,D_7,D_{11}\). Note that for any two of these disks (say \(D_a\) and \(D_b\)), \(D_{ab}\) must contain \(D_a\) and \(D_b\), but not any of the other 3 point-disks. Therefore we have 5 points in the plane such that for any 2 of them, there exists a circle containing only those 2. We now prove this is impossible. Clearly if any three of the points are on a line, the condition isn't satisfied - if the points are \(A,B,C\) in that order, the circle containing \(A\) and \(C\) also contains \(B\). Therefore no three of the points are on a line. It's easy to check that for any 5 such points, there exists a convex quadrilateral with vertices among them - one way to do this is to consider the 18 regions in which a concave quadrilateral's extended edges partition the plane and find that whichever one of them holds the fifth point, a convex quadrilateral is formed. Finally, consider the point \(X\) in which the convex quadrilateral's diagonals intersect. If the vertices of the quadrilateral are \(M,N,P,Q\) in that order, \(X\) needs to lie within both \(D_{MP}\) and \(D_{NQ}\), yet those disks are disjoint, contradiction.