KöMaL - Középiskolai Matematikai és Fizikai Lapok
Belépés
Regisztráció
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum
Versenykiírás
Tudnivalók
Nevezési lap
Feladatok
Eredmények
Korábbi évek
Arcképcsarnok
Munkafüzet

Rendelje meg a KöMaL-t!

MBUTTONS

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

Az A. 428. feladat (2007. május)

A. 428. Egy konvex rácssokszög minden csúcsának x és y koordinátája is a [0,n] intervallumba esik. Mutassuk meg, hogy a csúcsok száma kevesebb, mint 100n2/3.

(5 pont)

A beküldési határidő 2007. június 15-én LEJÁRT.


Megoldásvázlat. A csúcsok száma triviálisan legfeljebb 4n, ezért az állítás semmitmondó, ha n<253=56. A továbbiakban feltesszük, hogy n\ge56 és a sokszög csúcsainak száma legalább 54.

Legyenek a sokszög oldalvektorai pozitív körüljárás szerint v1,v2,...,vk, ahol k\ge54 a csúcsok száma. Mivel a sokszög konvex, kerülete legfeljebb akkora, mint a tartalmazó négyzet kerülete, tehát

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

Rendezzük sorba a sík egész koordinátájú vektorait hosszúság szerint: u_0,u_1,u_2,\ldots, ahol 0=|u0|<|u1|\le|u2|\le|u3|\le....

Legyen m tetszőleges pozitív egéz és tekintsük a u0,...,um vektorokat. Ha mindegyik végpontja köré egy-egy egységnégyzetet rajzolunk, a négyzetek diszjunktak és benne vannak az |um|+1 sugarú körben, területük összege pedig m+1. Ezért m+1<(|vm|+1)2\pi, amiből

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

Ezt a becslést behelyettesjtve (1)-be,


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

Teljes indukcióval igazolható, hogy \sum_{i=1}^k\sqrt{i}>\frac23k^{3/2}. Ezt alkalmazva,

 4n >\frac13k^{3/2}-k \ge \frac13k^{2/3} - \frac1{5^2}k^{3/2} >
\frac14k^{3/2}.

Tehát

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


Statisztika:

8 dolgozat érkezett.
5 pontot kapott: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.
Nem versenyszerű:1 dolgozat.

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