Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?
I want the old design back!!! :-)

Problem A. 555. (February 2012)

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

Deadline expired on March 12, 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:

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