There are $2015$ distinct circles in a plane, with radius $1$. Prove that you can select $27$ circles, which form a set $C$, which satisfy the following. For two arbitrary circles in $C$, they intersect with each other or For two arbitrary circles in $C$, they don't intersect with each other.
Problem
Source: 2015 Final Korean Mathematical Olympiad Day 2 Problem 6
Tags: combinatorics, combinatorial geometry, extremal principle
22.03.2015 22:36
Here is an outline. Set an $xy$ coordinate plane.Consider the center with highest $x$ coordinate. Lemma: If it intersects $3*26+1$ circles we can pick a set of $27$ circles such that every two intersect each other. Proof:All the circles that it intersects have their centers in a circle which center lies in a circle which center is the highest one and radius $2$.Cause this center is the highest,all the points lie on a maximum half circle with center the highest circle(there are no points above it).Now,divide this arc in $3$ equal regions.Now,it is trivial that if two points are in the same region their distance is less than $2$,so we are done by an easy pigenhole. If not,then we "save" that circle and we look at the picture without that circle and circles that it intersects and repeat the process.Now,at each step we remove at most $79$ circles,so after $25$ such removings we are left with $40$ circles,so if we have two of them that don't intersect we add them and if not we have a set of $40$ circles such that every two intersect.
07.06.2015 15:43
24.04.2020 06:12
Thanks to tapir1729 for giving me a hint on this question (see remark). Let $V$ be the set of centers of the circles, and let $G$ be the graph with vertex set $V$, and $i\sim j$ if $d(i,j)\le 2$ (i.e. the circles with $i$ and $j$ as centers intersect). It suffices to show that if $G$ contains no $K_{27}$, then it contains an independent set of size at least $27$. We perform the following procedure with $V'$ originally equal to $V$ and $C$ originally equal to $\emptyset$. Select $x$ on the convex hull of $V'$ and add $x$ to $C$. Delete $x$ along with all other points in $V'$ a distance at most $2$ from $x$. Clearly the final set $C$ is an independent set, so all we need to show is that the algorithm runs at least $27$ times. Indeed, consider the disk $\delta$ with center $x$ and radius $2$. Since $x$ is on the convex hull, at most a semicircle of $\delta$ can contain any other points of $V'$. Note that each $60^\circ$ arc of that semicircle can contain at most $25$ points (otherwise we get a $K_{27}$), so by deleting $x$, we delete at most $1+25\cdot 3=76$ points. There are a total of $2015$ points, so the algorithm runs at least $\lceil 2015/76\rceil=27$ times, as desired. Remark: Without the convex hull optimization, we see that each step deletes at most $1+25\cdot 6=151$ points, so this solves the problem if $2015$ is replaced with about $4000$.
26.02.2021 11:15
Let $G$ be the graph representation of this problem, that is, let the set of vertices be the set of centers of the circles, and connect two vertices if and only if they intersect, in other words we connect $v_i$ and $v_j$ if $d(v_i, v_j) \le 2$. We'll now prove that if graph $G$ doesn't contain $K_{27}$, then it must contain an independent set $H$ of size $27$. [asy][asy]usepackage("tikz");label("\begin{tikzpicture}[scale=0.6] \draw[fill=blue] (1,0) circle (3 pt); \draw[fill=red] (2,1) circle (3 pt); \draw[fill=blue] (0.5,1.1) circle (3 pt); \draw[fill=red] (1.6,0.3) circle (3 pt); \draw[fill=blue] (1.3,0.8) circle (3 pt); \draw[fill=blue] (0,0.3) circle (3 pt); \draw[fill=blue] (-0.9,-0.3) circle (3 pt); \draw[fill=red] (0.3,-1.2) circle (3 pt); \draw[fill=blue] (-0.2,0.4) circle (3 pt); \draw[fill=blue] (0.8,0.9) circle (3 pt); \draw[fill=red] (-0.9, -1.2) circle (3 pt); \draw[fill=red] (-1.3,2.1) circle (3 pt); \draw[fill=blue] (-0.4,1.43) circle (3 pt); \draw[fill=blue] (0.5,-0.4) circle (3 pt); \draw[fill=blue] (0.4, 1.4) circle (3 pt); \draw[green, dashed, very thick] (-1.3,2.1) -- (-0.9,-1.2) -- (0.3,-1.2) -- (1.6,0.3) -- (2,1) -- cycle; \end{tikzpicture}");[/asy][/asy] Consider the convex hull $\mathcal{C}$ of the set of centers. Claim 01. There are at most $75$ vertices connected to a vertex $v_i \in \mathcal{C}$. Proof. Consider a vertex $v_i \in \mathcal{C}$. Let the neighbors of $v_i$ in $\mathcal{C}$ be $v_{i + 1}$ and $v_{i - 1}$. By the definition of convex hull, since $v_i \in \mathcal{C}$, we can choose a line $\ell$ passing through $v_i$ such that $v_{i - 1}$ and $v_{i + 1}$ lies on the same side of line $\ell$. We'll consider the following diagram. [asy][asy]usepackage("tikz");label("\begin{tikzpicture}[scale=0.6] \draw[fill=black] (0,0) circle (4 pt); \draw[fill=yellow] (4,0) circle (3 pt); \draw[fill=yellow] (-4,0) circle (3 pt); \draw[line width=1pt,color=green] (0,0) circle (4 cm); \node[black, font= \small] at (0,0.7) {$v_i \in \mathcal{C}$}; \draw[line width = 1 pt, color= red, dashed] (0,0) circle (0.4 cm); \draw[line width = 1 pt, color= violet, dashed] (-4.2,0) -- (4.2,0); \node[red, font = \large] at (4.3,0) {$\ell$}; \draw[fill=yellow] (-2,-3.46) circle (3 pt); \draw[fill=yellow] (2,-3.46) circle (3 pt); \draw[line width = 1 pt, color=blue, dashed] (-2,-3.46) -- (0,0) -- (2,-3.46) ; \node[brown, font= \large] at (-2,-1.4) {$\mathcal{R}_1$}; \node[brown, font = \large] at (0,-2) {$\mathcal{R}_2$}; \node[brown, font= \large] at (2,-1.4) {$\mathcal{R}_3$}; \end{tikzpicture}");[/asy][/asy] Suppose there are at least $76$ vertices that are connected to $v_i$. Let the set of these $76$ vertices be $\mathcal{V}_i$. Now, notice that all of the vertices $v \in \mathcal{V}_i$ lie in/on circle $\Gamma$, which has center $v_i$ and radius $2$. Furthermore, it must lie in at least one of the three regions $\mathcal{R}_1, \mathcal{R}_2$ or $\mathcal{R}_3$. By the Pigeonhole Principle, there exists an index $i \in \{ 1, 2, 3 \}$ such that $|\mathcal{R}_i| \ge 26$. Take that particular region. Since any two vertices $v_j, v_k \in \mathcal{R}_i$ must satisfy $d(v_j, v_k) \le 2$, these $26$ vertices, and $v_i$ itself forms $27$ vertices that are connected to each other, forming a $K_{27}$, which is a contradiction. Now, we follow the following procedure: From the current set of points, take a vertex $v_1 \in \mathcal{C}$, where $\mathcal{C}$ is its convex hull and let $v_1 \in H$. Now, delete that vertices and all of the other vertices that are connected to $v_1$. By our previous lemma, there are at most $75$ vertices that are connected to $v_1$. Repeat the process. Notice that this process deletes at most $76$ vertices each turn, and therefore, we have \[ |H| \ge \left \lceil \frac{2015}{76} \right \rceil = 27 \]and hence, we are done. Remark. It is quite natural to interpret and work with graph instead. Our main aim is to show that there exists an independent set of size $27$, which by definition, $27$ centers of circles such that any two have distance more than $2$. In some sense, we want our $27$ centers to be "faraway from each other". One of the most straightforward thing to consider is noticing that if $v \in H$, then any vertices $w$ such that $d(v,w) \le 2$ won't be in $H$, by simple definition. This algorithm indeed works, but we need to save points, and delete as few points as possible in every move. Thus, convex hull gives us the right choice, and it's not hard from here.
20.09.2021 03:01
Take a circle $A_1$ on the convex hull. If it intersects more than $3 \cdot 25$ disks, it's not hard to see via a pigeonhole argument that we'll be able to find a set of $27$ disks including it that is of the first kind. Otherwise, we remove $A_1$ and all the disks it intersects. Then, we repeat this again with another circle $A_2$ on the convex hull of the set of disks that are left. We continue in this way, where on the $k$th step, we remove a circle $A_k$ on the convex hull of the circles that have not yet been removed, as well as all the circles it touches. We generate a sequence of disks $A_1, A_2, \dots $ where no two disks in the sequence intersect. We continue in this way until we find a set of the first type, or we have no more circles left. In the latter, we have done at least $\left \lceil \frac{2015}{76} \right \rceil = 27$ steps (we remove up to $76$ disks at a time). We take disks $A_1, A_2, \dots A_{27}$ and this is a set of the second type.
20.03.2023 02:52
Solved with a sizeable number of hints in 15 minutes because I have a history essay due tomorrow that needs to be written so I can't spend that much time on math Work with both the circles themselves and the obvious graph-theoretic interpretation. I will prove that if no $K_{27}$ exists, then we can find an independent set of size $27$. Consider the convex hull of all the circle centers, and pick one of its vertices $O$ which is the center of some circle $\omega$. Draw the two rays trisecting the angle at that vertex (so each of the three angles formed has measure less than $60^\circ$) and pick one of the three regions formed. Consider the $k$ circles intersecting $\omega$ whose centers lie in that region. The distance between $O$ and the center of any of these circles must be less than $2$. As such, it is easy to see that the distance between any two of these $k$ centers is less than $2$ as well, so $k \leq 25$, else the $k$ circles and $\omega$ form a $K_{27}$. Thus at most $76$ circles intersect $\omega$. Add $\omega$ to $C$ and delete the $\leq 75$ circles that intersect $\omega$, as well as $\omega$ itself. Then repeat this process with the remaining circles. We can do this at least $\lceil 2015/76 \rceil=27$ times, which gives us our independent set as desired. $\blacksquare$
23.09.2023 02:40
Consider the set of all centers of the circles, and connect two centers with an edge if the distance between them is at most $2$. Suppose that there exists no $27$-clique; we will build an independent set of size at least $27$ inductively. Let $S$ be the set of centers that can still be picked. Take $O$ to be a center on the convex hull, and consider adding $O$ to the set. Notice that all other points in $S$ adjacent to $O$ lie within a semicircle of radius $2$ centered at $O$. For no $26$ of these points to all be mutually connected, there must be at most $75$ of them within the semicircle. As a result, adding $O$ to the independent set decreases $|S|$ by at most $75$. However, $75 \cdot 26 < 2015$, thus we can select $27$ elements in the independent set, as needed.
01.08.2024 03:28
Replace radius $1$ with radius $1/2$. Make a graph with the centers of circles as the vertices, and an edge if and only if the distance is at most $1$. The idea is we try to construct an independent set. Select a point on the convex hull of all points, and destroy it along with all points within a distance of $1$ from it. Claim: If this operation destroys $79$ or more points, then a $K_{27}$ exists. Consider the selected point $P$, and let $\omega$ be the circle of radius $1$ around $P$. Since the point is on the convex hull, all other points in the circle are in the same $180$ degree arc of $\omega$. Split this arc into three $60$ degree arcs. By Pidgeonhole, since this circle has at least $79$ points in it, some region has $27$ points, creating a $K_{27}$. Thus, assume that this operation destroys at most $78$ points. After applying this operation $25$ times, we still have at least $2015-25\cdot 78=65$ vertices. At least two vertices out of these are not adjacent, since we are assuming no $K_{27}$, so these two vertices along with the previously deleted $25$ form an independent set of $27$ vertices, done.