From:           David Eppstein <eppstein@ics.uci.edu>
Subject:        Re: Russian math olympiad problem on lattice points
Newsgroups:     sci.math
Organization:   UC Irvine, Dept. of Information & Computer Science
Date:           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/