Here is a problem closely related to this, namely Problem 4 of the German pre-TST 2004, written in December 2003: In the plane, consider $n$ circular disks $K_1$, $K_2$, ..., $K_n$ with equal radius $r$. Assume that each point of the plane is contained in not more than $2003$ of these circular disks. Show that each circular disk $K_i$ intersects not more than $14020$ other circular disks.

Does my memory cheat me or did Orl delete a discussion about this problem ?! dg

There was definitely a thread on this problem, Darij, I've no idea where it's gone either... By the way, what's with the trend of posting up the IMO 2003 logo in all the threads?

Valiowk wrote: There was definitely a thread on this problem, Darij, I've no idea where it's gone either... Orl says that there was only spam... I remember that there was a discussion about generalizations of the problem... Valiowk wrote: By the way, what's with the trend of posting up the IMO 2003 logo in all the threads? That's definitely Orl. He uses the logo to characterize ISL problems. Darij

darij grinberg wrote: Valiowk wrote: There was definitely a thread on this problem, Darij, I've no idea where it's gone either... Orl says that there was only spam... I remember that there was a discussion about generalizations of the problem... Valiowk wrote: By the way, what's with the trend of posting up the IMO 2003 logo in all the threads? That's definitely Orl. He uses the logo to characterize ISL problems. Darij Actually I do not delete mathematical content of any kind. And I cannot remember any mathematical content in this thread. Just "kueh" posted kind of 1 line hint like "the problem is easy..." The problem with lots of spam messages is that users usually don't tend to publish a solution anymore. But I think right now we have just spam in this thread again and no solution will be posted. Old state re-established... And I want to say that I just like the IMO logo.

