KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

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.

Our web pages are supported by:   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