Author |
Topic: Circle containing k lattice points (Read 724 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
Circle containing k lattice points
« on: Jun 14th, 2007, 10:28pm » |
 Quote  Modify
|
Consider the 2D plane. Each point (m,n) where m and n are integers is called a lattice point.
Show that, for any natural number k, there exists a circle in the plane which has exactly k lattice points contained inside it.
|
|
 IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Circle containing k lattice points
« Reply #1 on: Jun 15th, 2007, 2:59am » |
Quote Modify
|
Center the circles at the point that has incommensurable coordinates?
|
|
IP Logged |
|
|
|
Miles
Junior Member
Cambridge, England
Gender:
Posts: 95
|
|
Re: Circle containing k lattice points
« Reply #2 on: Jun 15th, 2007, 4:46am » |
Quote Modify
|
| hidden: | So I think what Barukh's clue is getting at is to imagine a circle centred on (a,b) which we gradually expand. As the radius (r) increases it will clearly take in more and more points on the lattice. The question is now whether there is any radius at which two (or more) points on the lattice both lie on the circle, so that as the circle expands further the number of points inside the lattice jumps by 2 (or more) and we fail in our task.
The requirement in bold would require that there are two distinct solutions (m1, n1) and (m2, n2) of (m-a)^2 + (n-b)^2 = r^2.
A bit of expansion and subtraction leads to
(m1^2 - m2^2) + (n1^2 - n2^2) = 2a.(m1-m2) + 2b.(n1-n2).
The left hand side is a non-zero integer. But since at least one of (m1-m2) and (n1-n2) is non-zero, then provided a and b fit the incommensurable requirement (eg a = sqrt(2), b = pi; I am bit hazy on the term incommensurable, so I hope that's right) then there is no way the right hand side can be an integer. This guarantees that for any r, there is never more than one (m,n) lying on the circle. |
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Circle containing k lattice points
« Reply #3 on: Jun 15th, 2007, 10:33pm » |
Quote Modify
|
Exactly, Miles. 
I just noticed that any circle passing through 2 lattice points must be centered at a straight line with rational coefficients.
on Jun 15th, 2007, 4:46am, Miles wrote:
b = 1 will also do.
|
| « Last Edit: Jun 16th, 2007, 12:01am by Barukh » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Circle containing k lattice points
« Reply #4 on: Jun 16th, 2007, 7:07am » |
Quote Modify
|
on Jun 15th, 2007, 10:33pm, Barukh wrote:Exactly, Miles.
I just noticed that any circle passing through 2 lattice points must be centered at a straight line with rational coefficients.
b = 1 will also do.
|
|
but then which point enters first? (1,0) or (1,2)?
If either co-ordinate is half-integer, then there will be pairs of points entering the circle simultaneously which share the same co-ordinate on the other axis.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Circle containing k lattice points
« Reply #5 on: Jun 17th, 2007, 5:57am » |
Quote Modify
|
on Jun 16th, 2007, 7:07am, rmsgrey wrote:| If either co-ordinate is half-integer, then there will be pairs of points entering the circle simultaneously which share the same co-ordinate on the other axis. |
|
Of course! So stupid...
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Circle containing k lattice points
« Reply #6 on: Jun 20th, 2007, 8:55pm » |
Quote Modify
|
Strictly speaking, the point (a,b) will suffice if the numbers 1, a, b, are linearly independent over the rationals. So ( 2,  ) will suffice, because any rational combination of 1 and 2 is algebraic, while isn't. However, I believe it is unknown whether (e, ) satisfies this condition.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Circle containing k lattice points
« Reply #7 on: Jul 26th, 2007, 10:29pm » |
Quote Modify
|
How about this generalization, which seems to require a different approach:
Let S be a countably infinite, discrete subset of the plane [or any Rn]. Show that, for any natural number k, there exists a circle [or (n-1)-sphere] which has exactly k elements of S contained inside it.
|
|
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Circle containing k lattice points
« Reply #8 on: Aug 7th, 2007, 4:10pm » |
Quote Modify
|
Eigenray's generalization suggests that there is a solution to Aryabhatta's problem accessible to a first year high school student.
|
|
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Circle containing k lattice points
« Reply #9 on: Aug 19th, 2007, 8:40pm » |
Quote Modify
|
I have some questions (perversely asking for Eigenray's "different approach"). Assume Eigenray's hypothesis for the plane: S is a countably infinite subset of the plane.
A problem similar to Aryabhatta's appeared in a math contest. The proof that accompanied the problem stated, without proof, that there exists a point in the plane whose distances from each point in S are all different. Is this fact so obvious that no proof is required?
If "circle" is replaced by "rectangle", Aryabhatta's problem becomes trivial but Eigenray's problem remains a challenge. Does Eigenray's "different approach" still work, perhaps with minor modifications?
How about if "circle" is replaced by "equilateral triangle"?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Circle containing k lattice points
« Reply #10 on: Aug 20th, 2007, 12:27am » |
Quote Modify
|
on Aug 19th, 2007, 8:40pm, ecoist wrote:| A problem similar to Aryabhatta's appeared in a math contest. The proof that accompanied the problem stated, without proof, that there exists a point in the plane whose distances from each point in S are all different. Is this fact so obvious that no proof is required? |
|
The points at the same distance from 2 points is a straight line. To have all distances different, you only need to avoid a countably infinite set of lines. I think there is an argument that a countable set of lines cannot cover the plane.
|
|
IP Logged |
|
|
|
ecoist
Senior Riddler
Gender:
Posts: 405
|
|
Re: Circle containing k lattice points
« Reply #11 on: Aug 20th, 2007, 9:55am » |
Quote Modify
|
Your comment, Grimbal, is sufficient proof to my mind, but let me add this. Since there are as many line slopes as there are reals, there exists a line L not parallel to any of the given countably many lines. Hence L meets those countably many lines in at most countably many points on L. Therefore, there exists a point on L which lies on none of the given countably many lines.
Now, what about the remaining two questions? I had more trouble answering the second question than I did the third.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Circle containing k lattice points
« Reply #12 on: Aug 20th, 2007, 10:03pm » |
Quote Modify
|
My approach was only to note that Barukh's approach in reply #3 generalized to any countable set of lines in the plane. Or in fact, to any countable set of hyperplanes in n-space, simply by considering Lebesgue measure. But one can also generalize ecoist's proof by induction on the dimension.
on Aug 19th, 2007, 8:40pm, ecoist wrote:If "circle" is replaced by "rectangle", ...
How about if "circle" is replaced by "equilateral triangle"? |
|
Actually, there's something about these two shapes that makes the problem easier, in some sense: they can be grown moving one edge at a time.
A stronger statement holds: There exists a point P in the plane such that for any n>2 and any k, there is a regular n-gon centered at P containing exactly k points.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print