Lattice point problem from Stewart's Calculus

[issacnewton]

Homework Statement

A lattice point in the plane is a point with integer coordinates. Suppose that circles with
radius r are drawn using all lattice points as centers. Find the smallest value of r such that
any line with slope $(2/5)$ intersects some of these circles

Relevant Equations

equation of a line, distance from a point to the line

So, the way I understand this problem, I think the line $y = (2/5)x + c$ should only intersect some of the circles drawn around the lattice points. But, I am not sure I even understand the problem statement. Can the line pass through the lattice points ? My first goal is to understand the problem statement.

Thanks $\smile$

 

[pasmith]

Homework Statement: A lattice point in the plane is a point with integer coordinates. Suppose that circles with
radius r are drawn using all lattice points as centers. Find the smallest value of r such that
any line with slope $(2/5)$ intersects some of these circles
Relevant Equations: equation of a line, distance from a point to the line

So, the way I understand this problem, I think the line $y = (2/5)x + c$ should only intersect some of the circles drawn around the lattice points. But, I am not sure I even understand the problem statement. Can the line pass through the lattice points ? My first goal is to understand the problem statement.

Thanks $\smile$

It's not that the line "should intersect some", as opposed to all, such circles, but that the line must intersect at least one such cricle.

In fact, if a line of slope 2/5 intersects one such circle then it intersects infinitely many, because if it intersects the circle centered at (n,m) then it must also intersect the circles centered at (n+5k,m+2k) for every integer k.

 

[issacnewton]

How did you come about the point $(n + 5k, m + 2k)$ ?

 

[fresh_42]

Imagine circles with radius $1/4$ and lines $y=c.$ Then all lines with $c\in (-1/4\, , \,+1/4) + \mathbb{Z}$ intersect (infinitely many) circles, and all lines with $c\in [1/4\, , \,3/4]+\mathbb{Z}$ do not intersect any circle around the lattice points; assuming that a tangent does not count as an intersection. The smallest radius such that a parameter $c$ cannot be found is $1/2 + \varepsilon ;$ assuming that a tangent at $(0\, ,\, 1/2)$ does not count as an intersection. In the case a tangent counts as an intersection, the answer is $1/2$ for those parallel lines.

The problem statement says: find the minimal radius so that it is impossible to avoid intersections for any choice of $c.$

 

[issacnewton]

for horizontal lines (say y = 1/2), I can see that minimal radius is $1/2$, so that lines only are tangent to the circles with centers at the lattice points. But how do we generalize this to the lines of the form $y = mx + c$ ?

 

[WWGD]

for horizontal lines (say y = 1/2), I can see that minimal radius is $1/2$, so that lines only are tangent to the circles with centers at the lattice points. But how do we generalize this to the lines of the form $y = mx + c$ ?

What do you mean by just saying $y=1/2$? How are they spaced out from each other?

 

[issacnewton]

I am saying that if the line is $y = 1/2$, then the minimum radius of the circles should be $r = 1/2$ so that this line touches infinitely many circles at tangent point. I have no idea how to go about a general line like $y = mx + c$.

 

[fresh_42]

for horizontal lines (say y = 1/2), I can see that minimal radius is $1/2$, so that lines only are tangent to the circles with centers at the lattice points. But how do we generalize this to the lines of the form $y = mx + c$ ?

That's the exercise, isn't it? I would first check whether it is easier to work with horizontal lines and a rotated coordinate system, but I'm not sure, whether this is an improvement. @pasmith 's hint in post #2 is a good starting point to limit the problem to a finite area around the origin. And you should first answer your question in post #3.

 

[issacnewton]

fresh_42, I can't understand how pasmith came about point $(n+5k,m+2k)$. So, could not follow the hint

 

[fresh_42]

fresh_42, I can't understand how pasmith came about point $(n+5k,m+2k)$. So, could not follow the hint

Prove it! The lattice is symmetric, and so are the circles then. The hint says that you can shift the origin of the coordinate system by $(5,2)+\mathbb{Z}$ and you will find the exact same geometric situation.

Edit: My suspicion is, that the minimal radius is zero, i.e. that any line $y=0.4x+c$ always comes arbitrarily close to some center sooner or later because $2$ and $5$ are coprime. If not, then you have found your minimum. Just calculate the distance of the line to all possible centers as a function of $c$ and $r.$

 