Well, here is a solution of the problem: First, as an auxiliary result, we will solve the following problem, which is the Problem 4 of the German pre-TST 2004, written in December 2003 (the official solution is online at http://www.bundeswettbewerb-mathematik.de/imo/aufgaben/aufgaben.htm ): Auxiliary problem. In the plane, consider n circular disks $ K_1 $, $ K_2 $, ..., $ K_n $ with equal radius r. Assume that each point of the plane is contained in not more than 2003 of these circular disks. Show that each circular disk $ K_i $ intersects not more than 14020 other circular disks. Here's my original solution of this problem, i. e. the solution I gave during the TST (well... not exactly the solution I gave; I have corrected a little bagatelle mistake which even the proof-reader didn't notice ). In the following, disk will always mean closed circular disk ("closed" means that the points on the periphery of the circle belong the disk, too). If XY is a segment, then the disk with diameter XY will mean the disk corresponding to the circle with diameter XY. To cover a figure will mean covering it without gaps (but maybe with overlaps). First we prove: Lemma 1. For every positive number r, a disk of radius 2r can be covered by 7 disks of radius r. Proof. (See Fig. 1 below.) Let O be the center of a disk K with radius 2r, and let ABCDEF be a regular hexagon whose vertices lie on the periphery k of the disk K. Then, AB = BC = CD = DE = EF = FA = 2r (since it is well-known that the sidelength of a regular hexagon equals its circumradius). The disk with center O and radius r and the disks with diameters AB, BC, CD, DE, EF and FA will be called the little disks. The radii of these little disks are all r (in fact, this is clear for the disk with center O and radius r, and concerning the disks with diameters AB, BC, CD, DE, EF and FA, it follows from $ \frac{AB}{2}=\frac{BC}{2}=\frac{CD}{2}=\frac{DE}{2}=\frac{EF}{2}=\frac{FA}{2}=\frac{2r}{2}=r $). We will now show that these 7 little disks cover the disk K. This will clearly prove Lemma 1. Let P be a point inside the disk K; then we must show that this point P lies in one of our 7 little disks. Because of the rotational symmetry of the regular hexagon ABCDEF and because of the symmetrical construction of our disks, we can WLOG assume that the point P lies inside the circular sector AOB (including the arc AB of the circle k and the segments AO and BO). The triangle AOB is equilateral with sidelength AB = AO = BO = 2r; if A' and B' are the midpoints of the segments AO and BO, then $ OA^{\prime }=OB^{\prime }=\frac{2r}{2}=r $, so that these points A' and B' lie on the circle with center O and radius r. If the point P lies inside (or on the boundary) of triangle A'OB', then it follows that P lies inside the disk with center O and radius r, and the proof is done. Hence, it remains only to consider the case when the point P lies outside the triangle A'OB'. Since the triangle AOB is equilateral, symmetry yields $ BA^{\prime }\perp AO $, so that < AA'B = 90?. Similarly, < AB'B = 90?. Thus, the points A' and B' lie on the circle with diameter AB. Therefore, if the point P lies inside (or on the boundary) of the quadrilateral AA'B'B, then the point P lies inside the disk with diameter AB, and the proof is done again. So it remains to consider the case when the point P lies outside the triangle A'OB' and outside the quadrilateral AA'B'B. Then, the points P and O lie in different halfplanes with respect to the line AB. Then, since the point P lies inside the disk K, the angle < APB is greater or equal to the obtuse chordal angle of the chord AB in the circle k. But the obtuse chordal angle of the chord AB in the circle k equals 180? - the acute chordal angle of the chord AB; the acute chordal angle equals $ \frac12 $ times the central angle of the chord AB, and the central angle equals < AOB = 60? (since the triangle AOB is equilateral). Thus, the obtuse chordal angle of the chord AB is $ 180^{\circ }-\frac{1}{2}\cdot 60^{\circ }=180^{\circ }-30^{\circ }=150^{\circ } $. And thus, $ \measuredangle APB\geq 150^{\circ } $. Hence, also $ \measuredangle APB\geq 90^{\circ } $, and thus the point P lies inside the disk with diameter AB. So we are done again. Thus, every point P inside the disk K lies inside one of the 7 little disks. In other words, the 7 little disks cover the disk K. This proves Lemma 1. Now to the problem. The disk $ K_i $ intersects a disk $ K_j $ if and only if $ O_iO_j \leq r+r=2r $, where for every k, the point $ O_k $ is the center of the disk $ K_k $. Hence, the disk $ K_i $ intersects the disk $ K_j $ if and only if the point $ O_j $ lies inside the disk with center $ O_i $ and radius 2r. In this case, after Lemma 1, the point $ O_j $ must lie inside one of 7 certain disks with radius r which cover the disk with center $ O_i $ and radius 2r. But each of these 7 disks can contain at most 2003 different points $ O_k $, since else the center of this disk would have a distance $ \leq r $ to more than 2003 points $ O_k $ and thus, itself, would lie inside more than 2003 disks $ K_k $, what contradicts the problem hypothesis. Hence, the disk with center $ O_i $ and radius 2r contains at most $ 7 \cdot 2003 $ points $ O_k $, i. e. the disk $ K_i $ intersects at most $ 7 \cdot 2003 $ disks $ K_k $. Since one of these disks $ K_k $ is $ K_i $ itself (every disk intersects itself), it follows that the disk $ K_i $ intersects at most $ 7 \cdot 2003 - 1 = 14021 - 1 = 14020 $ other disks $ K_k $. And this for every i. This completes the solution of the auxiliary problem. Now, let's solve the actual problem: ISL 2003 problem C2. Let $ D_1 $, $ D_2 $, ..., $ D_n $ be closed discs in the plane. (A closed disc is the region limited by a circle, taken jointly with this circle.) Suppose that every point in the plane is contained in at most 2003 discs $ D_i $. Prove that there exists a disc $ D_k $ which intersects at most $ 7\cdot 2003 - 1 = 14020 $ other discs $ D_i $. Solution. This ISL problem can be reduced to the auxiliary problem as follows: Let $ O_1 $, $ O_2 $, ..., $ O_n $ be the centers and $ r_1 $, $ r_2 $, ..., $ r_n $ the radii of the discs $ D_1 $, $ D_2 $, ..., $ D_n $. Let $ r_u $ be the smallest radius among the radii $ r_1 $, $ r_2 $, ..., $ r_n $. Now, for every i, define a new disc $ K_i $ as follows: - Let $ K_u=D_u $. - If $ i\neq u $, then the disc $ K_i $ is defined as follows: Let the segment $ O_uO_i $ meet the periphery of the disc $ D_i $ at a point $ S_i $. Since the radius $ r_u $ is minimal, we have $ S_iO_i = r_i \geq r_u $, and hence we can find a point $ P_i $ on the segment $ S_iO_i $ such that $ S_iP_i=r_u $. Then, call $ K_i $ the disc with center $ P_i $ and radius $ r_u $. For every i, we have: (1) The disc $ K_i $ will completely lie inside the disc $ D_i $. (2) If the disc $ D_i $ intersects the disc $ D_u $, then the disc $ K_i $ intersects the disk $ D_u $, too. Proof of (1): This is trivial for i = u, and for $ i\neq u $, this is clear since the disk $ K_i $ touches the disc $ D_i $ at $ S_i $. Proof of (2): This is clear for i = u, and for $ i\neq u $, this follows from the simple observation that if the disc $ D_i $ intersects the disc $ D_u $, the point $ S_i $ lies inside the disc $ D_u $, and hence this point $ S_i $ is common to the discs $ D_u $ and $ K_i $. All discs $ K_1 $, $ K_2 $, ..., $ K_n $ have the same radius $ r_u $. Also, from the problem hypothesis we know that every point in the plaine is contained in at most 2003 discs $ D_i $; hence, after (1), we can conclude that every point in the plane is contained in at most 2003 discs $ K_i $. Thus, we can apply the problem I posted before, and see that every of the discs $ K_i $ intersects at most 14020 other discs $ K_j $. In particular, this is true for the disc $ K_u=D_u $. Thus, the disc $ D_u $ intersects at most 14020 other discs $ K_j $. Now, using (2), this implies that the disc $ D_u $ intersects at most 14020 other discs $ D_j $. And the ISL 2003 problem is solved. Darij

A simpler solution exists to this problem (Darij's solution is incredibly hard to come up with in my opinion). WLOG suppose $D_1$ is a disk with minimal radius, and WLOG suppose it has radius $1$. Let $O_i$ be the center of disk $i$. I claim that $k=1$ satisfies the desired conditions. Suppose this is not true, so $D_1$ meets at least $7\cdot 2003$ disks $D_i$. First, suppose that $\ge 2003$ disks $D_j$ have their centers $O_j$ inside $D_1$ for $j>1$. Then since the radius of each disk is $\ge 1$, each disk $D_j$ contains $O_1$, a contradiction. Therefore $<2003$ disks $D_j$ have centers inside $D_1$. Now ignore all such disks and consider only the disks with centers outside of $D_1$ which meet $D_1$ at some point, so there are at least $6\cdot 2003+1$ of these disks $D_i$. Draw six rays emanating from $O_1$, each ray $60^{\circ}$ apart from the previous ray, which meet $D_1$ at six points $A,B,C,D,E,F$, such that none of the $O_i$ lie on any of the six rays drawn. These rays divide the plane into six regions, and each $O_i$ for $i>1$ lies in one of the six regions, so some region, say the region contained in $\angle AO_1B$, has at least $2004$ centers $O_i$ within it. WLOG suppose these centers are $O_2,O_3,... O_{2005}$. Lemma: $D_2,D_3, .. D_{2005}$ each contain point $X$, where $XAOB$ is a parallelogram. Proof: We have two cases for each $2\le i\le 2005$. Case 1:$1\le O_1O_i< 2$. Then it's not hard to see $O_iX \le 1$, so it's clear that $X$ lies inside $D_i$. Case 2:$O_1O_i\ge 2$. Let $O_1O_i=r+1$, so that the radius of $D_i$ is at least $r$. Clearly $\angle O_iO_1X$ is at most thirty degrees, so by Law of Cosines, $O_iX^2 \le (r+1)^2 + 3 - 3(r+1) = r^2-r+1 \le r^2$, hence $X$ lies inside disk $D_i$. In either case, $D_i$ contains point $X$, so $2004$ disks contain point $X$, a contradiction, so we are done.

Really complex!

I have another solution to this problem If you want it email me I'll send it for you I can't write it in here ida_4444@yahoo.com

Difficult problem. Solved with Ankan Bhattacharya and Luke Robitaille. Let $m=2003$. Without loss of generality, let the minimal disk radius be $1$, and pick a disk with this radius. Suppose it has center $O$. We show that at most $7m-1$ disks intersect $(O)$. Clearly, at most $m-1$ additional disks contain the point $O$, so it suffices to show that at most $6m$ disks intersect $(O)$ but don't contain $O$. Let $\omega$ be a circle (not disk) centered at $O$ with radius $\sqrt{3}$. Lemma: Any disk $D$ intersecting the disk $(O)$ but not containing the point $O$ intersects $\omega$ in an arc with angle at least $\pi/3$. Proof: By minimality, the radius of $D$ is at least $1$. By taking a subdisk of $D$ with radius $1$, we may WLOG assume that $D$ has radius exactly $1$. Note that the center $A$ of $D$ is at least $1$ away from $O$, and at most $2$ away from $O$. Work in Cartesian coordinates with $O=(0,0)$, $A=(a,0)$, and let one of the two intersection of $\omega$ with $D$ be $X=(x,y)$. Then, $x^2+y^2=3$ and $(x-a)^2+y^2=1$. This implies \[x=\frac{a^2+2}{2a},\]and since $1\le a\le 2$, we have that $x\le 3/2$, which easily implies the result. $\blacksquare$ We now finish by noting that if $k$ disks intersect $(O)$ but don't contain $O$, then the total arc angle covered on $\omega$ is at least $k\pi/3$, so the average amount of disks a random point on $\omega$ is in is at least $k/6$, and this has to be at most $m$, so we're done. Remark: There are several ideas to solve this problem. Noting that the minimal disk probably satisfies the problem condition. This comes from examples where one can force every disk to intersect $7m$ others, except for the smallest one. Furthermore, the number $6$ probably represents the number of unit disks we can surround around another unit disk without interior overlap, and minimal disk works nicely with this. At this point, we want a global area or arc-length argument, and most natural area arguments give too weak of a bound. Furthermore, blocking these approaches are disks that are very close to the minimal disk. We get rid of these by doing the optimization of focusing only on disks that don't contain $O$, and we've turned $7$ into $6$ now! The "equality case" of six disks surrounding $D$ motivates looking at arc length (since none of the area estimates will be tight here), and magically radius $\sqrt{3}$ works (for a while I was doing horrible miscomputations and thought radius $2$ was the right way to go).

A good problem to showcase the powerful-ness of specific selection.

$\color{green} \rule{9.3cm}{2pt}$ $\color{green} \clubsuit$ $\boxed{\textbf{Classifying and Bounding Intersecting Circles.}}$ $\color{green} \clubsuit$ $\color{green} \rule{9.3cm}{2pt}$ Consider a disc $D$ with radius $r$ and center $O$. Pick a direction $d$, and plot six points $P_1,P_2,\ldots,P_6$ so that \[ |OP_i| = \sqrt{3}r \]and $\overrightarrow{OP_i}$'s direction towards $O$ is $d + 60^{\circ} \cdot (i-1)$. Then, we Claim that each disc of radius $r$ which intersects $D$ must contain one of the seven points \[ O, P_1, P_2,\ldots,P_6 \]$\color{green} \rule{25cm}{0.2pt}$ $\color{green} \spadesuit$ $\boxed{\textbf{Proof.}}$ $\color{green} \spadesuit$ Consider the center $O'$ of the disc which intersects $D$ (name it $D'$). Since the whole plane is divided into six regions, we can assume Without Loss of Generality that it lies inside the sector $OP_1P_2$. Furthermore, since that disc intersects $D$, we know that \[ |OO'| = c \leq r + r = 2r \]First, if $c \leq r$, we know that $O'$ lies inside $D$; and that implies $O$ also lies inside $D'$. Otherwise, let $r < c \leq 2r$. As we know that \[ \angle O'OP_1 + \angle O'OP_2 = 60^{\circ} \]we can again WLOG that $\theta = \angle O'OP_1 \leq 30^{\circ}$. This will imply \[ \cos{(\theta)} \geq \cos{30} = \dfrac{\sqrt{3}}{2} \]Now, we would like to prove that $|P_1O'| \leq r$, as that would imply $P_1$ to lie inside $D'$. By the cosine law on $\triangle O'OP_1$, we get \begin{align*} |O'P_1| &= \sqrt{c^2+3r^2-2 \cos{\theta} \cdot \sqrt{3}r \cdot c} \\ &\leq \sqrt{c^2+3r^2-3rc} \\ &= \sqrt{ \left( c - \dfrac{3}{2}r \right)^2 + \dfrac{3}{4}r^2} \\ &\leq \sqrt{\dfrac{1}{4}r^2 + \dfrac{3}{4}r^2} \\ &= r \end{align*}We are done for the first part. $\blacksquare$ $\color{blue} \rule{6.5cm}{2pt}$ $\color{blue} \clubsuit$ $\color{blue} \boxed{\textbf{The Ultra-Convenient Shrink.}}$ $\color{blue} \clubsuit$ $\color{blue} \rule{6.5cm}{2pt}$ Pick the disc with the smallest radius, and let it be $D$. $\blacksquare$ $\blacksquare$ Perform the procedure above to yield the seven points. We Claim that $\textbf{any}$ disc in the plane which intersects $D$ must intersect one of the seven points (not only the ones with radius equal to $D$, as depicted above.) $\color{blue} \rule{6.5cm}{0.2pt}$ If this is proven, since $O$ lies inside at most $2003-1$ other discs (aside from $D$) and $P_i$ lies inside at most $2003$ discs, the number of discs which intersect $D$ must not be more than $(2003-1)+6 \cdot 2003$. This is because any intersecting disc must be one of the discs specified in the previous sentence. So, $D$ satisfies the problem statement. $\color{blue} \rule{25cm}{0.2pt}$ $\color{blue} \spadesuit$ $\color{blue} \boxed{\textbf{Proof of the Claim.}}$ $\color{blue} \spadesuit$ Let the intersecting disc be $I_D$. (I'm just slamming random variable names in there) Since $I_D$ intersects $D$, there must exist a point $T$ (it stands for $\textit{tangent}$) belonging to $I_D$ which is inside $D$ (i.e. just pick the intersection point, or the point $OO_D \cap I_D$ where $O_D$ is the center of $I_D$.) Next, construct another disc $T_D$ with radius equal to $D$ which is internally tangent to $I_D$ at the point $T$. It is apparent that $T_D$ lies inside $I_D$, since the radius of $D$ is smaller than $I_D$'s. Finally, note that by $\color{green} \clubsuit$ $\boxed{\textbf{Classifying and Bounding Intersecting Circles}}$ $\color{green} \clubsuit$, we know that $T_D$ contains one of the seven points. This implies that $I_D$ contains that point too, by the previous paragraph. We are done. $\blacksquare$ $\blacksquare$ $\blacksquare$

ISL Marabot solve Let's define $O_i =$ center of $D_i$ and $R_i= $ radius of $D_i$ for all $1\leq i \leq n$. WLOG, let, $R_1 \leq R_2 \leq \dots \leq R_n$ and $R_1=1$ FTSOC, let's assume that $D_1$ intersects with at least $7\cdot 2003$ other disks. First, there can be at most $2002$ disks other than $D_1$ which contains $O_1$. So, there are at least $6\cdot 2003 +1$ disks that intersects with $D_1$ but doesn’t contain $O_1$. Now, we consider $\omega$ the circle with radius $\sqrt 3$ and center $O_1$. And, consider the set $S$ of six evenly separated point on the circumference of $\omega$. $\textbf{Claim:}$ If $D_i$ intersects with $D_1$ but doesn’t contain $O_1$ then, $D_i$ contains at least one point from $S$. $\textbf{Proof:}$ Here we consider a disk $E_i$ that is on the same direction and have same distance from $O_1$ as $D_i$ but have a radius of $1$. Let's call its center $M_i$. Clearly, $E_i$ also intersects $D_1$, doesn't contain $O_1$ and $E_i \subseteq D_i$ [As, $1\leq R_i$] Let, $P_i$ be the intersection of ray $\overrightarrow{O_1M_i}$ and boundary of $D_1$ and $Q_i$ is the reflection of $O_1$ over $P_i$. So, $M_i$ must lie on segment $P_iQ_i$. [As radius of $E_i = 1$] Let, $X_i,Y_i$ be the intersections of circles with center $P_i, Q_i$ and radius $1$. It's easy to show that $O_1X_i=O_1Y_i=\sqrt 3$ so, $X_i,Y_i\in \omega$. And, $\angle X_iO_1Y_i = 60^\circ$ so the minor arc $X_iY_i$ is $\frac16$ of the circumference of $\omega$. So minor arc $X_iY_i$ must contains at least one point from $S$. But, $X_iP_iQ_i$ is equilateral triangle. So, $M_iX_i \leq 1\implies X_i\in E_i$ as the same $Y_i\in E_i$. So, $E_i$ contains minor arc $X_iY_i$ of $\omega$. Hence, $E_i$ contains at least one point from $S$. So $D_i$ contains at least one point from $S$. [As, $E_i\subseteq D_i$] And our claim is proved. Now, by our claim and using PHP, at least one point of $S$ must be contained in $\left\lceil\frac{6\cdot 2003+1}{6}\right\rceil = 2004$ disks. And this gives the contradiction we wanted. $\blacksquare$

We claim that the smallest disk satisfies the conditions described in the problem. Let the smallest disk be $ D$ and the center of $ D$ be $ O$. Let its radius be $1$. Now, let $A_1$, $A_2$, $\dots$, and $A_6$ be six distinct points a distance of $\sqrt3$ from $ O$, and $\angle A_iOA_{i+1}=60^\circ$. Clearly, there can only be $2003-1$ other disks containing $O$. Consider any other disk, $D_1$ with center $O_i$. If $O$ is not contained in $D_1$, then note that $1\le O_1O\le 2$. WLOG, assume that $\angle A_1OO_1\le 30^\circ$ then by cosine law, $O_1A_1\le 1$. Therefore any such disk contains one of $A_1$, $A_2$, $\dots$, $A_6$. Thus, there are at most $6\cdot 2003$ disks not containing $O$ intersecting $O$. We are done.

awesomeming327. wrote: Consider any other disk, $D_1$ with center $O_i$. If $O$ is not contained in $D_1$, then note that $1\le O_1O\le 2$. Could you please tell how? I mean the lower bound of 1 is fine but the upper bound 2 does not make sense to me.

we're back baby (what the cringe) The smallest disk $D$ works. Assume this disc intersects exactly $N=7\cdot 2003$ other discs $E_1,\dots,E_N$. We prove that some point $P$ is contained in at least $2004$ of these discs. Without loss of generality, it is valid to assume that $E_i$ has the same size as $D$; simply take the original disc $E_i$, find a subset $E'_i$ which has nonempty intersection with $D$, and write $E_i:=E'_i$. Assume, also, that the common size---the radius of $D$---is exactly $1$. Now, let $O_1,\dots,O_N$ be the centers of the discs $E_i$. These centers lie in circle $\mathcal{R}$ concentric with $D$ with radius $2$. The condition from section $(1)$ regarding $P$ is actually equivalent to the following: that there exists a circle $\mathcal{r}$ with radius $1$, centered at $P$, which passes through $2024$ of the $O_i$. It is easier to prove using contradiction: that with $7\cdot 2023$ centers in $\mathcal{R}$, and only $2023$ centers in any $\mathcal{r}$, that a contradiction arises. We prove this statement now, solving the problem. Select six arbitrary equally-spaced points on the boundary of $\mathcal{R}$, with each pair of adjacent points serving as a diameter of a circle $\mathcal{r}$, for six circles in total. Each pair of $\mathcal{r}_1$ and $\mathcal{r}_2$ intersects at a point $Q$, which is a distance of $1$ from the center of $\mathcal{R}$. In particular, this observation proves that a final circle $\omega$ with radius $1$ concentric with $\mathcal{R}$---when combined with the previous six circles---will completely cover $\mathcal{R}$. We are almost done. Let $A$ be the set of points in $\mathcal{R}$ covered by exactly one of the aforementioned circles. Let $B$ be the complement of $A$. Suppose that there are $c>0$ centers in $B$. If we add together the center-counts for each of the seven circles, we obtain $7\cdot 2023+c$, which is not possible---so $c=0$, and there are exactly $2023$ centers in each of the seven circles. In other words, $A$ is split into seven disjoint regions, corresponding to subsets of the seven circles---and each region contains exactly $2023$ points. The rest is easy. Choose a center $X$ in one of the outer six regions. Rotate the entire configuration---of seven circles, of regions $A$ and $B$, into new seven circles and regions $A'$ and $B'$, so that $X\in B'$. We repeat, essentially, the same process used in the previous steps---but this time, $X$ is not in $A$ for a fact, leading to a contradiction. $\blacksquare$