KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

ELTE

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

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 points)

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 on problem A. 428.
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.


  • Problems in Mathematics of KöMaL, May 2007

  • Támogatóink:   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