Let $K$ be a cube with edge $n$, where $n>2$ is an even integer. Cube $K$ is divided into $n^3$ unit cubes. We call any set of $n^2$ unit cubes lying on the same horizontal or vertical level a layer. We dispose of $\frac{n^3}4$ colors, in each of which we paint exactly $4$ unit cubes. Prove that we can always select $n$ unit cubes of distinct colors, no two of which lie on the same layer.
Problem
Source: Bulgaria 1991 P2
Tags: geometry, 3D geometry, combinatorics, combinatorial geometry, Bulgaria
16.06.2021 21:39
I’ll present the official solution. Let $ S$ be the family of all configurations of $ n$ cubes (cells), no two of them lying on the same layer. Let's count how many elements $ S$ has. We can choose the firs cell $ c_1$ in $ n^3$ ways. After removing all layers $ c_1$ takes part in there remain $ (n-1)^3$ cubes. So the next cell $ c_2$ can be chosen in $ (n-1)^3$ ways and so on. This way, every configuration in $ S$ is counted $ n!$ times, hence $$ \displaystyle |S|=\frac{n^3\cdot (n-1)^3\cdots 2^3\cdot 1^3}{n!}=(n!)^2.$$Denote by $ B$ the family of "bad" configurations of $ n$ cells, no two of them in the same layer, in which there exists two identically colored cells. We can choose two cells of the same color by first choosing the color and then all possible pairs among the four cells colored in this color. Thus, we can choose two identically colored cells in $ \displaystyle \frac{n^3}{4}\cdot \binom{4}{2}=3\frac{n^3}{2}$ ways. Therefore $$ \displaystyle |B|\le 3\frac{n^3}{2} \big((n-2)!\big)^2 .$$Note that this inequality may be strict. For example it may happen a bad configuration consists of two pairs of identically colored cells. Then we count this configuration twice. Further, it's enough to show $ |B|<|S|$ because then $ S\setminus B$ could not be empty. Thus, it's enough to prove that for $ n\ge 4$ it holds $$ \displaystyle 3\frac{n^3}{2} \big((n-2)!\big)^2 < (n!)^2.$$It is equivalent to $ \displaystyle 3\frac{n}{2} < (n-1)^2 $ and it can be easily checked that it holds for $ n\ge 4.$ Remark. Some more comments and a generalization of this problem can be found in my blog.