From:David Eppstein <eppstein@ics.uci.edu>Subject:Re: Russian math olympiad problem on lattice pointsNewsgroups:sci.mathOrganization:UC Irvine, Dept. of Information & Computer ScienceDate:Thu, 17 Aug 2000 14:48:40 -0700

> > >: > : Given convex pentagon with vertices on lattice points. > > >: > : Prove, that there is lattice point inside or on the border > > >: > : of the "small" convex pentagon, cutted by "large" pentagon > > >: > : diagonales. Ok, let the given pentagon be abcde. Let the "small" pentagon of a pentagon P be denoted S(P). As someone (Peter Montgomory?) noted, some two of the five points have the same parity, so one of the ten edges connecting pairs of vertices has a lattice midpoint m. If m is in S(abcde), we are done. Else, if m is on an interior diagonal of the pentagon, say m = (a+c)/2, then one of the two pentagons abmde and mbcde is convex, say mbcde, and S(mbcde) is a subset of S(abcde). By induction on number of lattice points contained in the original pentagon, S(mbcde) contains a lattice point, which is also a lattice point of S(abcde). Else, suppose m is on an edge, say ab, and consider the convex pentagon mbcde. Now, S(mbcde) is not a subset of S(abcde), but it is a subset of the union of S(abcde) and the triangle T formed by lines ac, bd, and be. As before, by induction, S(mbcde) contains a lattice point f. If f is in S(abcde), we are done. If f is not in S(abcde), it is in T, and afcde is a convex pentagon such that S(afcde) is a subset of S(abcde); by induction a third time, S(afcde) contains a lattice point, which is also a lattice point in S(abcde). QED. Look ma, no Pick's theorem or anything... -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/