Let $n\geq 4$ be an even integer. A cube with edge of length $n$ (briefly, an $n$-cube) is constructed from $n^3$ unit cubes (briefly, $u$-cubes). There are $\frac{n^3}{4}$ different colors given and exactly $4$ $u$-cubes are colored in each of these given colors.

Prove that one can choose $n$ $u$-cubes of different colors, no two of which are in the same level (a level is a set of $n^2$ $u$-cubes whose centers lie in a plane parallel to one of the faces of the $n$ cube).

I am kind of clueless about how to approach the problem... Can you guys give me some hint ?

I am having some difficulties in particular in the understanding of the part where it is said that there are $\frac{n^3}{4}$ different colors with which $4$ $u$-cubes have been colored. Does that mean that I can have one face of a cube with more that one color ?

Bear with me if this question is just too stupid to be asked...

  • $\begingroup$ I edited but when you say "not less than $4$", I considered it meant $n\geq 4$. Is it what you meant or did you mean $n>4$. $\endgroup$ – MoebiusCorzer Nov 23 '15 at 17:02
  • $\begingroup$ There are $n^3$ u-cubes and each given one color. Every color is used exactly 4 times. Hope that makes the question clear. $\endgroup$ – Aravind Nov 23 '15 at 17:04
  • $\begingroup$ @MoebiusCorzer yes,I was meaning $ n \ge 4 $. $\endgroup$ – Mr. Y Nov 23 '15 at 17:05

If $n=6$ there are $6^3=216$ small cubes. We are told that there are four each of $\frac {216}4=54$ colors stacked together to form a $6 \times 6 \times 6$ cube. Each small cube can be labeled with four parameters: its color and its coordinate in each of the three axes. We are now asked to show that no matter how they are stacked into the large cube that you can select six small cubes that are all of different colors and have all the coordinates are pairwise distinct. For example, if the cubes on a body diagonal were of different colors, they would satisfy the requirement. Similarly, if the cubes at $(1,2,3), (2,3,4), (6,6,6), (3,4,5), (5,5,1) \text{ and } (4,1,2)$ were of different colors they would be a solution. The pairwise distinct coordinates is another way of saying they are all in different layers in all three axes.

There are $(n!)^2$ sets of $n$ cubes with acceptable coordinates. To make a set, you must have one cube with each value of each coordinate. You can put the first coordinates in order and have the other two coordinates any permutation. Now consider how many of these sets can be blocked by a given pair of matching color cubes. The pair has two values of each coordinate. You can put the remaining first coordinates in order, then permute the second and third coordinates in $(n-2)!$ ways each, so the pair can rule out $(n-2)!^2$ sets. Each four cubes of a given color can produce six pairs, so there are $6\frac{n^3}4$ pairs. The number of sets that can be ruled out is then $\frac 32n^3(n-2)!^2$ As for $n\ge 4$ this is less than $(n!)^2$ there must be some that are not ruled out.

  • $\begingroup$ I am not able to understand your solution,can you simplify it ? $\endgroup$ – Mr. Y Nov 23 '15 at 20:20
  • $\begingroup$ Forgive me but ,while the rest is fine, the first part gives me some trouble ..The first cube can have any coordinates so I can choose it in $n^3$ ways,now the second cube can be chosen in $n^3-(2n^2-n)$ since I can remove the two layers the first cube identify, and for the next choices i can remove always $2n^2-n$ layers. How is this equivalent to $(n!)^2$ ? $\endgroup$ – Mr. Y Nov 24 '15 at 10:26
  • $\begingroup$ There are three layers you must remove, so the second cube can be chosen in $(n-1)^3$ ways. The third can be chosen in $(n-2)^3$ and so on. These multiply to $n!^3$, but we have counted each set of cubes $n!$ times as you can choose the same set in any order. I was forcing us to choose them in order of one layer, which avoids the overcounting. It leads to the same number, as it must. $\endgroup$ – Ross Millikan Nov 24 '15 at 14:39
  • $\begingroup$ What is the third layer you are removing ? $\endgroup$ – Mr. Y Nov 24 '15 at 15:11
  • $\begingroup$ All three layers through the first cube. So if the first cube chosen were $(2,3,4)$ you would remove $(2,x,y), (x,3,y), (x,y,4)$ $\endgroup$ – Ross Millikan Nov 24 '15 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.