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 n² 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 S_x, S_y, S_z respectively denote the perpendicular projection of S onto the planes xy-, zx- and xy then

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

A proof of the Lemma can be found here.

Let the colors be C₁,...,C_n, and for every i=1,...,n let S_i be the points of color C_i. Since each color is used n² times, we have |S_i|=n². There are 3n² lines which are parallel to the axes and intersect the cube; denote them by L₁,L₂,...,L_3n².

Construct a bipartite graph in the following way. Let the two vertex classes be {L₁,L₂,...,L_3n²} and {C₁,C₂,...,C_n}. Connect L_i with C_j if the line L_i passes through at least one point of color C_j.

The perpendicular projections of the set S_j 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 C_j. Hence, the degree of C_j in the graph is exactly |S_jx|+|S_jy|+|S_jz|. Combining this with the AM-GM inequality,

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.

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 L_i 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

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

Already signed up?
New to KöMaL?