A finite basis theorem for packing boxes with bricks
FA Dick de Bruijn, DA David Klarner · TU/e Research Portal · 1975
Consider a catalogue S which lists one to infinitely many shapes of rectangular bricks with positive integer dimensions. Using as many bricks of each shape as needed, the bricks listed in S may be used to completely fill certain rectangular boxes. We assume the shapes to be oriented, i.e. we are not allowed to turn bricks around when trying to fill a box. Thus, a new catalogue reS) may be formed which lists the (infinitely many) rectangular boxes which may be completely filled with bricks having their shape listed in S. Some of the bricks listed in S may be shapes of boxes which can be filledup completely with smaller bricks listed in S; in other words, there may be elements SE S such that SE r(S\{s}). The bricks which may be formed with bricks in S smaller than themselves are composites. Bricks in S which are not composites are primes in S. If Br = Br(S) is the set of primes in S, then B; is non-empty and every box which can be formed with elements of S can be formed with elements of the subset Br of S; in other words, r(Br) = reS) (see lemma 4). The subject ofthis note is the remarkable fact that the set of primes Br(S) is finite for every set S. The brief history of this problem is as follows: Results involving the tiling of rectangles and three-dimensional boxes with identical polyominoes and polycubes are discussed in ref. 3. One sort of result presented there is typified by the following example. The L-tetromino and two of the smallest rectangles it tiles are shown in fig. I. An aX b rectangle can be tiled with copies of the L-tetromino