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!

Kifordítható

tetraéder

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

A. 555. The points of an n×n×n rectangular grid are colored with n colors in such a way that each color is used precisely n2 times. Show that there is a line, parallel to an edge of the grid, which passes through at least \root3\of{n} points with distinct colors.

(5 points)

Deadline expired on 12 March 2012.


Solution. We will use the statement of the 5th problem of the IMO in 1992:

Lemma. If S is a finite set in the 3-space and Sx, Sy, Sz respectively denote the perpendicular projection of S onto the planes xy-, zx- and xy then

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

A proof of the Lemma can be found here.

Let the colors be C1,...,Cn, and for every i=1,...,n let Si be the points of color Ci. Since each color is used n2 times, we have |Si|=n2. There are 3n2 lines which are parallel to the axes and intersect the cube; denote them by L1,L2,...,L3n2.

Construct a bipartite graph in the following way. Let the two vertex classes be {L1,L2,...,L3n2} and {C1,C2,...,Cn}. Connect Li with Cj if the line Li passes through at least one point of color Cj.

The perpendicular projections of the set Sj onto the planes yz, zx, xy contain the same number of elements as the number of lines, parallel to the x, y- and z-axes, respectively, which contain at least one point of color Cj. Hence, the degree of Cj in the graph is exactly |Sjx|+|Sjy|+|Sjz|. Combining this with the AM-GM inequality,

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

Double-counting the number of edges of the graph, we get


\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}.

Therefore, there is a line Li with degree at least \root3\of{n}, so this line passes through at least \root3\of{n} points with distinct colors.


Statistics on problem A. 555.
5 students sent a solution.
5 points:Ágoston Tamás, Janzer Olivér, Omer Cerrahoglu, Strenner Péter.
0 point:1 student.


  • Problems in Mathematics of KöMaL, February 2012

  • 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