# 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*^{2} times. Show that there is a line, parallel to an edge of the grid, which passes through at least 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*|^{2}|*S*_{x}|^{.}|*S*_{y}|^{.}|*S*_{z}|.

A proof of the Lemma can be found here.

Let the colors be *C*_{1},...,*C*_{n}, and for every *i*=1,...,*n *let *S*_{i} be the points of color *C*_{i}. Since each color is used *n*^{2} times, we have |*S*_{i}|=*n*^{2}. There are 3*n*^{2} lines which are parallel to the axes and intersect the cube; denote them by *L*_{1},*L*_{2},...,*L*_{3n2}.

Construct a bipartite graph in the following way. Let the two vertex classes be {*L*_{1},*L*_{2},...,*L*_{3n2}} and {*C*_{1},*C*_{2},...,*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}|3(|*S*_{jx}|^{.}|*S*_{jy}|^{.}|*S*_{jz}|)^{1/3}3|*S*_{j}|^{2/3}=3*n*^{4/3}.

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

Therefore, there is a line *L*_{i} with degree at least , so this line passes through at least 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