%Article: - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
%Author:  Nicholas G. de~Bruijn,
%Title:   Filling boxes with bricks,
\hoffset=-5mm
\voffset=-5mm
\hsize=17cm
\vsize=25cm
\parskip=2pt
\font\sc=cmcsc10

\centerline{{\bf Filling boxes with bricks}}
\centerline{{\sc Nicholas G. de~Bruijn} \footnote{\dag}%
{Eindhoven, The Netherlands}}
\centerline{American Mathematical Monthly, 76 (Jan. 1969) 37--40}

Brickwork is usually made of bricks whose measaments are 
$1 \times 2 \times 4$, so that they can fit together in many positions.
It is very remarkable, however, that this flexibility does not help at
all when it is required to fill a given rectangular box entirely with
such bricks. It can be proved (and a more general result will be proved
in this note) that if the box cannot be filled trivially (i.e., with all
bricks in parallel position), then it cannot be filled at all. 
For instance, if the box is $10 \times 10 \times 10$, it cannot be filled
trivially with $1 \times 2 \times 4$ bricks, since 4 does not divide 10.
By the theorem just mentioned, it cannot be filled at all without breaking
the bricks, although the number of bricks that is needed is an integer
(viz., 125).

It has to be remarked that the situation is different with bricks with
measurements $1 \times 2 \times 3$. For, the flat box $1 \times 5 \times 6$
can be filled (see figure), 
%%%%%%%%%%%%%%%
% 1 1 1 2 2 2 %
% 1 1 1 2 2 2 %
% 3 3 4 4 5 5 %
% 3 3 4 4 5 5 %
% 3 3 4 4 5 5 %
%%%%%%%%%%%%%%%
but it cannot be filled trivially.

In this note we shall determine all bricks which share the 
above-mentioned property of the $1 \times 2 \times 4$. The
problem will be solved for an arbitrary number of dimensions,
and the answer will be quite simple.

The decisive idea of this paper is a generalization of a trick
occuring in the solution of the following well-known problem.
Cut out two diagonally opposite squares of an $8 \times 8$
checker-board, and show that it is impossible to cover the 
remaining 62 squares by 31 dominoes of size $1 \times 2$.
The impossibility is shown as follows. Each domino will cover
both a black and a white square. On the other hand, the region
to be covered does not have the same number of squares of each
colour since the two removed squares had the same colour.

Measurements of $n$-dimensional bricks and boxes will be expressed
by integers. We consider bricks $a_1 \times \cdots \times a_n$ and 
a box $A_1 \times \cdots \times A_n$.
The box $A_1 \times \cdots \times A_n$ is called a {\it multiple}
of th brick $a_1 \times \cdots \times a_n$, if there are integers
$q_1, \cdots, q_n$ such that the numbers $q_1 a_1, \cdots, q_n a_n$
form a rearrangement of $A_1 \times \cdots \times A_n$.
(Example: $10 \times 16 \times 17$ is a multiple of $1 \times 2 \times 4$.)
It is easily seen that the box can be filled trivially if and only if
it is a multiple of the brick.

The brick $a_1 \times \cdots \times a_n$ is called {\it harmonic} if
the numbers $a_1, \cdots, a_n$ can be rearranged into $a'_1, \cdots, a'_n$
with $a'_1 | a'_2, a'_2 | a'_3, \cdots, a'_{n-1} | a'_n$.
(Example: the brick $2 \times 1 \times 6 \times 6$ is harmonic.)

The purpose of this note is to show that the harmonic bricks share the
above-mentioned property of the $1 \times 2 \times 4$ bricks (Theorem 2),
and that the nonharmonic bricks do not have this property (Theorem 3).
In other words, if the brick is not harmonic, then there are boxes which 
canbe filled, but cannot be filled trivially. If the brick is harmonic,
then every box that can be filled, can already be filled trivially.

We first prove 
\smallskip

{\sc Theorem 1.} 
If the box $A_1 \times \cdots \times A_n$ can be filled with bricks
$a_1 \times \cdots \times a_n$, then at least one of the $A_i$ is a
multiple of $a_1$, at least one of the $A_i$ is a multiple of $a_2$,
etc. (this does not necessarily imply that the box is a multiple of
the brick; cf. the case of the box $1 \times 5 \times 6$
and the brick $1 \times 2 \times 3$).
\smallskip

{\it Proof.} 
It suffices to consider $a_1$. 
As any brick $a_1 \times \cdots \times a_n$ can be subdivided into
brick $a_1 \times 1 \times \cdots \times 1$, we may start from the 
assumption that the box is filled, in some way or another, with such 
bricks $a_1 \times 1 \times \cdots \times 1$. We divide each one of
them into $a_1$ cubes $1 \times \cdots \times 1$. The box now contains
$A_1 \cdots A_n$ cubes. We give these cubes coordinates 
$(k_1, \cdots, k_n)$ $(1 \leq k_1 \leq A_1, \cdots, 1 \leq k_n \leq A_n)$.
We consider the sum
$$
 S(A)  =  \sum_{k=1}^{A} e^{2 \pi i k / a_1} \; ,
$$
and the multiple sum
$$
 \sum_{k_1=1}^{A_1} 
   \cdots 
 \sum_{k_n=1}^{A_n} 
    e^{2 \pi i (k_1 + \cdots + k_n) / a_1} 
