Filling boxes with bricks Nicholas G. de Bruijn † American Mathematical Monthly, 76 (Jan. 1969) 37–40 Brickwork is usually made of bricks whose measaments are 1 × 2 × 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 × 10 × 10, it cannot be filled trivially with 1 × 2 × 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 × 2 × 3. For, the flat box 1 × 5 × 6 can be filled (see figure), but it cannot be filled trivially.

In this note we shall determine all bricks which share the above-mentioned property of the 1 × 2 × 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 × 8 checker-board, and show that it is impossible to cover the remaining 62 squares by 31 dominoes of size 1×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} × ⋯ × a_{n} and a box A_{1} × ⋯ × A_{n}. The box A_{1} × ⋯ × A_{n} is called a multiple of th brick a_{1} × ⋯ × a_{n}, if there are integers q_{1}, ⋯, q_{n} such that the numbers q_{1}a_{1}, ⋯, q_{n}a_{n} form a rearrangement of A_{1} × ⋯ × A_{n}. (Example: 10 × 16 × 17 is a multiple of 1 × 2 × 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} × ⋯ × a_{n} is called harmonic if the numbers a_{1}, ⋯, a_{n} can be rearranged into a′_{1}, ⋯, a′_{n} with a′_{1}|a′_{2}, a′_{2}|a′_{3}, ⋯, a′_{n−1}|a′_{n}. (Example: the brick 2 × 1 × 6 × 6 is harmonic.)

The purpose of this note is to show that the harmonic bricks share the above-mentioned property of the 1 × 2 × 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

Theorem 1. If the box A_{1} × ⋯ × A_{n} can be filled with bricks a_{1} × ⋯ × 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 × 5 × 6 and the brick 1 × 2 × 3).

Proof. It suffices to consider a_{1}. As any brick a_{1} × ⋯ × a_{n} can be subdivided into brick a_{1} × 1 × ⋯ × 1, we may start from the assumption that the box is filled, in some way or another, with such bricks a_{1} × 1 × ⋯ × 1. We divide each one of them into a_{1} cubes 1 × ⋯ × 1. The box now contains A_{1} ⋯ A_{n} cubes. We give these cubes coordinates (k_{1}, ⋯, k_{n}) (1 ≤ k_{1} ≤ A_{1}, ⋯, 1 ≤ k_{n} ≤ A_{n}). We consider the sum

S(A) = ∑_{k=1}^{A} e^{2πik/a_{1}} ,

and the multiple sum

∑_{k_{1}=1}^{A_{1}} ⋯ ∑_{k_{n}=1}^{A_{n}} e^{2πi(k_{1}+···+k_{n})/a_{1}} = S(A_{1}) ⋯ 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} + ⋯ + x^{A_{j}} = x(x^{A_{j}} − 1)/(x − 1)

with x = e^{2πi/a_{1}}, we have e^{2πiA_{j}/a_{1}} = 1. It follows that A_{j} is a multiple of a_{1}.

† Eindhoven, The Netherlands Theorem 2. If a box is filled with harmonic bricks a_{1} × ⋯ × a_{n}, then the box is a multiple of the brick.

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}, ⋯, a_{n−1}|a_{n}. If the box is A_{1} × ⋯ × 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} × ⋯ × A_{n−1}. This is entirely filled with (n − 1)-dimensional bricks of various sizes, viz., a_{2} × ⋯ × a_{n}, or a_{1} × a_{3} × ⋯ × a_{n}, ⋯, or a_{1} × a_{2} × ⋯ × a_{n−1}. Each one of these can be subdivided into (n − 1)-dimensional bricks a_{1} × ⋯ × a_{n−1}, by virtue of the divisibility property of a_{1}, ⋯, a_{n}. The brick a_{1} × ⋯ × a_{n−1} being harmonic, we observe that A_{1} × ⋯ × A_{n−1} is a multiple of a_{1} × ⋯ × a_{n−1} by virtue of the induction hypothesis. Since we know that a_{n}|A_{n}, we infer that A_{1} × ⋯ × A_{n} is a multiple of a_{1} × ⋯ × a_{n}.

Theorem 3. If the brick a_{1} × ⋯ × a_{n} is not harmonic, then there is a box which can be filled without being a multiple of the brick.

Proof. We may assume that n > 1, a_{1} ≤ a_{2} ≤ ⋯ ≤ a_{n}, and that k is the largest integer for which a_{k−1} does not divide a_{k} (so 2 ≤ k ≤ n).

A box (a + b) × ab can be filled with bricks a × b (see figure, where a = 2, b = 3). Therefore the box

a_{1} × ⋯ × a_{k−2} × (a_{k−1} + a_{k}) × a_{k−1}a_{k} × a_{k+1} × ⋯ × a_{n}

can be filled with bricks a_{1} ×⋯×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}, ⋯, a_{j−1}, a_{k−1} + a_{k} is divisible by any of the numbers a_{j}, ⋯, a_{k−1}, a_{k}, ⋯, a_{n}. (Note that a_{j} = ⋯ = 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}, ⋯, a_{n} are multiples of a_{k}, according to the way k was chosen.)

If the box A_{1} × ⋯ × A_{n} is a multiple of the brick a_{1} × ⋯ × 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}, ⋯, 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 Mathematikai Lapok 12 (1961) pp. 110–112, problem 109 and 13 (1962) pp. 314–317, problem 119. Problem 109, dealing with bricks 1 × 2 × 4, was solved by G. Hajós, G. Katona, D. Szasz, I. Thiry, and the proposer. Problem 119 dealt with the n-dimensional case, and was solved by G. Hajós, G. Katona, D. Szasz, and the proposer.

The question of the bricks 1 × 2 × 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 × 6 × 6 box by bricks 1 × 2 × 4.