Inspired by Marta Reece

Geometry Level 5

There is a circle on a regular grid, the coordinates of whose center are ( p , q ) (p, q) .

If the circle goes through exactly n n grid points and neither p p nor q q is rational, find the maximum value of n n .

1 2 3 4 5 6 7

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Shaun Leong
Jul 5, 2017

Suppose that 3 or more rational points lie on it. Thus the circle is the circumcircle of the triangle formed by 3 of those points. By coordinate geometry, the centre is the intersection of the perpendicular bisectors, which is found by solving 2 linear equations. Thus the center is rational, a contradiction.

As pointed out by Zee Ell, I should provide a construction for completeness.

One such construction is the circle centred at ( 2 , 2 ) (\sqrt2,\sqrt2) with radius 5 2 2 \sqrt{5-2\sqrt2} . This passes through ( 0 , 1 ) (0,1) and ( 1 , 0 ) (1,0) .

For the sake of completeness, you should describe such a construction for n = 2.

E.g.: by working backwards, we can take any two (distinct) gridpoints (our circle line will go through these points).

Now, if we determine the equation of the perpendicular bisector of the line segment determined by these two points, we will get an equation ( y = mx + c) with rational coefficients (gradient and intercept).

At this point, we can substitute any irrational value for x. It is easy to see, that we will have an irrational y value as well, giving us the coordinates of the centre of the circle (both coordinates are irrational, with exactly 2 gridpoints on the circle, as required).

Zee Ell - 3 years, 11 months ago

The area of a circle with a radius of r r is r 2 π r^2\pi , so r 2 π > r 2 π r^2\pi>\left \lfloor r^2\pi \right \rfloor . Since the Blichfeldt's Theorem it can be translated, such that it covers minimum r 2 π + 1 \left \lfloor r^2\pi \right \rfloor +1 grid points.

If we give a positive integer, let this number be N N , then there exist a circle on the grid, which covers exactly N N points. This is because: Let the origo be O ( 2 ; 3 ) O(\sqrt{2}; \sqrt{3}) . Now the circle can't contain more than 1 point, because if there were, then the perpendicular to the midpoint of the segment between the points equation would be a x + b y = c ax+by=c , where a , b , c a, b, c are integers, and a 2 + b 3 = c a\sqrt{2}+b\sqrt{3}=c would have to be true, but squaring it: 6 = c 2 2 a 2 3 b 2 2 a b \sqrt{6}=\dfrac{c^2-2a^2-3b^2}{2ab} which is impossible, since 6 \sqrt{6} is irrational.

Now write a small circle over O O , which doesn't cover any point, and then increase the radius constantly. The growing circle will only go through 1 point, so we can increase the circle, such that it covers exactly N N points.

With this continuous increase it is also possible to add a circle on the square grid that does not have a grid point on its perimeter, but its radius is arbitrarily large.

But if we write a big circle around a grid point, it is only a little easier to avoid grid points, the more true it will be:

The distance of a circle around a grid point from its nearest grid point can be tapped down if the radius of the circle is sufficiently large (János Surányi)

It is a bit unclear from your solution, why is n ≤ 2. You only mention n=0 as a possibility and show a concrete example regarding n = 1, but I cannot see any proof (or example) regarding n≤2 or at least n=2 here and now.

Please also see Shaun Leong's solution with my comments.

Zee Ell - 3 years, 11 months ago

I don't quite follow your argument.

  1. You seem to be mixing up "covers N grid points in the interior + boundary" with "contains N grid points on the boundary".
  2. The circle can be translated, but you cannot arbitrarily choose the amount of translation. Review the proof of the theorem to understand which translations would work.

Calvin Lin Staff - 3 years, 11 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...