KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

Problem A. 428. (May 2007)

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.

(5 pont)

Deadline expired on 15 June 2007.


Solution. The number of vertices is trivially at most 4n, so we can assume that n\ge56 and the number of vertices is at least 54.

Let the side vectors of the polygon be (in counterclockwise order) v1,v2,...,vk, where k\ge54 is the number of vertices. Since the perimeter of the convex polygon cannot be greater than the perimeter of the square containing it,

 \sum_{i=1}^k|v_k| \le 4n. (1)

Sort the integer vectors in the plane by their lengths: u_0,u_1,u_2,\ldots, ahol 0=|u0|<|u1|\le|u2|\le|u3|\le....

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\pi, and

 |v_m| > \sqrt{\frac{m+1}\pi} -1 > \frac{\sqrt{m}}2-1.

Substituting into (1),


4n \ge 
\sum_{i=1}^k |v_i| \ge
\sum_{i=1}^k |u_i| \ge
\sum_{i=1}^k \left(\frac{\sqrt{i}}2-1\right)
>\frac13k^{3/2}-k \ge \frac13k^{2/3} - \frac1{5^2}k^{3/2} >
\frac14k^{3/2}.

Hence,

k<(16n)2/3<100n2/3.


Statistics:

8 students sent a solution.
5 points:Gyenizse Gergő, Kónya 495 Gábor, Lovász László Miklós, Nagy 224 Csaba, Nagy 235 János, Nagy 314 Dániel, Tomon István.
Unfair, not evaluated:1 solution.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley