%Article: - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
%Author:  J. B. Kelly
%Title:   Polynomials and Polyominoes
\hoffset=-5mm
\voffset=-5mm
\hsize=17cm
\vsize=25cm
\parskip=2pt
\font\sc=cmcsc10

\centerline{{\bf Polynomials and Polyominoes}}
\centerline{{\sc J. B. Kelly} \footnote{\dag}%
{Arizona State University}}
\centerline{American Mathematical Monthly 73 (1966) 464--471}

{\bf 1. The associated polynomial.}
Let $S$ be a finite set of lattice points (i.e. points with integral
coordinates) in $k$-dimensional Euclidean space, $E_k$. There will
be no loss in generality in assuming that $S$ is contained in $E'_k$,
where $E'_k$ is that portion of $E_k$ in which all points have
nonnegative coordinates. With the point $p$ of $S$ having the integral
coordinates $n_1, n_2, \cdots, n_k$, we associate the monomial
$$
 M(p) = x_1^{n_1} x_2^{n_2} \cdots x_k^{n_k} \;.
$$
With $S$ itself we associate the polynomial $P(S) = \sum M(p)$, the
summation being extended over all points of $S$. In particular, with
the lattice points of the rectangluar parallelopiped $R$, which has
one vertex at the origin and lies in $E'_k$, we associate the
polynomial, $P(R)$, where
$$
 P(R) = \prod_{i=1}^{k} {x_i^{l_i} - 1 \over x_i - 1} \;.
 \leqno(1)
$$
Here $(l_1 - 1, l_2 - 1, \cdots, l_i - 1, \cdots, l_k - 1)$ is the point
of $R$ farthest from the origin.

Let $T_1, T_2, \cdots, T_r$ be finite sets of lattice pointes in $E'_k$
and let $P(T_1), P(T_2), \cdots, P(T_r)$ be their associated polynomials.
We say that $S$ is covered by $T_1, T_2, \cdots, T_r$ if every point of
$S$ is covered exactly once by suitable translations of $T_1, T_2, \cdots, T_r$
and if no point not in $S$ is covered by these translations. This means
that there exist polynomials $Q_1, Q_2, \cdots, Q_r$ in $x_1, x_2, \dots, x_k$
with coefficients 0 or 1 such that
$$
 P(S) = \sum_{i=1}^{r} Q_i(x_1, x_2, \cdots, x_k) P(T_i).
 \leqno(2)
$$
(We can assume that $T_1, T_2, \cdots, T_r$ have at least one point on
each coordinate axis. Then no negative exponents can occur in 
$Q_1, Q_2, \cdots, Q_r$.) It follows that $P(S)$ must belong to the 
polynomial ideal generated by $P(T_1), P(T_2), \cdots, P(T_r)$. The
ring of coefficients may be any ring containing a subring isomorphic
to the ring of rational integers; we shall find it convenient to employ
the fields of real and complex numbers. If $(\xi_1, \xi_2, \cdots, \xi_k)$
is a point in the manifold of the ideal $(P(T_1), P(T_2), \cdots, P(T_r))$,
i.e. a point with coordinates in a suitable extension of the ring of
coefficients at which $P(T_1), P(T_2), \cdots, P(T_r)$ all vanish, then
$P(S)$ must vanish there also. This is not, of course, a sufficient
condition that $P(S)$ belong to the ideal.

To every lattice point $p$ in $E_k$ there corresponds a unique
$k$-dimensional unit cube having vertices with integral coordinates,
$p$ being one of them, with no vertex having any coordinate less than
the corresponding coordinate of $p$.
(For example, in the two-dimensional case, we have a square with
horizontal and vertical sides, and with $p$ as its southwest corner.)
Hence to every configuration $S$ of lattice points there corresponds
a solid region, $\overline{S}$, composed of these cubes.
We set $P(\overline{S}) = P(S)$.
Thus any problem involving the covering of such solid regions by other
such regions may be reduced to a problem involving the corresponding
configurations of lattice points. Note that (1) gives the associated
polynomial of a solid rectangular parallelopiped with one vertex at
the origin and sides parallel to the coordinate axes of length
$l_1, l_2, \cdots, l_k$.
 
