There are $100$ circles of radius one in the plane. A triangle formed by the centres of any three given circles has area at most $2017$. Prove that there is a line intersecting at least three of the circles.
Problem
Source: Canadian Mathematical Olympiad 2017
Tags: combinatorial geometry, discrete geometry
zephyrcrush78
01.04.2017 01:43
Take two centers $A$ and $B$ such that $AB = 2k$ is maximal. By maximality and the $2017$ condition, all points must lie in a rectangle with dimensions $2k$ and $2 \cdot 2017/k$, where $AB$ is a midline. One of these dimensions must be less than $90$. Split the side with this dimension into $45$ strips with width at most $2$. Then we have $98$ centers left, so by Pigeonhole at least one strip must contain at least $3$ centers. Then just take the line that goes in the middle of this strip; since the strip has width at most $2$, this intersects the circles with these $3$ centers as desired.
here is a pro drawing
va2010
01.04.2017 15:46
Darn, so apparently this isn't the same as 2002 IMO #6
CQYIMO42
08.06.2017 18:32
Oops I was being lazy, here is my solution:
Proof:
First take the smallest convex hull composed of all the $100$ centres of the circle.
We first prove a lemma.
Lemma:
There always exist a certain direction such that the projection of the convex hull in this direction $<98$.
Proof of the lemma:
For the sake of contradiction, assume that the projection of the convex hull in any direction is greater than $98$.
Suppose that the projections of the convex hull at a certain direction are $A_1,B_2$, where $A_1$ is the projection of the point $A$ and $B_1$, the projection of the point $B$.
Then $|AB|\ge|A_1B_1|\ge98$.
Now consider the projection in the direction perpendicular to $AB$ and we get $C_1D_1\ge98$.
Then the distance from either $C$ or $D$ is greater or equal to $49$. WLOG, suppose that it is $C$.
Therefore the area of the triangle $ABC>\frac{49\times98}{2}>2017$, which is a contradiction.
And that completes the proof of the lemma. //
By Lemma, we notice that there exist a certain direction in which the projection length of the convex hull is less than $98$, suppose that this direction is horizontal, and suppose that the projection length $l<98$.
For the sake of contradiction, suppose that any lines can intersect at most $2$ circles, then the number of centres of circles whose distance to a line $<\frac{l}{98}<1$ is at most $2$.
So we take $49$ lines that are parallel and with distance $\frac{2l}{98}$ between each other and whose "dominating" area covers exactly the projection length.
Then we can show that there are at most $98$ points, but there are $100$ points in the problem, which is a contradiction, and that completes the proof.
$Q.E.D.$
Plops
29.12.2019 22:57
Let the maximal distance between two circles-centers $A$ and $B$ be $AB=d$. Then, construct a line $l$ s.t. $l \perp AB, l \cap AB=P$. Then, project all the circle centers except $A$ and $B$ onto $l$, and let the far left and far right projections be labeled $C$ and $D$. By the area condition, $CP,DP \leq \frac{\sqrt{2017}}{d} \implies CP+DP \leq \frac{2\sqrt{2017}}{d}$, and the maximality condition implies $CP+DP \leq d$. Since $\min(\frac{2\sqrt{2017}}{d}, d) \leq 2\sqrt{2017}$, $CD \leq 2\sqrt{2017}$. Then, consider dropping perpendiculars from the points of tangency of all the circles with lines parallel to $AB$ and tangent to the circles at two points resectively, to $l$. Call the sub-segment of $l$ created by these projections $L$, and its length $L'$. The lengths of all the projections counted regardless of overlapping is then $200$, and $L'= \leq 2\sqrt{2017}+2$. Therefore, by the pigeonhole principle, there exists a point on $L$ (not necessarily a projection) covered by $\lceil \frac{2 \times 100}{2\sqrt{2017}+2} \rceil =3$ circles.
jj_ca888
05.07.2020 05:26
Nice problem! I wish I could see something similar on a non-Canadian contest. Claim: We can choose some line $\ell$ in the plane, such that when the centers of the $100$ circles are projected onto the line, the $100$ points lie in some interval with length at most $\sqrt{8068}$. Proof: Let $\mathcal{P}$ denote the set of $100$ circle centers. Choose two of them, $X$ and $Y$, that are the farthest apart. Let $\overline{XY} = d$. Now consider some other point $Z \in \mathcal{P}$. We must have $\delta(Z, XY) \leq \tfrac{4034}{d}$. If $d \leq \sqrt{8068}$, then we can simply choose line $XY$ to be $\ell$. Note that the projection of any point $Z \in \mathcal{P}$ must lie on line segment $XY$, since otherwise, the assumption that $XY = d$ is maximal is contradicted because we would have one of $ZX, ZY$ greater than $XY$. If $d > \sqrt{8068}$, then we can choose any line perpendicular to $XY$ to be $\ell$. This is because, for any point $Z \in \mathcal{P}$,\[\delta(Z, XY) \leq \frac{4034}{d} < \frac{\sqrt{8068}}{2}\]so when all points in $\mathcal{P}$ are projected onto such a line $\ell$, they cover an interval with length less than $\sqrt{8068}$. Our claim has been proven. $\square$ Now suppose we project all $100$ circles onto such a line described above. Each circle projects to an interval of length $2$, and all $100$ such intervals of length $2$ are contained in a large interval of length $\leq \sqrt{8068} + 2 < 92$. It suffices to show that there exists a point on contained in some three length $2$ intervals. We argue by expected value. For each point, the expected number of length $2$ intervals it belongs to is\[\mathbb{E} \geq \frac{2 \cdot 100}{\sqrt{8068} + 2} > 2.\]Hence, there must exist a point belonging to $3$ such intervals, and we are done. $\blacksquare$ Remark: Wow. Combinatorics and Geometry are my favorite two subjects
Aryan-23
27.09.2020 23:46
Awesome problem. We will solve a generalization of this : General Problem wrote: There are $n$ circles of radius one in the plane. A triangle formed by the centres of any three given circles has area at most $A$. Prove that there is a line intersecting at least $\tfrac {n}{\sqrt A+1}$ of the circles. We will denote by $S$ the set of centers of the circles. Claim : There exists a line $\ell$ such the projections of $S$ onto $\ell$ lie in a interval of length atmost $2\sqrt A$. Proof : Pick $A,B \in S$ such that $AB=d$ is maximal. Note that by the area condition we have that every point in $S$ is at a distance of atmost $\tfrac {2A}d$ from $S$. Pick a line $\ell$ perpendicular to $AB$ such that it intersects $AB$ at $X$. Then note that the projections of $S$ onto $\ell$ lies inside a interval of length $\tfrac {4A}d$ centered at $X$. Note that this interval must have length atmost $d$. Hence the interval must have length atmost $\operatorname {min} (d, \tfrac {4A}d ) \le 2\sqrt A$. Hence the claim is proven. $\square$. We now consider such a line $\ell$ and project all the circles onto $\ell$. Note that the projection of each circle is a interval of length $2$ (we will call these regions henceforth) , however the total interval length is atmost $2\sqrt A+2$. Hence each point in the interval is in a average of $\tfrac {2n}{2\sqrt A+2}$ regions. Hence one of the points must be in atleast $\tfrac {n}{\sqrt A+1}$ regions. Taking the perpendicular to $\ell$ from this point finishes. $\square$ Okay this is one of my favourite problems now
Mr.C
03.10.2020 04:07
well i almost hate every single problem like this , but this one was fun ... here is how i did it . . one of the main idea's used in problems like this ,is using projections and the greatest differece of 2 points . . we will show how this kills the problem . . first for any line $t$ denote $f(t)=r$ such that the projections of the centers of circles on $t$ has a lenght of $r$ . now let $k$ be the largest disstance of any two centers. name the centers $A,B$ take a line $u$ perpendicular to $AB$ . any point is at most $\frac{4034}{k}$ away from the line $AB$ so $f(u) \le min(k, \frac{8068}{k})$ . now we just leave it there to see what happens. . now if we project every thing to the line named $g$ with $f(g)=h$ we have that there is a line passing through at least $\frac{200}{h+2}$ so having $\frac{200}{h+2} >2$ is enough so we just need to have $98>h$ now we just have too prove $98 > min(k,\frac{8068}{k})$ clearly we should have $k>98$ which gives $\frac{8068}{98}<\frac{8068}{98}<83<98$ and done. . and by doing this one can also guess the generalization @above .
Eliot
04.10.2020 18:16
Aryan-23 wrote: Awesome problem. We will solve a generalization of this : General Problem wrote: There are $n$ circles of radius one in the plane. A triangle formed by the centres of any three given circles has area at most $A$. Prove that there is a line intersecting at least $\tfrac {n}{\sqrt A+1}$ of the circles. .... Okay this is one of my favourite problems now Nice solution but sadly it's exactly the same solution as the solution in Canda 2019 IMO training handout.
TheUltimate123
20.07.2021 07:54
Let \(AB\) be the segment of longest length \(D\). Claim: There is a line \(\ell\) such that the projections of the 100 centers onto \(\ell\) span a distance of at most \(\sqrt{8068}\). Proof. Let \(\overline{AB}\) be horizontal, so the horizontal span of the centers is \(D\). For any point \(C\in S\), we are given that the distance from \(C\) to \(\overline{AB}\) is at most \(\frac{4034}D\), thus the vertical span of the centers is at most \(\frac{8068}D\). But \(\min\{D,\frac{8068}D\}\le\sqrt{8068}\) as desired. \(\blacksquare\) [asy][asy] size(10cm); defaultpen(fontsize(10pt)); pair A,B,X,Y; real theta=75,t=.2; A=(0,0); B=(1,0); X=(t,sqrt(1-(1-t)^2)); Y=reflect(A,B)*X; void f(pair P) { dot(P,heavygreen); draw(P--foot(P,A,B),heavygreen); } f((.05,-.2)); f((.1,.3)); f((.15,.1)); f((.25,-.1)); f((.34,-.5)); f((.43,.4)); f((.57,-.3)); f((.66,.2)); f((.75,.4)); f((.85,-.2)); f((.95,.1)); draw(A--B,blue+linewidth(1)); draw(arc(A,1,-theta,theta),lightblue); draw(arc(B,1,180-theta,180+theta),lightblue); draw(brace(A,B)); draw(brace( (1.1,.4),(1.1,-.5))); label("\tiny\(D\)",(A+B)/2+(0,.17)); label("\tiny\(4034/D\)",(1.1,-.05)+(.225,0)); dot("\(A\)",A,W); dot("\(B\)",B,E); [/asy][/asy] Now let the projections of the centers onto \(\ell\) be \(X_1\), \(X_2\), \(\ldots\), \(X_{100}\) in order along \(\ell\). I contend we may take the perpendicular bisector of \(\overline{X_iX_{i+2}}\) for some \(i\). If this is not possible, then \(X_iX_{i+2}>2\) for all \(i\), implying \(X_1X_{100}>98\), contradicting \(X_1X_{100}<\sqrt{8068}\).