Does there exist a convex pentagon, all of whose vertices are lattice points in the plane, with no lattice point in the interior?
Problem
Source:
Tags: induction, The Geometry of Numbers
25.05.2007 03:25
No,there is not.suppose $A_1..A_5$is the smallest one($A_i(x_iy_i)$),then$x_i\equiv x_j,y_i\equiv y_j(mod 2)$,then the midpoint X is also lattic points.then X be in the interior or there is a smaller pentagon ( I will rewrite this solution tommorow )
25.05.2007 03:25
Hawk Tiger wrote: ( I will rewrite this solution tommorow ) reminder...
30.03.2008 15:22
If "MM" is what I think it is (Mathematics Magazine) then Peter's reference (MM, Problem 1409, Gerald A. Heur) is incorrect. Moreover, I think the real problem here is the following: Theorem 1 (Russian Mathematical Olympiad 2000). If $ ABCDE$ is a convex pentagon having the vertices on lattice points, then the "smaller" pentagon determined by the diagonals of $ ABCDE$ contains (in its interior or on its boundary) a lattice point. Although Kalva doesn't give a solution, I suspect the official solution is by combining a minimality argument with Pick's theorem several times (as in Titu Andreescu's 2000-2001 book). However, viewing Hawk Tiger's nice observation I can continue using his idea. Let me first rewrite in a more understandable way the things he said: Proof of Theorem 1. Since a lattice point can have only one of the four formes (odd, odd), (even, even), (odd, even), (even odd), two of the vertices of $ ABCDE$ will have the same form, and therefore the midpoint $ M$ of the segment determined by these two points is a lattice point as well. Therefore we have two cases: For sake of clarity, in the following I will denote by $ S(XYZUV)$ the "small" pentagon determined by the diagonals of $ XYZUV$: 1. Suppose $ M$ is in the interior of a diagonal of the pentagon $ ABCDE$; assume WLOG that $ M$ is the midpoint of $ AC$. If it lies inside (on the boundary) of $ S(ABCDE)$ we are done. If it doesn't, one of the two pentagons $ ABMDE$ and $ MBCDE$ is convex. Let this one be $ MBCDE$. This convex pentagon is a lattice pentagon contained in the initial $ ABCDE$. We observe that $ S(MBCDE)$ is included in $ S(ABCDE)$. Thus, by inducting on the number of lattice points contained in the initial convex pentagon, $ S(MBCDE)$ will contain a lattice point, and then so will $ S(ABCDE)$. We are done. 2. Suppose $ M$ is in the interior of an edge of the pentagon $ ABCDE$; assume WLOG that $ M$ is the midpoint of $ AB$. The pentagon $ MBCDE$ is convex. Now, we do not have anymore that $ S(MBCDE)$ is included in $ S(ABCDE)$, but we notice that $ S(MBCDE)$ is included in the reunion of $ S(ABCDE)$ with the triangle, say $ PQR$, bounded by the three lines $ BD$, $ BE$, $ AC$. Thus, by induction, $ S(MBCDE)$ contains a lattice point $ M'$. If $ M'$ is in $ S(ABCDE)$ we are done. Suppose it isn't. Thus, it is in $ PQR$, and the pentagon $ AM'CDE$ is convex, with $ S(AM'CDE)$ incldued in $ S(ABCDE)$. By induction, once again, we conclude that $ S(AM'CDE)$ contains a lattice point, and therefore (according to the inclusion argument) $ S(ABCDE)$ does as well. This proves Theorem 1. EDIT: Here is an older topic about Theorem 1 (which Darij pointed out to me), but there's no complete solution: http://www.mathlinks.ro/Forum/viewtopic.php?t=5743 (iura's remark is a part of the official solution).