In the case $k=2$, such a ``solid'' region, when ``rookwise'' connected,
was called a ``polyomino'' by Golomb, in his interesting  paper [1] on
checkerboard recreations. Here we shall use the word, ``polyomino,'' to
mean any such solid region, for any value of $k$. Golomb discusses
problems of covering a full or deleted checkerboard with polyominoes
of prescribed form. His principal tool is a ``coloring'' of the 
checkerboard. As will readily be seen, this corresponds to assigning
certain values to $x_1$ and $x_2$ in our formulation.
\smallskip

{\bf 2. Examples.} 
In this section we shall show how (2) may be used to obtain necessary
conditions for the existence of a solution of various problems
involving coverings by polyominoes. Primarily we shall use the fact
that $P(\overline{S})$ must vanish on the manifold of 
$(P(T_1), P(T_2), \cdots, P(T_r))$. It seems to be more difficult
to take significant advantage of the requirement that the coefficients
of $Q_1, Q_2, \cdots, Q_r$ be 0 or 1.

{\it Example I:} %% (X X) 
We begin with a well-known checkerboard problem from [1] which may 
easily be solved without recourse to our method of associated polynomials.
Can one cover a checkerboard with one pair of opposite corners removed,
with $1 \times 2$ dominoes? If $\overline{S}$ is the deleted checkerboard,
then
$$
 P(\overline{S}) = {x_1^{8} - 1 \over x_1 - 1} \cdot {x_2^{8} - 1 \over x_2 - 1}
                 - 1 - x_1^7 x_2^7 \;.
$$
If $\overline{T}_1$ is the domino in its horizontal position and 
$\overline{T}_2$ is the domino in its vertical position then
$P(\overline{T}_1) = 1 + x_1$ and $P(\overline{T}_2) = 1 + x_2$.
From (2) we have
$$
 {x_1^{8} - 1 \over x_1 - 1} \cdot {x_2^{8} - 1 \over x_2 - 1} - 1 - x_1^7 x_2^7
 = Q_1(x_1,x_2) (1 + x_1) + Q_2(x_1,x_2) (1 + x_2) \;.
$$
Setting $x_1 = -1$, $x_2 = -1$, we arrive at a contradiction, so that the
desired covering is impossible. Notice that with these values of $x_1$
and $x_2$, $x_1^{n_1} x_2^{n_2}$ has one value $(\pm 1)$ on all the black
squares of the checkerboard in the usual coloring, and its negative $(\mp 1)$
on the white squares. This observation relates our solution of the problem
to the more elementary solution which consists simply in remarking that the
proposed covering is impossible because the deleted checkerboard does not
contain equal numbers of black and white squares.

The remaining examples in this section deal with the covering of rectangular
$k$-dimensional parallelopipeds by ``straight'' polyominoes. By a straight
polyomino we shall mean the solid region corresponding to a set of lattice
points in $E_k$ lying on a straight line parallel to one of the coordinate
axes. A straight polyomino is not necessarily connected. A straight
polyomino is symmetric if it is invariant under reflection in its center.

{\it Example II:} %% (X X . X . X X)
Is there some rectangular parallelopiped which can be covered by the 
straight symmetric polyomino formed by taking seven adjacent cubes and
deleting the third and fifth? (In this, and in the subsequent examples,
we agree that the polyominoes may be placed parallel to any axis.) If
the polyomino is parallel to the $x_i$-axis, the associated polynomial
for this position is $1 + x_i + x_i^3 + x_i^5 + x_i^6$. If the problem
has a solution, we see, from (1) and (2), that we must have
$$
 \prod_{i=1}^{k} {x_i^{l_i} - 1 \over x_i - 1} 
 =
 \sum_{i=1}^{k} Q_i(x_1, x_2, \dots, x_k) (1 + x_i + x_i^3 + x_i^5 + x_i^6).
 \leqno(3)
$$
for some choise of the positive integers $l_1, l_2, \cdots, l_k$.

The polynomial $1 + x + x^3 + x^5 + x^6$ has a root, $\lambda$, between
$0$ and $-1$. If we put $x_1 = x_2 = \dots = x_k = \lambda$, we obtain
a contradiction from (3), inasmuch as all roots of $x_i^{l_i} - 1$ lie
on the unit circle. Therefore the problem has no solution. We have made
implicit use here of the theorem that a real function continuous on a
closed interval assumes in that interval all values between its values
at the end-points of the interval. The method of associated polynomials
makes available some of the simpler theorems analysis for the handling
of problems involving lattice point configurations.

