A. 428. Given a convex lattice polygon such that both x- and y-coordinates of each vertex lie in the interval [0,n]. Show that the number of vertices is less than 100n2/3.
Deadline expired on 15 June 2007.
Solution. The number of vertices is trivially at most 4n, so we can assume that n56 and the number of vertices is at least 54.
Let the side vectors of the polygon be (in counterclockwise order) v1,v2,...,vk, where k54 is the number of vertices. Since the perimeter of the convex polygon cannot be greater than the perimeter of the square containing it,
Sort the integer vectors in the plane by their lengths: , ahol 0=|u0|<|u1||u2||u3|....
For an arbitrary positive integer m, consider the vectors u0,...,um. Drawing a unit square around their end-points, these squares do not overlap and they are contained in a circle of radius |un|+1. Therefore m+1<(|vm|+1)2, and
Substituting into (1),
|Statistics on problem A. 428.|
Problems in Mathematics of KöMaL, May 2007