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 3space 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 3n^{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 zaxes, 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 AMGM inequality,
d(C_{j})=S_{jx}+S_{jy}+S_{jz}3(S_{jx}^{.}S_{jy}^{.}S_{jz})^{1/3}3S_{j}^{2/3}=3n^{4/3}.
Doublecounting 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:
