Geometry - Lattice in Circle Problem

[sfrick]

Hi.

Can someone please help me with the following problem:

What is the radius of the largest circle whose interior contains exactly n lattice points.
Find the solution for n=0 through 9, and a general solution.

 

[Hurkyl]

Don't multiple post.

What have you tried? What thoughts have you had on the problem?

 

[sfrick]

Sorry for the multiple post. I posted it in the geometry section, but noticed that their was not much activity so I posted it here.

I haven't even been able to get a start on this one. The problem was given as what to look forward to in geometry next year. I'd thought it might be solved using algebra but got no where trying that.

So was hoping that someone might enlighten me.

 

[sfrick]

Can someone please help me with this problem. I just don't know how to do it.

 

[OlderDan]

Can someone please help me with this problem. I just don't know how to do it.

I assume by lattice you mean a regularly spaced set of points forming a square array. If not, you need to specify what it is.

What does "exactly n lattice points" mean? If it implies that the space surrounding a lattice point is associated with that point, so that a circle might include a fraction of the lattice point, then the problem is not too difficult. You just have to compare the area of a circle with the area associated with n lattice points.

I suspect that might not be what it means, in which case the problem is much more difficult. You need to draw a lattice and draw the biggest circle you can that includes n point and excludes all others. I don't see that leading to a general expression for n lattice points.

 

[sfrick]

OlderDan

Lattice = regularly spaced set of points forming a sqare array is correct.

Your 2nd paragraph assumtion is correct.

I need to find the solution for each n, when n=0,1,2 through 9.

A general formula (solution) so that I can plug in each n would do the trick, I guess

 

[sfrick]

Thanks for the reply. To further clarify, I assume that the lattice points are all 1 unit apart. The goal is to find the radius of a circle, whereby the circle is the largest it can be when encompassing 0 lattice points, then another with 1 lattice point, then 2 and so on up to 9 lattice points.
So in the one where n=0 (n=lattice pts.) I think the largest the circle could be would drawn so that the circumference of the circle would include 4 lattice pts on the circle. but none inside the circle. Does that sound right to you?
If n=1, I think the center of the circle would actually be the 1 lattice point inside the circle and the circumference would then have 4 lattice points on the circle.
So, if this thought process is right then there must be a formula for computing the radius for each problem (n=0 through 9), and maybe a gerneral formula where you could just plug in for n.

Does that help in further explaining it. I hope you can solve this as I have all but given up and it is driving me crazy.

 

[OlderDan]

I think I can draw the circles that are appropriate for n = 0 through 9, but I don't see them leading to a general formula. I agree with your view for n = 0 and n = 1. Then for n = 1 there is a diameter increase from \sqrt{2} to 2, with one point at the center, but only a small increase going to n = 2, with diameter \sqrt{5}, and then a small increase for n = 3. For n = 4 there is a nice symmetry that jumps the diameter up to \sqrt{10}, but the diameter for n = 5 has to be \sqrt{8}, which is smaller than the one for n = 4. n = 6 appears to me to be almost the same as n=4, since the slightest displacement of the symmetric n = 4 case takes you into n = 6 with and infinitesimal reduction in the diameter. n= 7 appears to be slightly larger than n=6, surrounding a 1, 3, 3 configuration, and n = 8 has a nice symmetry with diameter of \sqrt{13} surrounding a 1, 3, 3, 1 configuration. Finally, n = 9 also has nice symmetry surrounding 3, 3, 3 with a diameter of 4.

I have a diagram for these, with the ones that lack symmetry reasonably approximated. If you can agree with the ones I gave diameters for, let me know and then I will post it.

 

[sfrick]

Dan. You may be right on track. I have to find the radius for each solution so that is why I was thinking that there must be some formula that would apply. I was thinking about d=2r. When n=0, the radius would be 1/2 of the lattice unit. Then when n=1, the lattice point would be in the center and thus r=1. When n=2, the center of the circle would have to be a point between 2 lattice points, so r=1. I haven't quite figured out n=3 yet but I think r may = 1 or 1.25 here too. When n=4, r=1.5.
Does this seem right to you? Am I finding calculating the radius correctly?

How do you get n=3 or n=5? I can figure the even's but I can't seem to get the odds.

HELP! ^*^*^

 

[OlderDan]

Dan. You may be right on track. I have to find the radius for each solution so that is why I was thinking that there must be some formula that would apply. I was thinking about d=2r. When n=0, the radius would be 1/2 of the lattice unit. Then when n=1, the lattice point would be in the center and thus r=1. When n=2, the center of the circle would have to be a point between 2 lattice points, so r=1. I haven't quite figured out n=3 yet but I think r may = 1 or 1.25 here too. When n=4, r=1.5.
Does this seem right to you? Am I finding calculating the radius correctly?

How do you get n=3 or n=5? I can figure the even's but I can't seem to get the odds.

HELP! ^*^*^

You can make n = 0 bigger. Draw the circle through the 4 corners of one square. The diameter is the diagonal of the square. You are correct that the odd ones are more difficult. I have found a new way to do n = 5 that is essentially the same as n = 4 and n = 6. I am posting the diagram so you can see what I have. I will leave it to you to do the calculations of the diameters, which you can halve to get the radii. The calculations for n = 3 and n = 7 can be done if you take advantage of the fact that any triangle inscribed in a circle having a diameter as one of the sides must be a right triangle. It is easy to find the lengths of the chords drawn on the n = 3 and n = 7 figures, and not too difficult to find the angles between those chords and the diameters. You can then use trig to find the diameter lengths.

The way to think about the larger of the two circles for n = 5 is to look first at the n = 4 case. Then move the center of the circle toward one of the points on the circle, reducing the diameter slightly so the circle still touches that point. This will pull the circle in from all the other points that were on the circe. Then you can keep the diameter constant and shift the circle slightly so that the one remaining point on the circle moves to the inside.

The same idea applies to the n = 6 case, but it is a bit trickier. Here you want to move the center of the circle toward one of the four inscribed points of the n = 4 case. That will cause 4 additional points to be enclosed. Then reduce the radius slightly to eliminate two of those. In the diagram I shifted the center of the n = 6 circle toward the upper left point.