BMO 2022 shortlist

Suppose that for some $k>1$ and some placed cubelet there is a valid filling. In each unit cubelet (of the original cube) with coordinates $(x,y,z)$ where $0\le x,y,z\le 2020$, we assign the complex number ${\omega }^{x+y+z}$ where $\omega =e^{\frac{2\pi i}{k}}$. We also assign the number ${\omega }^{a+b+c}$ in the additional cubelet in position $(a,b,c)$.

Since $1+\omega +{\omega }^2+\cdots +{\omega }^{k-1}=\frac{{\omega }^k-1}{\omega -1}=0$, then the sum of numbers in any $1\times 1\times k$ cuboid is equal to zero. So the sum of all assigned numbers is equal to $$0=(1+\omega +\cdots +{\omega }^{2020}{)}^3+{\omega }^{a+b+c}.(1)$$ This gives $$1=|-{\omega }^{a+b+c}|=|(1+\omega +\cdots +{\omega }^{2020}{)}^3|={\left|\frac{1-{\omega }^{2021}}{1-\omega }\right|}^3.$$ Thus $|1-\omega |=|1-{\omega }^{2021}|$ which means that $1$ is equidistant from the numbers $\omega$ and ${\omega }^{2021}$. Since $|{\omega }^{2021}|=1$, this happens if and only if ${\omega }^{2021}=\omega$ or ${\omega }^{2021}={\omega }^{-1}$. Then ${\omega }^{2020}=1$ or ${\omega }^{2022}=1$ which gives $k|2020$ or $k|2022$. However $k|2021^3+1$. Since $2021^3+1\equiv 2\mathrm{mod}2020$, if $k|2020$ then $k|2$. So in any case we have $k|2022$. Now (1) gives $${\omega }^{a+b+c}=-(1+\omega +\cdots +{\omega }^{2020}{)}^3=-(-{\omega }^{2021}{)}^3={\omega }^{6063}={\omega }^{-3}.$$ So $a+b+c\equiv -3\mathrm{mod}k$. If we have a valid filling for $k$, then we have a valid filling for every prime factor of $k$. So we may assume that $k$ is prime and therefore $k\in \{2,3,337\}$. Assume without loss of generality that the additional cubelet is at the bottom of the cube, i.e. $c=-1$. Then $a+b\equiv -2\mathrm{mod}k$. By symmetry, if we have a valid filling for $(a,b,-1)$, then we have a valid filling for $(2022-a,b,-1)$. So we must also have $2022-a+b\equiv -2\mathrm{mod}k$ and so $b-a\equiv -2\mathrm{mod}k$. Since also $a+b\equiv -2\mathrm{mod}k$ we get $a\equiv b\equiv -1\mathrm{mod}k$ for $k\ne 2$ and $a\equiv b\mathrm{mod}2$ for $k=2$. We will now show that the above necessary conditions are also sufficient to have a valid filling. We claim first that a square defined by coordinates $(x,y)$ where $0\le x,y\le 2020$, with a removed cell $(a,b)$ satisfying the above restrictions can be covered by $1\times k$ rectangles. This is because such a square can be covered by four rectangles of sizes $(a+1)\times b$, $(2020-a)\times (b+1)$, $(2021-a)\times (2020-b)$ and $a\times (2021-b)$, where each of these rectangles can be covered by $1\times k$ rectangles. This follows since $k|a+1,b+1,2021-a,2021-b$ if $a\equiv b\equiv -1\mathrm{mod}k$ and since $2|b,2020-a,2020-b,a$ if $a\equiv b\equiv 0\mathrm{mod}2$. Now we fill the cube with the added cubelet as follows: The lowest $k-1$ "layers" of the original cube of side $2021$ are filled using the previous method together with a $1\times 1\times k$ cuboid covering the holes in these layers and the additional cubelet. The remainder is the $2021\times 2021\times (2022-k)$ cuboid which can be easily filled by $1\times 1\times k$ cuboids because $k|2022-k$. To complete the solution, we need to count the number of ordered pairs $(a,b)$ with $0\le a,b\le 2020$, such that $a\equiv b\mathrm{mod}2$, or $a\equiv b\equiv -1\mathrm{mod}3$ or $a\equiv b\equiv -1\mathrm{mod}337$. There are $1011^2$ choices with $a\equiv b\equiv 0\mathrm{mod}2$ and $1010^2$ choices with $a\equiv b\equiv 1\mathrm{mod}2$. If $a\equiv b\equiv -1\mathrm{mod}3$ but $a\ne b\mathrm{mod}2$ then one of $a,b$ must be congruent to $2\mathrm{mod}6$ and the other to $5\mathrm{mod}6$. There are $2\times 337\times 336$ such choices. Finally, if $a\equiv b\equiv -1\mathrm{mod}337$ but is not yet accounted for, then one of them is equal to $\{336,1010,1684\}$ and the other to $\{673,1347\}$. (Note that in this case the second one is definitely not congruent to $-1\mathrm{mod}3$.) There are $2\times 3\times 2$ such choices. In total we have $2268697$ choices for the pair $(a,b)$. Therefore, because of symmetry, the total number of ways is $6\times 2268697=13612182$.

