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: yes
Solve time: 1m41s

Solution

Let the cells of the $l \times m \times n$ box have coordinates $(x,y,z)$, where

$0\le x<l,\qquad 0\le y<m,\qquad 0\le z<n.$

Let $\omega$ be a primitive $k$th root of unity. Assign to the cell $(x,y,z)$ the weight

$w(x,y,z)=\omega^{x+y+z}.$

Suppose first that the box is tiled by $1\times1\times k$ bricks. Consider a brick parallel to the $x$-axis, beginning at $(x_0,y,z)$. Its total weight is

$$ \sum_{i=0}^{k-1}\omega^{x_0+i+y+z}

\omega^{x_0+y+z}\sum_{i=0}^{k-1}\omega^i. $$

Since $\omega$ is a primitive $k$th root of unity,

$$ \sum_{i=0}^{k-1}\omega^i=0, $$

so every such brick has weight $0$. The same calculation applies to bricks parallel to the $y$-axis or the $z$-axis. Therefore every possible $1\times1\times k$ brick has total weight $0$.

Hence, if the whole box is tiled, the total weight of the box must also be $0$. The total weight of the 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). $$

For any positive integer $s$,

$$ \sum_{i=0}^{s-1}\omega^i= \frac{1-\omega^s}{1-\omega}. $$

Because $\omega\ne1$, this sum is zero exactly when

$$ \omega^s=1. $$

Since $\omega$ has order $k$, this is equivalent to

$$ k\mid s. $$

Therefore

$$ \sum_{x=0}^{l-1}\omega^x=0 \iff k\mid l, $$

and the analogous statements hold for $m$ and $n$. If $k$ divides none of $l$, $m$, and $n$, then all three factors in the expression for the total weight are nonzero, so the total weight of the box is nonzero. This contradicts the fact that every brick contributes weight $0$.

Consequently, a necessary condition for a complete filling by $1\times1\times k$ bricks is that

$$ k\mid l,\qquad\text{or}\qquad k\mid m,\qquad\text{or}\qquad k\mid n. $$

Now consider a filling by $a\times b\times c$ bricks. To prove the stated consequence for $a$, choose a primitive $a$th root of unity $\omega$ and give the cell $(x,y,z)$ the weight

$$ w(x,y,z)=\omega^{x+y+z}. $$

Every $a\times b\times c$ brick has one side of length $a$. If that side is parallel to the $x$-axis, the contribution of the brick contains the factor

$$ \sum_{i=0}^{a-1}\omega^i=0. $$

If the side of length $a$ is parallel to the $y$-axis or the $z$-axis, the same vanishing factor appears in the corresponding coordinate sum. Thus every $a\times b\times c$ brick has total weight $0$.

The total weight of the box is

$$ \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). $$

This product can vanish only if $a$ divides at least one of $l$, $m$, or $n$. Therefore

$$ a\mid l,\quad\text{or}\quad a\mid m,\quad\text{or}\quad a\mid n. $$

Applying the same argument with primitive $b$th and $c$th roots of unity gives

$$ b\mid l,\quad\text{or}\quad b\mid m,\quad\text{or}\quad b\mid n, $$

and

$$ c\mid l,\quad\text{or}\quad c\mid m,\quad\text{or}\quad c\mid n. $$

Thus every dimension of the brick must satisfy the stated divisibility condition. This completes the proof.

∎

TAOCP 7.2.2.1 Exercise 347

Solution

$$ \sum_{i=0}^{k-1}\omega^{x_0+i+y+z}

$$ \sum_{x=0}^{l-1}\sum_{y=0}^{m-1}\sum_{z=0}^{n-1}\omega^{x+y+z}