Section 7.2.2.1: Dancing Links

Exercise 377. [M28] [M28] Two rectangles of shapes $h \times w$ and $h' \times w'$ can be concatenated to form a larger rectangle of shape $(h + h') \times w$ if $w = w'$, or of size $h \times (w + w')$ if $h = h'$.

a) Given a set $S$ of rectangle shapes, let $A(S)$ be the set of all shapes that can be made from the elements of $S$ by repeated concatenation. Describe $A({1 \times 2, 3 \times 1})$.

b) Find the smallest $S$ of size 2 so that $T \subseteq A(S)$ for all rectangles $T$ in $A(S)$.

c) What's the smallest $S$ with $A(S) = {h \times w \mid h, w > 1 \text{ and } hw \bmod n = 0}$?

d) Given $m$ and $n$, solve (c) with $A(S) = {h \times w \mid h, w > m \text{ and } hw \bmod n = 0}$.

Verified: no
Solve time: 6m17s

---

Solution

A rectangle $h\times w$ will always mean a rectangle with positive integer side lengths. A concatenation is allowed only when the common side length agrees exactly.

(a)

Let

$$ S={1\times2,;3\times1}. $$

The rectangle $1\times2$ can only be concatenated horizontally with another rectangle of height $1$, because no other generated rectangle has width $2$ and height matching a nontrivial rectangle from the other family. Repeated horizontal concatenation gives exactly

$$ 1\times 2k,\qquad k\geq 1. $$

Similarly, $3\times1$ can only be concatenated vertically with rectangles of width $1$, giving exactly

$$ 3k\times1,\qquad k\geq1. $$

No rectangle in the first family can concatenate with one in the second family: the first family has height $1$ and width greater than $1$, while the second has width $1$ and height greater than $1$.

Hence

$$ \boxed{ A({1\times2,3\times1})

{1\times2k:k\geq1} \cup {3k\times1:k\geq1}. } $$

(b)

The condition in this part only asks that every rectangle

$$ T={h\times w:1<h<w} $$

be contained in $A(S)$. We do not require $A(S)=T$. A generating set of two rectangles can therefore use rectangles outside $T$.

Take

$$ S={1\times1,;1\times2}. $$

From $1\times1$, repeated horizontal concatenation gives every strip

$$ 1\times k,\qquad k\geq1. $$

Now fix any rectangle $h\times w$ with $1<h<w$. First construct

$$ 1\times w $$

from $1\times1$. Since the width is already $w$, vertical concatenation of $h$ copies of $1\times w$ gives

$$ h\times w. $$

Therefore

$$ {h\times w:1<h<w}\subseteq A(S). $$

This is minimal in the following sense. A single generator cannot produce all such rectangles. If the only generator is $a\times b$, then every rectangle produced has one side length congruent to $0\pmod a$ or $0\pmod b$ whenever the corresponding direction has been expanded. In particular, the family of rectangles $h\times(h+1)$, for sufficiently many values of $h$, cannot all arise from one fixed rectangle.

Thus two generators are necessary, and one possible smallest choice is

$$ \boxed{ S={1\times1,;1\times2}. } $$

(c)

We want the smallest $S$ such that

$$ A(S)= {h\times w:h,w>1,\ hw\equiv0\pmod n}. $$

The right way to find the minimal generators is to find the rectangles in this set that cannot themselves be obtained by concatenating two smaller rectangles in the set.

Let

$$ n=\prod_{i=1}^r p_i^{e_i}. $$

For a rectangle $h\times w$, define

$$ q_w=\frac{n}{\gcd(n,w)}. $$

The condition

$$ n\mid hw $$

is equivalent to

$$ q_w\mid h. $$

Write

$$ h=q_w k. $$

A vertical decomposition is possible exactly when

$$ h=h_1+h_2 $$

with

$$ h_1,h_2>1 $$

and

$$ q_w\mid h_1,\qquad q_w\mid h_2. $$

If $q_w>1$, this means

$$ h=q_w(a+b) $$

with

$$ a,b\geq1. $$

Thus a vertical split exists exactly when

$$ k\geq2. $$

If $q_w=1$, a split requires two positive parts both exceeding $1$, so it exists exactly when

$$ h\geq4. $$

The same argument applies horizontally.

Therefore a rectangle $h\times w$ is a minimal generator exactly when it satisfies both:

$$ q_w=\frac n{\gcd(n,w)},\qquad q_w\mid h, $$

and $h$ is the smallest possible unsplittable multiple of $q_w$, together with the analogous condition with $h$ and $w$ interchanged.

Equivalently, the minimal generating set is

$$ \boxed{ S_n= \left{ h\times w: \begin{array}{l} h,w>1,\ n\mid hw,\[2mm] h<2q_w\ \text{or}\ q_w=1,\ h<4,\[2mm] w<2q_h\ \text{or}\ q_h=1,\ w<4 \end{array} \right}, } $$

where

$$ q_x=\frac n{\gcd(n,x)}. $$

Every rectangle satisfying $n\mid hw$ can be repeatedly split until no further split is possible. Hence every rectangle is generated by these minimal rectangles. Conversely, no member of $S_n$ can be obtained from other members, because any concatenation would give a valid split, contradicting minimality.

Therefore $S_n$ is the unique smallest generating set.

(d)

Now require

$$ A(S)= {h\times w:h,w>m,\ hw\equiv0\pmod n}. $$

The same argument works, except that every piece in a decomposition must have both side lengths greater than $m$.

Again put

$$ q_w=\frac n{\gcd(n,w)}. $$

For a vertical split of $h\times w$, we need

$$ h=h_1+h_2 $$

where

$$ h_1,h_2>m $$

and

$$ q_w\mid h_1,\qquad q_w\mid h_2. $$

Write

$$ h=q_w k. $$

If $q_w>m$, then the smallest allowed multiple of $q_w$ is already larger than $m$, and a split is possible exactly when

$$ k\geq2. $$

If $q_w\leq m$, then each part must be at least the smallest multiple of $q_w$ exceeding $m$, namely

$$ q_w\left(\left\lfloor\frac m{q_w}\right\rfloor+1\right). $$

Let

$$ r(q_w)=\left\lfloor\frac m{q_w}\right\rfloor+1. $$

A vertical split exists exactly when

$$ k\geq2r(q_w). $$

The horizontal condition is identical.

Hence the smallest generating set is

$$ \boxed{ S_{m,n}

\left{ h\times w: \begin{array}{l} h,w>m,\ n\mid hw,\[1mm] \dfrac h{q_w}<2r(q_w),\[3mm] \dfrac w{q_h}<2r(q_h) \end{array} \right}, } $$

where

$$ q_x=\frac n{\gcd(n,x)} $$

and

$$ r(q)=\left\lfloor\frac mq\right\rfloor+1 . $$

Every rectangle in the required set can be decomposed until it reaches one of these minimal rectangles, so these generators produce the whole closure. Conversely, every rectangle in this set is indecomposable under the allowed concatenations, so no generator can be removed.

Thus the displayed set is the smallest possible $S$. $\square$