{\it Example III:} %% (X X . X X)
Is there a rectangular $k$-dimensional parallelopiped which can be
covered by the straight polyomino formed by taking five consecutive
cubes and deleting the middle one? Proceeding as in example II, we
obtain the condition
$$
 P(\overline{S}) = \prod_{i=1}^{k} {x_i^{l_i} - 1 \over x_i - 1} 
 =
 \sum_{i=1}^{k} Q_i(x_1, x_2, \dots, x_k) (1 + x_i + x_i^3 + x_i^4)
 =
 \sum_{i=1}^{k} Q_i(x_1, x_2, \dots, x_k) (1 + x_i)^2 (1 - x_i + x_i^2).
 \leqno(4)
$$
The remainder of the argument cannot be the same as in example II
because all the roots of the polynomial $1 + x + x^3 + x^4$ are roots
of unity. Thus it is possible to select the sides $l_i$ so that $P(S)$
vanishes on the manifold of the ideal 
$(1 + x_1 + x_1^3 + x_1^4, \cdots, 1 + x_k + x_k^3 + x_k^4)$.
But nevertheless $P(S)$ does not belong to this ideal, for any
polynomial in the ideal, when expanded in powers of 
$1 + x_1, 1 + x_2, \cdots, 1 + x_k$ has no term in
$$
 (1 + x_1)(1 + x_2) \cdots (1 + x_k), \quad \hbox{whereas} \quad
 { \partial^k P(\overline{S}) \over \partial x_1 \cdots \partial x_k } 
 \ne 0
$$
when $x_1 = x_2 = \cdots = x_k = -1$ unless some $l_i = 1$.
This later case is easily excluded.

{\it Example IV:} %% (X X X . X X X)
Is there a rectangular $k$-dimensional parallelopiped which can be
covered by the straight polyomino formed by taking seven adjacent
cubes and deleting the middle one? 

Proceeding just as before, we obtain
$$
 P(\overline{S}) = \prod_{i=1}^{k} {x_i^{l_i} - 1 \over x_i - 1} 
 =
 \sum_{i=1}^{k} Q_i(x_1, x_2, \dots, x_k) (1 + x_i + x_i^2 + x_i^4 + x_i^5 + x_i^6)
 =
 \sum_{i=1}^{k} Q_i(x_1, x_2, \dots, x_k) { (x_i^4 + 1) (x_i^3 - 1) \over  x_i - 1} .
 \leqno(5)
$$
Again, the roots of $1 + x + x^2 + x^4 + x^5 + x^6$ are all roots of unity.
In this case, however, $P(\overline{S})$ will belong to the ideal
$(1 + x_1 + x_1^2 + x_1^4 + x_1^5 + x_1^6, \cdots, 
  1 + x_k + x_k^2 + x_k^4 + x_k^5 + x_k^6)$
if the integers $l_i$ are divisible by 24. This follows from the fact
that $x^{24} - 1$ is divisible by $(x^3 - 1) (x^4 + 1)$. To handle the
problem it is necessary then to make use of the condition that the
coefficients of the polynomials $Q_i(x_1, x_2, \dots, x_k)$ be 0 or 1,
or possibly, of the weaker condition, that they be nonnegative.
We have had no success with this; we can say only that no solution
exists when $k = 2$, a fact established by trail and error.
The case $k > 2$ is open.

