Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Az A. 555. feladat (2012. február)

A. 555. Egy n×n×n-es kockarács pontjait kiszíneztük n színnel úgy, hogy mindegyik színt pontosan n2-szer használtuk fel. Igazoljuk, hogy van olyan rácsegyenes, ami párhuzamos a kocka valamelyik élével, és a rácsnak legalább \root3\of{n} különböző színű pontján átmegy.

(5 pont)

A beküldési határidő 2012. március 12-én LEJÁRT.


Megoldás. A megoldáshoz felhasználjuk a 1992. évi Nemzetközi Matematikai Diákolimpia 5. feladatának állítását (az állítást kissé átfogalmaztuk):

Lemma. Ha S a háromdimenziós tér pontjainak egy véges halmaza, és Sx, Sy, illetve Sz jelöli rendre az S pontjainak az xy-, zx-, ill. xy-síkokra vett merőleges vetületeiből álló halmazokat, akkor

|S|2\le|Sx|.|Sy|.|Sz|.

A Lemma bizonyítása megtalálható például itt.

A felhasznált színek legyenek C1,...,Cn, és minden i=1,...,n-re legyen Si a Ci színű pontok halmaza. A feltétel szerint minden színt pontosan n2-szer használunk, tehát |Si|=n2. A rácskockát a tengelyekkel párhuzamosan összesen 3n2 egyenes metszi; jelöljük ezeket L1,L2,...,L3n2-tel.

Építsünk páros gráfot a következőképpen. A két csúcsosztály legyen {L1,L2,...,L3n2}, illetve {C1,C2,...,Cn}. Az Li egyenest és a Cj pontot akkor kössük össze éllel, ha az Li egyenes tartalmaz legalább egy Cj színú pontot.

Az Sj halmaz yz-, zx, illetve xy-síkra vett merőleges vetülete pontosan annyi pontból áll, mint ahány, az x-, y-, illetve z-tengellyel párhuzamos egyenes tartalmaz Cj színű pontot; ezek szerint a gráfban a Cj foka pontosan |Sjx|+|Sjy|+|Sjz|. Kombinálva a Lemmát a számtani és mértani közepek közötti egyenlőtlenséggel,

d(Cj)=|Sjx|+|Sjy|+|Sjz|\ge3(|Sjx|.|Sjy|.|Sjz|)1/3\ge3|Sj|2/3=3n4/3.

A fokszámok összege a gráf mindkét osztályában megegyezik az élek számával, ezért


\max\Big(d(L_1),d(L_2),\dots,d(L_{3n^2})\Big) 
\ge \frac1{3n^2}\sum_{i=1}^{3n^2} d(L_i)
= \frac1{3n^2}\sum_{j=1}^n d(C_j)
\ge \frac1{3n^2} \sum_{j=1}^n 3n^{4/3}
= n^{1/3}.

Van tehát legalább egy olyan Li egyenes, aminek a foka a gráfban legalább \root3\of{n}, ami azt jelenti, hogy ez az egyenes legalább \root3\of{n} különböző színű pontot tartalamaz.


Statisztika:

5 dolgozat érkezett.
5 pontot kapott:Ágoston Tamás, Janzer Olivér, Omer Cerrahoglu, Strenner Péter.
0 pontot kapott:1 versenyző.

A KöMaL 2012. februári matematika feladatai