TAOCP 7.2.2.1 Exercise 347
Let $\omega$ be a primitive $k$th root of unity, so $\omega^k = 1$ and $1 + \omega + \cdots + \omega^{k-1} = 0$.
Section 7.2.2.1: Dancing Links
Exercise 347. ▶ [M21] [M21] (N. G. de Bruijn, 1961.) Prove that an $l \times m \times n$ box can be completely filled with $1 \times 1 \times k$ bricks only if $k$ is a divisor of $l$, $m$, or $n$. (Consequently, it can be completely filled with $a \times b \times c$ bricks only if $a$, $b$, and $c$ all satisfy this condition.)
Verified: no
Solve time: 1m46s
Solution
Let $\omega$ be a primitive $k$th root of unity, so $\omega^k = 1$ and $1 + \omega + \cdots + \omega^{k-1} = 0$.
For each unit cube with integer coordinates $(x,y,z)$ in the box $0 \le x < l$, $0 \le y < m$, $0 \le z < n$, assign the complex weight
$w(x,y,z) = \omega^{x+y+z}.$
Consider a single $1 \times 1 \times k$ brick. Such a brick occupies exactly $k$ consecutive unit cubes along one coordinate axis, with the other two coordinates fixed.
If the brick is aligned along the $x$-axis, its cubes have coordinates $(x_0 + t, y_0, z_0)$ for $t = 0,1,\dots,k-1$. The total weight of this brick is
= \omega^{x_0+y_0+z_0} \sum_{t=0}^{k-1} \omega^t = 0.$$ If the brick is aligned along the $y$-axis, its cubes are $(x_0, y_0 + t, z_0)$, and its total weight is $$\sum_{t=0}^{k-1} \omega^{x_0+(y_0+t)+z_0} = \omega^{x_0+y_0+z_0} \sum_{t=0}^{k-1} \omega^t = 0.$$ The same computation applies to bricks aligned along the $z$-axis. Every brick contributes total weight $0$. If the box is tiled completely, the sum of all cube weights equals the sum over all bricks, hence equals $0$. On the other hand, the total weight of the entire box is $$\sum_{x=0}^{l-1} \sum_{y=0}^{m-1} \sum_{z=0}^{n-1} \omega^{x+y+z} = \left(\sum_{x=0}^{l-1} \omega^x\right)\left(\sum_{y=0}^{m-1} \omega^y\right)\left(\sum_{z=0}^{n-1} \omega^z\right).$$ Each factor satisfies $$\sum_{t=0}^{L-1} \omega^t = \begin{cases} 0, & k \nmid L,\ L, & k \mid L. \end{cases}$$ Hence the product is zero only if at least one of $l$, $m$, $n$ is divisible by $k$. Since the tiling forces the total weight to be zero, at least one factor must vanish, and therefore $k$ divides $l$ or $m$ or $n$. This completes the proof. ∎