{\it Example V:} %% (X . X X . X)
The preceding examples may lead one to suspect that any straight,
symmetric polyomino which cannot cover any segment, cannot cover
any rectangular parallelopiped. A polyomino formed by taking six
adjacent cubes and removing the second and fifth obviously cannot
cover any segment, but such a polyomino can cover a $7 \times 12$
rectangle. This is shown in Figure 1. 
There the polyominoes are numbered from 1 to 21 and a square
numbered $a$, $1 \leq a \leq 21$, is covered by the polyomino
numbered $a$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 15 08 16 08 08 13 08 13 13 19 13 21 %
% 05 14 05 05 17 05 12 18 12 12 20 12 %
% 15 04 16 04 04 11 04 11 11 19 11 21 %
% 15 14 16 07 17 07 07 18 07 19 20 21 %
% 03 14 03 03 17 03 10 18 10 10 20 10 %
% 15 02 16 02 02 09 02 09 09 19 09 21 %
% 01 14 01 01 17 01 06 18 06 06 20 06 %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
$$\vbox{
\halign{
  \strut \vrule height 4mm depth 2mm
  \hbox to 6mm { \hfil # \hfil } \vrule  && 
  \hbox to 6mm { \hfil # \hfil } \vrule  \cr
  \noalign{\hrule}
  15& 8&16& 8& 8&13& 8&13&13&19&13&21\cr
  \noalign{\hrule}
   5&14& 5& 5&17& 5&12&18&12&12&20&12\cr
  \noalign{\hrule}
  15& 4&16& 4& 4&11& 4&11&11&19&11&21\cr
  \noalign{\hrule}
  15&14&16& 7&17& 7& 7&18& 7&19&20&21\cr
  \noalign{\hrule}
   3&14& 3& 3&17& 3&10&18&10&10&20&10\cr
  \noalign{\hrule}
  15& 2&16& 2& 2& 9& 2& 9& 9&19& 9&21\cr
  \noalign{\hrule}
   1&14& 1& 1&17& 1& 6&18& 6& 6&20& 6\cr
  \noalign{\hrule}
}
} \atop \hbox{Fig. 1}%
$$
\smallskip

{\bf 3. The box problem.} 
Most of the results in the preceding section were of a negative character.
In this section we shall discuss what is perhaps the simplest problem of
polyomino coverings, obtain a necessary condition for its solvability
by means of the method of associated polynomials and then show that this
necessary condition, together with an auxiliary condition, is sufficiently
strong to guarantee the existence of a solution.

The problem, which we have called the box problem, is the following:
Under what circumstances is it possible to stack $k$-dimensional ``boxes''
with integral sides $b_1, b_2, \cdots, b_k$ in a $k$-dimensional ``room''
with sides $r_1, r_2, \cdots, r_k$ so that the room is completely filled?
Clearly, the volume of one of the boxes must divide the volume of the room
and each of the numbers $r_1, r_2, \cdots, r_k$ must be a linear combination
of $b_1, b_2, \cdots, b_k$, with nonnegative integral coefficients. We prove
a demonstrably stronger necessary condition:

\item{(A)} %%%  Property A  %%%
{\it 
If an arbitrary integer $h$ divides $t_h$ 
of the integers $b_1, b_2, \cdots, b_k$, \par
it must divide at least $t_h$ 
of the integers $r_1, r_2, \cdots, r_k$.}

It follows from (A) that, for example, a $30 \times 30$ square cannot be 
covered by $4 \times 9$ rectangles even though $30 \times 30$ is
divisible by $4 \times 9$ and $30 = 2 \cdot 9 + 3 \cdot 4$.

{\it Proof of} (A).
From (1) and (2) we have
$$
 \prod_{i=1}^{k} {x_i^{r_i} - 1 \over x_i - 1} 
 =
 \sum_{\sigma} Q_{\sigma}(x_1, x_2, \dots, x_k)
 \prod_{i=1}^{k} {x_{\sigma(i)}^{b_i} - 1 \over x_{\sigma(i)} - 1} \, ,
 \leqno(6)
$$
the summation being extended over all permutations $\sigma$ of the
integers $1, 2, \cdots, k$. Each permutation corresponds to a 
different way of stacking the boxes.

Suppose that only $q$ of the integers $r_1, r_2, \cdots, r_k$ are
divisible by $h$, where $q < t_h$. Then $k-q$ of the integers
$r_1, r_2, \cdots, r_k$ are not divisible by $h$. We may assume
that these are $r_1, r_2, \cdots, r_{k-q}$. In (6), let
$x_1 = x_2 = \dots = x_{k-q} = \omega$ where $\omega$ is a
primitive $h$th root of unity. In each product on the right side of (6)
there is at least one factor which vanishes, since $k-q+t_h > k-q+q=k$.
Thus the right side of (6) vanishes identically in 
$x_{k-q+1}, \cdots, x_k$, whereas the left side does not.

Condition (A) is clearly not sufficient. For example, it is impossible
to fill a $48 \times 48 \times 1$ room with $2 \times 3 \times 4$ boxes,
although condition (A) is satisfied. What is needed is an additional 
condition which ensures that $r_1, r_2, \cdots, r_k$ may be expressed
as linear combinations, with positive integral coefficients, of
$b_1, b_2, \cdots, b_k$. Such a condition is

\item{(B)} %%%  Property B  %%%
{\it $r_1, r_2, \cdots, r_k$ are sufficiently large. }

That is, there exists a positive integer, $N$, such that if
$r_i > N$, $i = 1, 2, \cdots, k$, and the set\footnote{*}%
{Set stands for multiset. The $b$'s and $r$'r need not be distinct.}
$\{ r_1, r_2, \cdots, r_k \}$ satisfies condition (A), then the box problem
has a solution. Here $N$ depends upon $b_1, b_2, \cdots, b_k$.

We prove that condition (A) and (B) are sufficient for the existence
of a solution of the box problem. Our plan is to split the room into
smaller parallelopipeds, each of whose sides is divisible by a different
number in the set $b_1, b_2, \cdots, b_k$. These smaller parallelopipeds
are then obviously coverable by boxes of sides $b_1, b_2, \cdots, b_k$;
hence the room is also.

Two lemmas, both well-known results, are required.

{\sc Lemma I.} %% Frobenius Problem.
{\it Let $a_1, a_2, \cdots, a_n$ be any set of positive integers,
and let $\delta$ be their greatest common divisor. Any sufficiently
large integer which is divisible by $\delta$ may be expressed as a
linear combination of $a_1, a_2, \cdots, a_n$ with positive
coefficients. }

An account of recent work based upon this lemma may be found in [2].
It was known to Frobenius, and may have been noticed by earlier
mathematicians.

{\sc Lemma II.} %% marriage theorem of Hall
{\it Given $k$ objects, each of which possesses one or more of the
attributes $P_1, P_2, \cdots, P_k$. For any set of $j$ attributes,
let there exists $j$ objects each possessing at least one attribute
of the set. Then it is possible to pair each object with one of its
attributes in such a way that no two objects are paired with the
same attribute. }

This lemma is due to P. Hall [3].

Let us order all nonempty subsets of $b_1, b_2, \cdots, b_k$ by
means of an index $j$, running from $1$ to $2^k - 1$. Let
$b_{j_1}, b_{j_2}, \cdots, b_{j_{m_j}}$ be the elements of the
$j$th subset. Let $\delta_j$ be the greatest common divisor of
$b_{j_1}, b_{j_2}, \cdots, b_{j_{m_j}}$. Condition (A) implies
that $\delta_j$ divides at least $m_j$ of the integers
$r_1, r_2, \cdots, r_k$.

Suppose that ${j_1}, {j_2}, \cdots, {j_{\alpha_i}}$ are the
indices of those greatest common divisors which divide $r_i$.
Condition (A) gives $\alpha_i \geq 1$. Then we may write
$$
 r_i = \sum A^{(i)}({j_1, l_1}, {j_2, l_2}, \cdots, {j_{\alpha_i}, l_{\alpha_i}}) ,
 \leqno(7)
$$
where the summation extends over all possible sets of values of
${l_1}, {l_2}, \cdots, {l_{\alpha_i}}$ such that
$$
 1 \leq l_1 \leq m_{j_1}, \;
 1 \leq l_2 \leq m_{j_2}, \; \cdots , \;
 1 \leq l_{\alpha_i} \leq m_{j_{\alpha_i}} ,
$$
and where the positive integer 
$A^{(i)}({j_1, l_1}, {j_2, l_2}, \cdots, {j_{\alpha_i}, l_{\alpha_i}})$
is divisible by each of the integers 
$b_{j_1 l_1}, b_{j_2 l_2}, \cdots$, $ b_{j_{\alpha_i} l_{\alpha_i}}$.
This result follows at once from the fact that the positive integers
form a distributive lattice under the operations $\cap =$ least common
multiple and $\cup =$ greatest common divisor.
One infers that $r_i$ is divisible by the greatest common divisor of
all the least common multiples one can form by taking one $b$ from each
set associated with the $\alpha_i$ $\delta$'s dividing $r_i$. If we 
apply Lemma I, identifying the integers $a_1, a_2, \cdots, a_n$ with
these least common multiples, we see that the integers
$A^{(i)}({j_1, l_1}, {j_2, l_2}, \cdots, {j_{\alpha_i}, l_{\alpha_i}})$
may be chosen to be positive if $r_i$ is sufficiently large.

We now divide our $k$-dimensional room into smaller parallelopipeds
by splitting the sides as indicated by (7). The sides of a 
representative smaller parallelopiped will be
$$
 A^{(1)} ({j_1, l_1}, {j_2, l_2}, \cdots, {j_{\alpha_1}, l_{\alpha_1}})
 \cdots 
 A^{(k)} ({j'_1, l'_1}, {j'_2, l'_2}, \cdots, {j'_{\alpha_k}, l'_{\alpha_k}}) .
 \leqno(8)
$$

We apply Lemma II, the $k$ objetcs being the sides of the smaller
parallelopiped and the $k$ attributes being divisibility by
$b_1, b_2, \cdots, b_k$. We show that the hypothesis of Lemma II
is fulfilled. Let $\delta_j$ be the greatest common divisor of
some set of $m_j$ $b$'s. Then $\delta_j$ will divide at least
$m_j$ of the positive integers $r_1, r_2, \cdots, r_k$;
by our construction, therefore, at least $m_j$ of the positive
integers (8) are divisible by at least one member of the given
set of $b$'s. From Lemma II we conclude that it is possible to
pair each side of the smaller parallelopiped with a distinct
member of the set $b_1, b_2, \cdots, b_k$ which will divide it.
Thus this parallelopiped may be covered with boxes of sides
$b_1, b_2, \cdots, b_k$. The larger room with sides 
$r_1, r_2, \cdots, r_k$ may then also be so covered.

N. G. de~Bruijn, in a problem published in the Hungarian journal,
{\it Mathematikai Lapok}\footnote{\dag}%
{12 (1961) 110 Problem 109 and 13 (1962) 314 Problem 119},
around 1960, dealt with an interesting aspect of the box-problem.
He showed that if the box problem has a solution and 
if $b_1$ divides $b_2$, $b_2$ divides $b_3$, etc.,
then the boxes may all be given the same orientation. 
Moreover, if every room covered by boxes of dimensions 
$b_1 \leq b_2 \leq b_3 \leq \cdots \leq b_k$
may be covered by boxes with the same orientation, 
then $b_1$ divides $b_2$, $b_2$ divides $b_3$, etc.
In the course of his proof, de~Bruijn established the necessary
portion of our box problem for boxes with dimensions
$1 \times 1 \times 1 \times \cdots \times m$. His method was
similar to ours and may be extended to the more general case.
\smallskip

{\bf Conclusion.} 
Certain mathematical games involving ``jumping'' may be discussed by means
of associated polynomials. One allows the associated polynomials to have
coefficients $-1, 0, 1$ in such a case. In treating questions involving
multiple covering of lattice points, the sole restriction that one need
place on $Q_1, Q_2, \cdots, Q_r$ is that they have nonnegative integral
coefficients.

Interesting problems arise when one considers infinite sets of lattice
points. Here the associated polynomial becomes an associated formal
power series. If one substitutes real or complex numbers for the
indeterminates, convergence difficulties present themselves, particularly
if the configuration extends from $-\infty$ to $+\infty$ in some direction.

Fundamentally, the method of attack in this paper goes back to Descartes.
The associated polynomial is merely the ``coordinate'' of the polyomino.
\bigbreak

% - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
\def\bib{\par\noindent\hangindent 20pt}
\centerline{ {\bf References} }

\bib
[1] \enspace
Solomon W. Golomb,
Checkerboards and polyominoes,
American Mathematical Monthly, 61 (Dec. 1954) 675--682.
Zbl. 57.1005.

\bib
[1*] \enspace
Solomon W. Golomb,
Polyominoes,
New York: Scribners, 1965.

\bib
[2] \enspace
Alfred Brauer and James E. Shockley,
On a problem of Frobenius,
Journal f\"ur die Reine und Angewandte Mathematik, 211 (1962) 215--220.
Zbl. 108.4604.

\bib
[3] \enspace
P. Hall,
On representatives of subsets,
Journal of the London Mathematical Society, 10 (part I) (1935) 26--30.
Zbl. 10.34503.

\bib
[4*] \enspace
Nicholas G. de~Bruijn,
Filling boxes with bricks,
American Mathematical Monthly, 76 (Jan. 1969) 37--40.
Zbl. 174.25501.

\smallskip
\noindent
References indicated with a star are additions.
\bye
