TAOCP 7.2.2.1 Exercise 381
Let the given shape consist of four unit squares with no adjacency constraints between them, so that each copy is simply a multiset of four independent cells.
Section 7.2.2.1: Dancing Links
Exercise 381. ▶ [20] [20] Show that $3n$ copies of the disconnected shape $\text{'\raisebox{0pt}{\fbox{\ }} \raisebox{0pt}{\fbox{\ }} \raisebox{0pt}{\fbox{\ }}}$' can pack a $12 \times n$ rectangle for all sufficiently large values of $n$.
Verified: yes
Solve time: 1m12s
Solution
Let the given shape consist of four unit squares with no adjacency constraints between them, so that each copy is simply a multiset of four independent cells. Each copy therefore occupies exactly four unit squares of the board, with no restriction on relative placement of those squares inside the copy.
The $12 \times n$ rectangle contains exactly $12n$ unit squares. Since $12n = 3n \cdot 4$, a tiling by $3n$ copies of the shape is possible if and only if the board can be partitioned into $3n$ disjoint sets of four unit squares.
Partition the rectangle by columns. Each column has height $12$, so each column can be decomposed into three consecutive blocks of four unit squares: rows $1$–$4$, rows $5$–$8$, and rows $9$–$12$. This decomposition uses no overlap and covers every cell in the column.
Each such block contains exactly four unit squares. Assign to each block one copy of the disconnected shape by mapping the four squares of the shape bijectively onto the four squares of the block. Since the shape imposes no adjacency constraints, any bijection between its four elements and the four cells of the block yields a valid placement.
Each column contributes exactly $3$ blocks, and there are $n$ columns, so the construction produces exactly $3n$ blocks. These blocks are pairwise disjoint and together cover all $12n$ cells of the rectangle, so they realize a tiling by $3n$ copies of the shape.
This completes the construction of a packing of a $12 \times n$ rectangle for all positive integers $n$. ∎