[issacnewton]

should all circles have the same radius ?

 

[fresh_42]

should all circles have the same radius ?

Sure. How could you conclude anything if not?

 

[issacnewton]

Ok, let $(x_1, y_1)$ be the point of intersection of the line $y = (2/5)x + c$ and the circle of radius $r$ with center at $(n, m)$. The equation of such a circle is

$$ (x - n)^2 + (y - m)^2 = r^2 $$

Since $(x_1, y_1)$ also lies on this circle, we have

$$ (x_1 - n)^2 + (y_1 - m)^2 = r^2 $$

Now, lets do coordinate translation where all points are shifted $5k$ units right and $2k$ units up. So, $(x_1, y_1)$ gets translated to $(x_1 + 5k, y_1 + 2k)$ and $(n, m)$ gets translated to $(n + 5k, m + 2k)$. Its easy to verify that $(x_1 + 5k, y_1 + 2k)$ satisfies the equation of the line $y = (2/5)x + c$ and also satisfies equation of the circle with center at $(n + 5k, m + 2k)$ and radius $r$. This proves that if the line with slope $2/5$ intersects a circle with center at $(n,m)$ then, it will also intersect the circle with center at $(n + 5k, m + 2k)$. This was stated in post # 2. So, how do I proceed now ?

 

[issacnewton]

can anybody guide me further in this problem ?

 

[fresh_42]

What is the distance $d$ between the straight $y=\dfrac{2}{5}x+c$ and the circle $(x-n)^2+(y-m)^2=r^2\text{ ?}$ This distance is a function $d=d(c,r,n,m).$ Which is it?

 

[issacnewton]

If $y = (2/5)x + c$ is tangent to the circle, then the distance from the center $(n,m)$ to the tangent is given by the following formula from geometry

$$ d = \frac{|2n - 5m + 5c|}{\sqrt{2^2 + (-5)^2}} = \frac{|2n - 5m + 5c|}{\sqrt{29}} $$

 

[pasmith]

If $y = (2/5)x + c$ is tangent to the circle, then the distance from the center $(n,m)$ to the tangent is given by the following formula from geometry

$$ d = \frac{|2n - 5m + 5c|}{\sqrt{2^2 + (-5)^2}} = \frac{|2n - 5m + 5c|}{\sqrt{29}} $$

How does the distance from a line to the edge of a circle of radius r not depend on r? Please show your working.

EDIT: Eliminating y between y = (2/5)x + c and (x-n)^2 +(y-m)^" = r^2 will give a quadratic in x. The line is tangent to the circle when the discriminant of this quadratic vanishes.

 

[issacnewton]

Ok, maybe I made a mistake. After plugging $y = (2/5)x + c$ into $(x-n)^2 + (y - m)^2 = r^2$, I get the following quadratic equation in $x$

$$ \frac{29}{25}x^2 + \left[ -2n + \frac{4}{5}(c-m) \right] x + n^2 + (c-m)^2 - r^2 = 0 $$

As suggested by pasmith, tangent occurs when there is only one intersection point. So, discriminant of this quadratic must vanish

$$ D = \left[ -2n + \frac{4}{5}(c-m) \right]^2 - 4\left( \frac{29}{25} \right) (n^2 + (c-m)^2 - r^2) = 0 $$

$$ D = \frac{1}{25} \left[ 116r^2 - 16n^2 -100(c-m)^2 -80n(c-m) \right] = 0$$

$$ 116r^2 = 16n^2 +100(c-m)^2 + 80n(c-m) $$

How does this help us ?

 

[fresh_42]

I'm not sure what exactly you did here. I think you should calculate the length $d(c,n,m,r)$ of the red line

where the straight is $y=\dfrac{2}{5}x+c$ and the circle is $(x-n)^2+(y-m)^2=r^2.$ The problem statement then reads: Find the minimum value of $r$ such that for any value $c$ there exists $n,m$ such that $d(c,n,m,r)\leq r.$ You have to investigate this inequality with an arbitrary parameter value $c$ and a solution $(n,m).$ We need to know $d(c,n,m,r).$

 

[issacnewton]