=
 S(A_1) \cdots S(A_1) \; .  
$$

Each term in this multiple sum corresponds to a cube in the box.
These terms can be grouped together in blocks of $a_1$ terms each,
combining terms corresponding to cubes belonging to one and the
same brick. In such a group of terms, one of the indices runs
through a set of $a_1$ consecutive integers, and the other indices
remain constant. It follows that the contribution of such a group
is zero, irrespective of the orientation of the brick.

We infer that the multiple sum over all cubes vanishes and
therefore one of the $S(A_j)$ equals zero. Since
$$
 S(A_j)  =  x + x^2 + \cdots + x^{A_j} 
         =  x ( x^{A_j} - 1 ) / ( x - 1 )
$$
with $x = e^{2 \pi i / a_1}$, we have $e^{2 \pi i A_j / a_1} = 1$.
It follows that $A_j$ is a multiple of $a_1$.
\smallskip

{\sc Theorem 2.} 
If a box is filled with harmonic bricks $a_1 \times \cdots \times a_n$,
then the box is a multiple of the brick.
\smallskip

{\it Proof.} 
We use induction with respect to $n$. If $n = 1$ we have a triviality.
Assuming that the assertion holds in the $n-1$-dimensional case, we
shall tackle the case of $n$ dimensions.

Without loss of generality we may assume that
$a_1 | a_2, a_2 | a_3, \cdots, a_{n-1} | a_n$.
If the box is $A_1 \times \cdots \times A_n$, we have, by the previous 
theorem, that one of the $A_i$ is a multiple of $a_n$. Assume that $A_n$
is a multiple of $a_n$.

We consider an $(n-1)$-dimensional face $A_1 \times \cdots \times A_{n-1}$.
This is entirely filled with $(n-1)$-dimensional bricks of various sizes, viz.,
$a_2 \times \cdots \times a_n$, or $a_1 \times a_3 \times \cdots \times a_n$,
$\cdots$, or $a_1 \times a_2 \times \cdots \times a_{n-1}$. 
Each one of these can be subdivided into $(n-1)$-dimensional bricks 
$a_1 \times \cdots \times a_{n-1}$, by virtue of the divisibility property
of $a_1, \cdots, a_n$. The brick $a_1 \times \cdots \times a_{n-1}$ being
harmonic, we observe that $A_1 \times \cdots \times A_{n-1}$ is a multiple of 
$a_1 \times \cdots \times a_{n-1}$ by virtue of the induction hypothesis.
Since we know that $a_n | A_n$, we infer that $A_1 \times \cdots \times A_n$
is a multiple of $a_1 \times \cdots \times a_n$.
\smallskip

{\sc Theorem 3.} 
If the brick $a_1 \times \cdots \times a_n$ is not harmonic, then there
is a box which can be filled without being a multiple of the brick.
\smallskip

{\it Proof.} 
We may assume that $n > 1$, $a_1 \leq a_2 \leq \cdots \leq a_n$, and that
$k$ is the largest integer for which $a_{k-1}$ does not divide $a_k$ 
(so $2 \leq k \leq n$).

A box $(a+b) \times ab$ can be filled with bricks $a \times b$
(see figure, where $a=2$, $b=3$). Therefore the box
$$
  a_1 \times \cdots \times a_{k-2} \times
  (a_{k-1} + a_k) \times a_{k-1} a_k \times
  a_{k+1} \times \cdots \times a_n
$$
can be filled with bricks $a_1 \times \cdots \times a_n$. 
We show that this box is not a multiple of the brick. 
Let $j$ be the smallest integer with $a_j = a_{k-1}$. 
Then no one of the numbers $a_1, \cdots, a_{j-1}, a_{k-1} + a_k$ is 
divisible by any of the numbers $a_j, \cdots, a_{k-1}, a_k, \cdots, a_n$. 
(Note that $a_j = \cdots = a_{k-1}$, that $a_{k-1} + a_k$ is not 
divisible by $a_{k-1}$ or $a_k$, nor by any multiple of $a_k$. And
$a_{k+1}, \cdots, a_n$ are multiples of $a_k$, according to the way
$k$ was chosen.)

If the box $A_1 \times \cdots \times A_n$ is a multiple of the brick
$a_1 \times \cdots \times a_n$, there can be at most $j-1$ $i$'s such
that $A_i$ is no multiple of any of the numbers $a_j, \cdots, a_n$.
Therefore, the box constructed above is not a multiple of the brick.
This completes the proof. 

The material of Theorems 1 and 2 was presented in the form of problems
in Hungarian in {\it Mathematikai Lapok}
12 (1961) pp. 110--112, problem 109 and 13 (1962) pp. 314--317, problem 119.
Problem 109, dealing with bricks $1 \times 2 \times 4$, was solved by
G. Haj\'os, G. Katona, D. Szasz, I. Thiry, and the proposer.
Problem 119 dealt with the $n$-dimensional case, and was solved by
G. Haj\'os, G. Katona, D. Szasz, and the proposer.

The question of the bricks $1 \times 2 \times 4$ arose from a remark
by the proposer's son F. W. de~Bruijn who discovered, at the age of 7,
that he was unable to fill his $6 \times 6 \times 6$ box by 
bricks $1 \times 2 \times 4$.

% - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
\bye