wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Circle containing k lattice points
        
(Message started by: Aryabhatta on Jun 14^th, 2007, 10:28pm)

Title: Circle containing k lattice points
Post by Aryabhatta on Jun 14^th, 2007, 10:28pm

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.

Title: Re: Circle containing k lattice points
Post by Barukh on Jun 15^th, 2007, 2:59am

[hide]Center the circles at the point that has incommensurable coordinates[/hide]?

???

Title: Re: Circle containing k lattice points
Post by Miles on Jun 15^th, 2007, 4:46am

[hideb]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.[/hideb]

Title: Re: Circle containing k lattice points
Post by Barukh on Jun 15^th, 2007, 10:33pm

Exactly, Miles. :D

I just noticed that [hide]any circle passing through 2 lattice points must be centered at a straight line with rational coefficients.[/hide]

on 06/15/07 at 04:46:15, Miles wrote:

eg a = sqrt(2), b = pi

b = 1 will also do.

Title: Re: Circle containing k lattice points
Post by rmsgrey on Jun 16^th, 2007, 7:07am

on 06/15/07 at 22:33:02, Barukh wrote:

Exactly, Miles. :D

I just noticed that [hide]any circle passing through 2 lattice points must be centered at a straight line with rational coefficients.[/hide]

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.

Title: Re: Circle containing k lattice points
Post by Barukh on Jun 17^th, 2007, 5:57am

on 06/16/07 at 07:07:16, 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...

Title: Re: Circle containing k lattice points
Post by Eigenray on Jun 20^th, 2007, 8:55pm

Strictly speaking, the point (a,b) will suffice if [hide]the numbers 1, a, b, are linearly independent over the rationals. So (http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif2, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif) will suffice, because any rational combination of 1 and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif2 is algebraic, while http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif isn't[/hide]. However, I believe it is unknown whether (e, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif) satisfies this condition.

Title: Re: Circle containing k lattice points
Post by Eigenray on Jul 26^th, 2007, 10:29pm

How about this generalization, which seems to require a different approach:

Let S be a countably infinite, discrete subset of the plane [or any Rⁿ]. 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.

Title: Re: Circle containing k lattice points
Post by ecoist on Aug 7^th, 2007, 4:10pm

Eigenray's generalization suggests that there is a solution to Aryabhatta's problem accessible to a first year high school student.

Title: Re: Circle containing k lattice points
Post by ecoist on Aug 19^th, 2007, 8:40pm

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"?

Title: Re: Circle containing k lattice points
Post by Grimbal on Aug 20^th, 2007, 12:27am

on 08/19/07 at 20:40:24, 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.

Title: Re: Circle containing k lattice points
Post by ecoist on Aug 20^th, 2007, 9:55am

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.

Title: Re: Circle containing k lattice points
Post by Eigenray on Aug 20^th, 2007, 10:03pm

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 08/19/07 at 20:40:24, 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: [hide]they can be grown moving one edge at a time[/hide].

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.