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 100n^2/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<25³=5⁶. A továbbiakban feltesszük, hogy n $\ge$ 5⁶ és a sokszög csúcsainak száma legalább 5⁴.

Legyenek a sokszög oldalvektorai pozitív körüljárás szerint v₁,v₂,...,v_k, ahol k $\ge$ 5⁴ 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=|u₀|<|u₁| $\le$ |u₂| $\le$ |u₃| $\le$ ....

Legyen m tetszőleges pozitív egéz és tekintsük a u₀,...,u_m vektorokat. Ha mindegyik végpontja köré egy-egy egységnégyzetet rajzolunk, a négyzetek diszjunktak és benne vannak az |u_m|+1 sugarú körben, területük összege pedig m+1. Ezért m+1<(|v_m|+1)² $\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<100n^2/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.

A KöMaL 2007. májusi matematika feladatai

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.

Már regisztráltál?
Új vendég vagy?