A square grid on the Euclidean plane consists of all points $(m,n)$, where $m$ and $n$ are integers. Is it possible to cover all grid points by an infinite family of discs with non-overlapping interiors if each disc in the family has radius at least $5$?
Problem
Source: USAMO 2007
Tags: geometry, combinatorics, USAMO, combinatorial geometry, Soddy
26.04.2007 09:03
No. Between any three non-overlapping circles of radius greater than $\frac{ 2 \sqrt{6}+3 \sqrt{2}}{2}= 4.57...$ we can insert a circle of radius greater than $\frac{1}{ \sqrt{2}}$ in which there must be a lattice point.
04.12.2007 03:07
Here's a proof of why you can always fit a circle of radius $ \frac{\sqrt 2}{2}$, inside the region formed by $ 3$ circles, each of which has radius at least $ 5$. 1: First we note it's sufficient to prove it in the case where all the circles are tangent. Consider three circles $ C_{1}, C_{2}, C_{3}$, with centres $ O_{1}, O_{2}, O_{3}$. Let $ D$ be the inner Soddy circle of $ O_{1} O_{2} O_{3}$. Clearly $ D$ lies strictly inside the triangle $ O_{1} O_{2} O_{3}$, and $ D$ is the circle externally tangent to three other circles, each of which has radius at least $ 5$. Thus if we can prove the result for these $ 3$ externally tangent circles, that it's sufficient. 2: My proof for $ 3$ externally tangent circles is just brute force. If the radii of the $ 3$ circles are $ a, b, c$, then by Soddy circle results, the radius of the Inner Soddy circle, which lies inside the region formed by these $ 3$ circles, is $ f(a,b,c) = \frac {abc} {ab+bc+ac + 2 \sqrt{abc(a+b+c)}}$. By differentiation, it's clear that $ f(a,b,c)$ is increasing in each of it's variables, so $ f(a,b,c) \geq f(5,5,5) > \frac {1}{\sqrt{2}}$, so we can find a circle inside that has radius at least $ \frac {1}{\sqrt{2}}$, and contains a grid point, as required. 3: It's intuitely obvious that this solves the problem, but here's a formal argument: Label the circles in our infinite family $ C_{i}$. Consider any circle in this square grid, $ C_{1}$. Draw a circle tangent to $ C_{1}$, centre $ O_{1}$, with radius $ \frac {1}{\sqrt{2}}$. This circle contains a grid point, so another circle $ C_{2}$, centre $ O_{2}$ intersects this circle. Now consider any circle $ C_{n}$. As described in Step 1, we can find a circle of radius at least $ \frac {1}{\sqrt {2}}$ 'inside' these three circles. So another circle $ C_{m}$ must intersect this circle. Now repeat the argument for $ C_{1}, C_{2}$ and $ C_{m}$. Continue in this fashion, and after finitely many steps we will reach a disc of radius at least $ \frac {1}{\sqrt {2}}$, that lies outside our infinite family, which is a contradiction.
14.04.2009 06:00
Alternately, the smallest possible area of the gap between three circles is \[ 25\left(\sqrt{3}-\frac{\pi}{2}\right)=4.031...>4\] hence by Minkowski's theorem it contains a lattice point.
28.04.2011 18:42
me@home wrote: Alternately, the smallest possible area of the gap between three circles is \[ 25\left(\sqrt{3}-\frac{\pi}{2}\right)=4.031...>4\] hence by Minkowski's theorem it contains a lattice point. I hate to bump an old topic, but Minkowski's theorem only applies to convex sets symmetric to the origin, so I don't know if this argument is valid.
22.06.2014 21:03
Incorrect solution, please ignore
01.04.2016 22:25
t0rajir0u wrote: No. Between any three non-overlapping circles of radius greater than $\frac{ 2 \sqrt{6}+3 \sqrt{2}}{2}= 4.57...$ we can insert a circle of radius greater than $\frac{1}{ \sqrt{2}}$ in which there must be a lattice point. Sorry, but how do you know that the circle of radius greater than $\frac{1}{ \sqrt{2}}$ which touches three circles doesn't intersect/touch a fourth circle? Thanks!
04.04.2016 22:59
Does anyone know why this can't happen? Thank you very much!
07.04.2016 05:17
10.04.2016 10:15
EDIT: I think this solution was not rigorous enough
17.04.2017 01:59
me@home wrote: Alternately, the smallest possible area of the gap between three circles is \[ 25\left(\sqrt{3}-\frac{\pi}{2}\right)=4.031...>4\]hence by Minkowski's theorem it contains a lattice point. Wikipedia wrote: In mathematics, Minkowski's theorem is the statement that any convex set in $\mathbb{R}^n$ which is symmetric with respect to the origin and with volume greater than $2^n d(L)$ contains a non-zero lattice point. The theorem was proved by Hermann Minkowski in 1889 and became the foundation of the branch of number theory called the geometry of numbers. Is the region convex and symmetric? (If so, then everything I learned in Mathcounts about arcs and "weird areas" is false ) Anyway,
02.10.2018 08:46
Draw a small circle whose interior is disjoint from all the disks. Now, continuously expand and translate this circle until its interior has to intersect some disk. This circle is tangent now two three disks. Suppose the centers of these disks are at $A,B,C$, and that they have radii $a,b,c$. Also suppose that the circle is centered at $O$ and it has radius $r$. WLOG, suppose $\angle AOB\le 120^\circ$ (if not, permute the labels of the disks until its true). We then see that $AB^2=OA^2+OB^2-2\cdot OA\cdot OB\cos\angle AOB$. Note that $\cos\angle AOB\ge -1/2$, and $AB\ge a+b$, so \[(r+a)^2+(r+b)^2-2(r+a)(r+b)(-1/2)\ge (a+b)^2,\]or \[3r^2\ge ab-3ra-3rb,\]or \[12r^2\ge (a-3r)(b-3r).\]Thus, $12r^2\ge (5-3r)^2$, so in particular $r>\sqrt{2}/2$. Thus, a unit square can be inscribed in the circle, which means a lattice point is inside the circle, so its not covered by the disks. Thus the claimed situation can't be achieved.
05.10.2020 02:53
No. Suppose it was possible. The main idea is to show that we can get a circle with radius at least $1/\sqrt2$ that does not intersect any disk; this circle then must contain a $1\times 1$ square; which contains a lattice point. Start with a point $O$ and a red circle centered at $O$ that doesn't intersect any circle. Take a homothety at $O$ till the new circle (color it blue) is tangent to some disk $\odot(O_1)$ at a point $P$. Take a homothety at $P$ till the new circle (color it green) is also tangent to some disk $\odot(O_2)$. Expand the green circle while keeping it tangent to $\odot(O_1)$ and $\odot(O_2)$ till it is tangent to a disk $\odot(O_3)$.
Claim: The final circle $\omega$ has radius at least $1/\sqrt2$. Proof: At each vertex of $\triangle O_1O_2O_3$, there is a circle at $O_i$ of radius $r_i$. If the three circles are not pairwise tangent, then you can increase one of the radii a bit, which decreases the radius of $\omega$. So WLOG assume the $\odot(O_i)$ are pairwise tangent. WLOG $\angle O_1OO_2 \le 120^\circ$. By LoC in $\triangle OO_1O_2$, we have \begin{align*} &-\frac12 \le \cos \angle O_1OO_2 = \frac{(r+r_1)^2+(r+r_2)^2-(r_1+r_2)^2}{2(r+r_1)(r+r_2)} \\ \implies& -(r+r_1)(r+r_2) \le (r+r_1)^2+(r+r_2)^2-(r_1+r_2)^2 \\ \implies& 3r^2\ge r_1r_2-3r(r_1+r_2) = (r_1-3r)(r_2-3r) - 9r^2 \ge (5-3r)^2-9r^2 \\ \implies& 12r^2 \ge (5-3r)^2 \\ \implies& r \ge \tfrac13(10\sqrt3-15) > 1/\sqrt2. \end{align*}This proves the claim. $\blacksquare$
15.08.2021 21:13
Quite an interesting problem - focusing locally on a set of three circles is relatively easily motivated making it slightly underwhelming in my opinion. We will prove that there is a circle of radius $\frac{1}{\sqrt{2}}$ that intersects no other circles in the plane which suffices as we get a $1$ by $1$ square in any such circle which will ultimately contain a lattice point. Take a circle $\omega_1$ and the closest circle to it, $\omega_2$, we can assume that $\omega_1$ and $\omega_2$ are tangent simply by increasing the radius of $\omega_1$ by $dist(\omega_1,\omega_2)$. Now, take one of the two circles tangent to both $\omega_1$ and $\omega_2$ on the exterior with radius $\frac{10}{\sqrt{3}}-5 > \frac{1}{\sqrt{2}}$, say $\Gamma$. $\textbf{Claim:}$ $\Gamma$ doesn't have two distinct intersections with any of the other circles in our tiling. $\textbf{Proof)}$ Consider a third circle $\omega_3$ that is, without loss of generality, tangent $\omega_1, \omega_2, \Gamma$, we shall prove that the radius of $\omega_3 \geq 5$ in which case we get that the two circles can't have two intersections.
Now, notice that whenever we increase the radius of $\omega_3$ ($\omega_1, \omega_2. \omega_3$ now have symmetric roles), any circle that was contained with the region created by $\omega_1, \omega_2, \omega_3$ with the former radii is still contained in the aforementioned region. We can consequently assume that the three circles all have radii $5$. Then, introducing the centers of the three circles, $O_1, O_2, O_3$ and computing the circumradius of $\triangle O_1O_2O_3$ which is equilateral (sidelength $10$), we have that the circle tangent to the three circles on the exterior has radius $\frac{10}{\sqrt{3}} - 5$ completing the proof. $\blacksquare$
18.07.2023 10:25
Note that for $0 \le i \le 2$, if we have a circle tangent to $i$ circles we can increase the radius of the circle, potentially moving it, to maintain the tangencies. Call this expanding. Thus, if we take a point not in the circles and expand, we eventually end up with a circle tangent to three circles in the family. We claim that this circle has radius at least $\frac{1}{\sqrt{2}}$, which implies a lattice point within the circle. Restrict our view to these three circles. By expanding these circles we can assume that they are pairwise tangent. Then, decreasing the radius of one of the circle and fixing the rest moves the tangency points with the other circles inward, as well as increasing the curvature of the arc. Thus, we can repeat until all three circles have radius $5$, at which point the result directly follows.
27.08.2023 19:14
This is a very boring problem. The answer is no; most of the diffculty is dealing with the details. It suffices to show that we can fit a circle of radius $\frac 1{\sqrt 2}$ somewhere between the circles, as then we will be able to fit a square of side length $1$. Consider any three circles in the plane; I will show that we will be able to fit such a circle between the three. Let $O_1, O_2, O_3$ be the centers, and let $O$ be the circumcenter of $O_1O_2O_3$. By Descartes' circle theorem, the circle with radius $\frac{10\sqrt 3 - 15}3 > \frac 1{\sqrt 2}$ centered at $O$ will not intersect any of the given circles, as the distance from a point on its rim to one of the $O_i$ is at least $5$. This is our desired circle.
29.12.2024 01:28
The answer is no. Claim: In the regions between any $3$ circles we can fit a circle of radius $\frac{1}{\sqrt{2}}$. Proof: Suppose we wanted to minimize the largest possible radius we can fit. Then clearly the $3$ circles must be tangent. If a circle has radius $>5$ then decreasing the radius will squish in the area more by convexity reasons. So the radius of a circle is minimized when the $3$ circles are pairwise tangent and have radius $5$ which gives us a possible radius of $\frac{10}{\sqrt{3}} - 5 > \frac{1}{\sqrt{2}}$.$\square$ However the range of $x$, and $y$ coordinates for a circle of radius $\frac{1}{\sqrt{2}}$ is $\sqrt{2} >1$. So by pigeonhole there must exist a lattice point so it is indeed impossible.