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 n²-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 S_x, S_y, illetve S_z jelöli rendre az S pontjainak az xy-, zx-, ill. xy-síkokra vett merőleges vetületeiből álló halmazokat, akkor

|S|² $\le$ |S_x|^.|S_y|^.|S_z|.

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

A felhasznált színek legyenek C₁,...,C_n, és minden i=1,...,n-re legyen S_i a C_i színű pontok halmaza. A feltétel szerint minden színt pontosan n²-szer használunk, tehát |S_i|=n². A rácskockát a tengelyekkel párhuzamosan összesen 3n² egyenes metszi; jelöljük ezeket L₁,L₂,...,L_3n²-tel.

Építsünk páros gráfot a következőképpen. A két csúcsosztály legyen {L₁,L₂,...,L_3n²}, illetve {C₁,C₂,...,C_n}. Az L_i egyenest és a C_j pontot akkor kössük össze éllel, ha az L_i egyenes tartalmaz legalább egy C_j színú pontot.

Az S_j 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 C_j színű pontot; ezek szerint a gráfban a C_j foka pontosan |S_jx|+|S_jy|+|S_jz|. Kombinálva a Lemmát a számtani és mértani közepek közötti egyenlőtlenséggel,

d(C_j)=|S_jx|+|S_jy|+|S_jz| $\ge$ 3(|S_jx|^.|S_jy|^.|S_jz|)^1/3 $\ge$ 3|S_j|^2/3=3n^4/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 L_i 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

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

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