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: 5m29s

---

The previous solution fails because it assumes concatenation can generate new side lengths. In fact, concatenation never creates new labels for sides; it only combines rectangles that already share an exact side length.

The correct analysis starts from this invariant.

Fundamental invariant (correct model)

Let $S$ be a set of rectangles.

Each rectangle $(h,w)\in S$ introduces two labels: a height label $h$ and a width label $w$.

Concatenation rules are:

• If two rectangles share the same width $w$, we may form $(h+h',w)$.
• If two rectangles share the same height $h$, we may form $(h,w+w')$.

Crucial consequence:

No operation ever creates a new height label or a new width label.

All rectangles in $A(S)$ use only heights and widths that already appear in $S$.

Thus:

$$ {\text{heights in }A(S)} \subseteq {h : (h,w)\in S},\quad {\text{widths in }A(S)} \subseteq {w : (h,w)\in S}. $$

What changes is not the alphabet of side lengths, but which linear combinations are reachable within each fixed label.

Key structural consequence

Fix a width $w$. All rectangles in $A(S)$ with width $w$ have heights in the additive semigroup generated by:

$$ H_w = {h : (h,w)\in S}. $$

Similarly, for a fixed height $h$, widths in $A(S)$ lie in the additive semigroup generated by:

$$ W_h = {w : (h,w)\in S}. $$

No interaction produces new labels outside those already present in $S$.

(a) Compute $A({1\times 2,;3\times 1})$

Start with:

$$ S = {(1,2), (3,1)}. $$

Step 1: identify label structure

Heights present: ${1,3}$

Widths present: ${2,1}$

Thus possible rectangles can only have:

$$ h \in {1,3}, \quad w \in {1,2} \text{ after closure constraints are checked.} $$

But we must compute closures per label.

Step 2: width $2$

For width $2$, the only incident rectangle is $(1,2)$. So:

$$ H_2 = {1}. $$

Additive semigroup generated by ${1}$ is:

$$ {1,2,3,\dots}. $$

Thus:

$$ (h,2) \in A(S) \text{ for all } h \ge 1. $$

Step 3: width $1$

For width $1$, the only incident rectangle is $(3,1)$. So:

$$ H_1 = {3}. $$

Additive semigroup generated by ${3}$ is:

$$ {3k : k \ge 1}. $$

Thus:

$$ (h,1) \in A(S) \iff h \equiv 0 \pmod 3. $$

Step 4: no width creation

There is no second rectangle with height $1$, so we cannot add widths at height $1$. Similarly, no second rectangle with width $2$, so widths stay rigid there.

Thus no new width labels appear.

Final answer for (a)

$$ \boxed{ A({1\times 2,,3\times 1})

{(h,2)\mid h\ge 1} ;\cup; {(3k,1)\mid k\ge 1} } $$

(b) Smallest $S$ of size 2 such that $T \subseteq A(S)$ for all rectangles $T \in A(S)$

This condition means:

$S$ must be closed under its own generated structure and no smaller set generates the same closure.

From part (a), any generating set must produce:

• one width that admits all heights $\Rightarrow$ requires a rectangle with height $1$
• one width that restricts heights to multiples of $3$ $\Rightarrow$ requires a rectangle with height $3$
• and two distinct widths must exist ($1$ and $2$) to separate behaviors

Thus any valid generator set must include:

• a rectangle with height $1$ and some width $w_1$
• a rectangle with height $3$ and some width $w_2$

To reproduce the same closure structure minimally, we may choose smallest widths:

$$ S = {1\times 2,; 3\times 1}. $$

Removing either breaks one of the two independent semigroup constraints, so it is minimal.

$$ \boxed{S = {1\times 2,; 3\times 1}} $$

(c) Smallest $S$ such that

$$ A(S)={h\times w \mid h,w>1,; hw \equiv 0 \pmod n}. $$

Critical observation

From the invariant:

• $A(S)$ can only involve heights and widths explicitly appearing in $S$.
• Therefore $A(S)$ can never contain all integers $h>1$ or $w>1$ unless $S$ already contains them.

But the target set contains infinitely many distinct heights and widths:

$$ {h\times w : h,w>1,; n \mid hw} $$

includes all sufficiently large $h$ and $w$, depending on factorization of $n$.

There is no mechanism in concatenation to generate new labels such as $6$, $10$, $15$, etc., unless they already appear in $S$.

Thus:

Conclusion

No finite set $S$ can satisfy the requirement.

Moreover, any valid $S$ must already contain every rectangle in the target set.

So the minimal choice is:

$$ \boxed{ S = {h\times w \mid h,w>1,; hw \equiv 0 \pmod n} } $$

and then trivially $A(S)=S$ because no new labels are ever introduced beyond those already present.

(d) Case $h,w>m$ and $hw \equiv 0 \pmod n$

The same reasoning applies.

The closure operation does not create new side lengths, so it cannot generate all integers $>m$ unless they are already present.

Hence the same fixed-point argument applies:

$$ \boxed{ S = {h\times w \mid h,w>m,; hw \equiv 0 \pmod n} } $$

and this is minimal because removing any element removes it from $A(S)$ as well.

Final summary

• Concatenation only forms additive combinations along fixed side labels.
• It never introduces new height or width values.
• Therefore $A(S)$ is controlled entirely by which labels appear in $S$, not by multiplicative or divisor structure.
• Parts (c) and (d) collapse to fixed-point problems: the only way to realize the full target set is to include it already in $S$.