Lattice points inside a circle

sfrick

New member
Joined
May 25, 2005
Messages
6
Can someone please help me with the following problem:

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.

I don't have a clue on how to set up and solve this problem.
 
Can you tell a bit more about the terms being used.
For example, is question asking us to find a largest circle that contains exactly three lattice points?
If not, is the center of these circles fixed? Say the origin?
You see that we need to know the definitions of your terms.
 
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.
 
Very well done!
You are correct on n=0, r=√(2)/2.
Correct on n=1, r=√(2).

Now for two lattice points say (1,1)&(2,1).
The center should be C(1.5,1) and r=√(5)/2 the distance from C to (1,2).

Now it is starting to get tricky.
For n=3, say (1,1), (1,2) & (2,1).
Let C(1.5-er,1.5-er) where er is for error say .01, radius distance of C from (1,2)+er/2; in this case about 0.712. This is to avoid the lattice point (2,2).

The case n=4, say (1,1), (1,2), (2,1) & (2,2), is easy.
C(1.5,1.5), r=√(10)/2 the distance from C to (1,3).

Thus you can see how the even cases are easily done.
It is the odd cases that take some work.

You try n=5, say (1,1), (1,2), (2,1), (2,2) & (1,3).
 
pka. Is there no common formula that can be used here? Also, if you use an error as you suppose for the odd ones how then can it still be a circle.
this is what is driving me crazy......
 
My suggestion is to use a graphing utility to see the case n=3.
For n=5, look at (1,2), (2,2), (3,2), (2,3) & (2,1).
Use the center C(2,2), radius r=√(2): the distance from C to (1,3).

For n=6, look at (1,1), (1,2), (1,3), (2,1), (2,2), & (2,3).
Use the center C(1.5,2), radius r=√(9)/2: the distance from C to (0,2).

NOW YOU TRY TO FIND A PATTERN!
 
How are you computing the radius for n=3?

I'm not seeing a pattern here. I think I'm brain dead!
 
I think n=3 and n=7 can be done if the radius is slightly greater then 1.0 like 1.00000000000009. Is that right?

Still can't find a pattern or common formula?

I'm getting a headache!!!!
 
I WILL DO THIS FOR YOU!
For n=3, say (1,1), (1,2) & (2,1).
To enclose exactly three lattice points we must use a ‘triangle’.
DID YOU GRAPH THIS?
The circumcenter is (1.5,1.5) and the circumradius is √(2)/2.
Therefore, for n=3 we need a radius greater than √(2)/2.
BUT, if we use the circumcenter (1.5,1.5) and a larger radius then we include (2,2)
That means FOUR lattice points! Thus we must “back away” from (1.5,1.5) while still including the triangle.
 
Ted.. I can graph this. My problem is computing the radius. I think I am having a problem understanding what you refer to as the circumradius and circumcenter. Can you explain.
 
Not much progress but...
I used the distance formulas to find that for n=3 the certer of the circle is at (1/6,1/6) which gives a radius of 25/18 = 1.3888... I'm assuming that the circle can go thru the lattice points (1,1), (-1,0) and (0,-1)
{I used (0,0), (0,1) and (1,0) which doesn't change the radius}
 
Top