---

Alternative solution.

Since there are a total of $2021^3+1$ cubelets and each cuboid covers $k$ of them, we must have $k|2021^3+1$. We have $$2021^3=2022\cdot (2021^2-2021+1)=2\cdot 3\cdot 337\cdot 3\cdot 7\cdot 31\cdot 6271$$ as a product of prime factors. If we have a valid filling for $k$, then we have a valid filling for every prime factor of $k$. So we may assume that $k$ is prime and therefore $k\in \{2,3,7,31,337\}$. (The case $k=6271$ is easily seen to be impossible.) We colour the cubelet at position $(x,y,z)$ for $0\le x,y,z\le 2020$ by the colour $x+y+z\mathrm{mod}k$. So every $1\times 1\times k$ cuboid covers 1 cubelet of each colour. If $k=2$ then it is easy to see that we have one more cubelet of the form $0\mathrm{mod}2$ than of the form $1\mathrm{mod}2$. So assuming that the additional cubelet is in position $(a,b,-1)$, we must have $a+b\equiv 0\mathrm{mod}2$ as in Solution 1. If $k=3$ then, since it is each to cover all cubelets with $1\times 1\times k$ cuboids except those of the form $(x,y,z)$ with $0\le x,y,z\le 2$, we see that there is one less cubelet of the form $0\mathrm{mod}3$ than of the form $1,2\mathrm{mod}3$. So assuming that the additional cubelet is in position $(a,b,-1)$, we must have $a+b\equiv -2\mathrm{mod}3$. Exploiting the symmetry as in Solution 1 we get $a\equiv b\equiv -1\mathrm{mod}3$. If $k=7$ then note that (since $7|2016$) it is easy to cover all cubelets with $1\times 1\times k$ cuboids except those of the form $(x,y,z)$ with $0\le x,y,z\le 4$. Note that exactly 19 of these cubicles have the colour $0\mathrm{mod}7$. (3 when $z=0$, 3 when $z=1$, 4 when $z=2$, 5 when $z=3$ and 4 when $z=4$.) These are more than $\frac{5^3+1}{7}=18$ so one of these will remain uncovered. So $k=7$ is impossible. If $k=31$ then note that (since $31|2015$) it is easy to cover all cubelets with $1\times 1\times k$ cuboids except those of the form $(x,y,z)$ with $0\le x,y,z\le 5$. Note that only one of those cubelets has the colour $0\mathrm{mod}31$. So even if the additional cubelet has the same colour it is still less than the $\frac{6^3+1}{31}=7$ which are expected in a proper covering. So $k=31$ is impossible. If $k=337$ then note that the square containing all cells of the form $(x,y)$ with $0\le x\le 2020$ and $0\le y\le 2021$ can be covered with $1\times k$ rectangles and so contains equal number of cells of each colour (thinking of $z=0$). In the column with $y=2021$, the cells have in order the colours $-1,0,1,\dots ,-3\mathrm{mod}k$. So the colour $-2\mathrm{mod}k$ appears one time less in that column and therefore one time more in the square of the form $(x,y)$ with $0\le x,y\le 2020$. In the 'layer' above the extra colour is $-1\mathrm{mod}k$, then $0\mathrm{mod}k$ and so on until $2020-2\equiv -4\mathrm{mod}k$. So in the original cube all colours appear an equal number of times except $-3\mathrm{mod}k$ which appear one time less and must be the colour of the additional cubelet $(a,b,-1)$. Thus $a+b\equiv -2\mathrm{mod}k$. Exploiting the symmetry as in Solution 1 we get $a\equiv b\equiv -1\mathrm{mod}337$. So we get the same necessary conditions as in Solution 1. The sufficiency of these conditions is proved in a similar way as in Solution 1.