fresh_42, is $d$ the perpendicular distance from the line $y = (2/5)x + c$ and the center of the circle ? I don't think I understand what you are saying. My last post was reply to pasmith's post. sorry for misunderstanding.

 

[fresh_42]

fresh_42, is $d$ the perpendicular distance from the line $y = (2/5)x + c$ and the center of the circle ? I don't think I understand what you are saying. My last post was reply to pasmith's post. sorry for misunderstanding.

Yes. The perpendicular is the shortest distance between the line and the circle. The problem asks for a specific radius $r_0$ such that ...

... any line with slope $(2/5)$ intersects some of these circles.

That means, regardless of the choice of $c$ (=any line with slope $0.4$), i.e. for all values $c,$ the line has to intersect at least one circle (=some of these circles), i.e. there exists at least one pair $(n,m)$ such that the (red) distance $d=d(c,n,m,r)$ between the line and the circle is less than the radius $r$ in order to intersect it.

This means in a formula: Find
$$
r_0=\min\{r\geq 0\,|\,\forall\,c\in \mathbb{R}\,\exists\, (n,m)\in \mathbb{Z}^2\, : \,d(c,n,m,r)\leq r\}
$$
The first step is to determine this distance $d.$
The second step is to examine under which conditions $d(c,n,m,r)\leq r$ has always a solution, no matter what the parameter $c$ is. This means in particular that we cannot have roots of negative numbers.
The last step is to determine the minimal value $r$ such that this condition always holds.

So whatever you do, we need to know $d=d(c,n,m,r),$ the length of the red line, the length between the point $C=(n,m)$ and the point $P$ on the straight $L\, : \,y=0.4\,x+c$ that is perpendicular to the circle. I would start by finding the equation that describes the red line, then calculate the point $P$ on $L$ that is perpendicular to the circle with center at $C=(n,m)$ and radius $r,$ then determine $d=d(c,n,m,r)= |\overline{PC}|$ and analyze the condition $d\leq r.$

 

[issacnewton]

I have found solution on some site which I will explain here. As I have already shown that if the line $y = (2/5)x + c$ intersects the circle $(x-n)^2 + (y-m)^2 = r^2$, then it will also intersect the circle $(x-n-5k)^2 + (y -m-2k)^2 = r^2$, where $k \in \mathbb{Z}$. Now, consider the points $(0,0)$ and $(5,2)$. Lets draw two circles of same radius with these two points as their centers. Also draw a line $y = (2/5)x + c$ with the value of $c$ such that the line is a tangent in the fourth quadrant. Now, lets also draw a circle of the same radius with the point $(3,1)$ as the center. Now all three circles have same radius. Now, reduce the radius so that the line is tangent to the circle with center $(3,1)$. And draw two perpendiculars to the line passing through $(0,0)$ and $(3,1)$. We need to get the coordinates of points P and Q as shown in the attached diagram. The equation of the perpendicular line passing through the origin is $y = (-5/2)x$ and this intersects the circle $x^2 + y^2 = r^2$ at point P. Solving for x and y, the coordinates of point P would be

$$ x = \frac{2}{\sqrt{29}}r , y = \frac{-5}{\sqrt{29}}r $$

Now, for point Q, equation of the perpendicular line passing through $(3,1)$ is $(y-1) = (-5/2)(x-3)$ and this intersects the circle $(x-3)^2 + (y-1)^2 = r^2$ at point Q. Note that the x coordinate of Q would be less than 3. So, taking that into account and doing some algebra, we have the coordinates of point Q

$$ x = 3 - \frac{2}{\sqrt{29}}r, y = 1 + \frac{5}{\sqrt{29}}r $$

Now, points P and Q lie on the line $y = (2/5)x + c$. So, the slope of the line is $(2/5)$. Using slope formula and the above given coordinates of P and Q, we have

$$ \frac{2}{5} = \frac{1 + \frac{5}{\sqrt{29}}r - \left( \frac{-5}{\sqrt{29}}r \right)}{ 3 - \frac{2}{\sqrt{29}}r - \frac{2}{\sqrt{29}}r} = \frac{\sqrt{29} + 10r}{3 \sqrt{29} - 4r} $$

Solving this, we get $r = \frac{\sqrt{29}}{58}$. So, this should be the minimum radius.
Thanks fresh_42 and others for all the help. $\smile$