Problem A. 428. (May 2007)
A. 428. Given a convex lattice polygon such that both x and ycoordinates of each vertex lie in the interval [0,n]. Show that the number of vertices is less than 100n^{2/3}.
(5 pont)
Deadline expired on 15 June 2007.
Solution. The number of vertices is trivially at most 4n, so we can assume that n5^{6} and the number of vertices is at least 5^{4}.
Let the side vectors of the polygon be (in counterclockwise order) v_{1},v_{2},...,v_{k}, where k5^{4} is the number of vertices. Since the perimeter of the convex polygon cannot be greater than the perimeter of the square containing it,
 (1) 
Sort the integer vectors in the plane by their lengths: , ahol 0=u_{0}<u_{1}u_{2}u_{3}....
For an arbitrary positive integer m, consider the vectors u_{0},...,u_{m}. Drawing a unit square around their endpoints, these squares do not overlap and they are contained in a circle of radius u_{n}+1. Therefore m+1<(v_{m}+1)^{2}, and
Substituting into (1),
Hence,
k<(16n)^{2/3}<100n^{2/3}.
Statistics:
