58. National mathematical olympiad Final round

We shall prove that the solutions are the triples $(a,b,c)$ such that $a$ divides $b$ and $b$ divides $c$. We denote by $((x_0,y_0,z_0),p,q,r)$ the parallelepiped with a low right vertex $(x_0,y_0,z_0)$ and dimensions $p,q$ and $r$, at axes $Ox,Oy$ and $Oz$, respectively.

Let us assume that $b$ is not divisible by $a$, i.e. $b=ma+n$ for some $m,n\in \mathbb{N}$, $0<n<a$. If $(p,q,r)$ is a permutation of $(a,b,c)$, then it follows from the condition for the parallelepipeds $((0,0,0),p,q,r)$ and $((0,0,1),p,q,r)$ that the parallelepipeds $((0,0,0),p,q,1)$ and $((0,0,r),p,q,1)$ are filled with cubes of the same colors. This implies that the parallelepipeds $((0,0,0),c,a,1)$ and $((0,0,b),c,a,1)$ are also filled with cubes of the same colors and the same is true for the parallelepipeds $((0,0,0),c,b,1)$ and $((0,0,ma),c,b,1)$. Since $((0,0,0),c,b,1)$ contains $((0,0,0),c,a,1)$ and $((0,0,ma),c,b,a)$ contains $((0,0,ma),c,b,1)$ and $((0,0,b),c,a,1)$, every color in $((0,0,0),c,a,1)$ appears at least two times in $((0,0,ma),c,b,a)$. This contradiction completes the proof that $a$ divides $b$. We analogously see that $b$ divides $c$.

Now let $a|b$ and $b|c$, as $b=p_{1}a,c=p_{2}b=p_1{p}_{2}a$, where $p_1,p_2\in \mathbb{N}$. For every two positive integers $m$ and $n$ we denote by $R(m,n)$ the remainder of $m$ modulo $n$. The coordinates of a cube will be the coordinates of its low right vertex.

We determine the color the cube $(x,y,z)$ in remainders as follows: $$(R(x,a);R(y,a);R(z,a);R(\lfloor \frac{x}{a}\rfloor +\lfloor \frac{y}{a}\rfloor ,p_1);R(\lfloor \frac{y}{a}\rfloor +\lfloor \frac{z}{a}\rfloor ,p_1);R(\lfloor \frac{x}{b}\rfloor +\lfloor \frac{y}{b}\rfloor +\lfloor \frac{z}{b}\rfloor ,p_2)).$$ The counting of all possible remainders in the six coordinates shows that the number of the colors used is $a^3{p}_1{p}_1{p}_2=abc$.

Let us assume that two distinct cubes $(x_1,y_1,z_1)$ and $(x_2,y_2,z_2)$ lie in a parallelepiped of dimensions $a\times b\times c$. Then we have $|x_1-x_2|\le \alpha$, $|y_1-y_2|\le \beta$ and $|z_1-z_2|\le \gamma$, where $(\alpha ,\beta ,\gamma )$ is a permutation of $(a,b,c)$. Since $|x_1-x_2|$, $|y_1-y_2|$ and $|z_1-z_2|$ are divisible by $a$, one of these numbers equals $0$. Let us have $x_1=x_2$. Then the fourth and fifth coordinates of that color show that $|y_1-y_2|$ and $|z_1-z_2|$ are divisible by $b$ and therefore one of these two numbers equals $0$. If, for example, $y_1=y_2$, then the last coordinate shows that $|z_1-z_2|$ is divisible by $c$, i.e. $z_1=z_2$. We obtained $(x_1,y_1,z_1)\equiv (x_2,y_2,z_2)$, which is a contradiction.