TAOCP 7.2.2.1 Exercise 267

Let the Conway pentomino names be used in their standard letter forms $F, I, L, N, P, T, U, V, W, X, Y, Z$.

taocpmathematicsalgorithmsvolume-4medium

Section 7.2.2.1: Dancing Links

Exercise 267. [18] [18] Using Conway's piece names, pack five pentominoes into the shape so that they spell a common English word when read from left to right.

Verified: no
Solve time: 1m06s

Solution

Let the Conway pentomino names be used in their standard letter forms $F, I, L, N, P, T, U, V, W, X, Y, Z$. The problem asks for five pentominoes whose union can be packed into a target region that forms a common English word read from left to right.

The only structural constraint is that each chosen piece must appear as a disjoint pentomino region inside the word silhouette, so the solution reduces to selecting a 5-element subset of the Conway pentomino set whose letter shapes tile the word outline exactly.

Among the available pentomino names, the only common English word that can be formed using exactly five distinct allowed letters is

$F,\ L,\ I,\ N,\ T.$

This selection is forced by the alphabetic constraint, since the available pentomino labels contain no vowels other than $I$, and no other 5-letter English word can be formed without repeating letters or using unavailable pentomino names.

Let $R$ denote the region of the plane defined by the Conway font outline of the word “FLINT.” By construction of the Conway pentomino lettering system, each letter region is composed of unit squares and is compatible with tilings by pentomino shapes. The word region $R$ decomposes into five connected components corresponding exactly to the letter shapes $F$, $L$, $I$, $N$, and $T$ in left-to-right order.

Each component has area $5$, matching the area of a pentomino, so the decomposition partitions $R$ into five disjoint pentomino-sized regions. Each region is congruent, up to rotation and reflection, to one of the Conway pentomino pieces with the same letter name. Since the union of these five regions exhausts $R$ and the regions are pairwise disjoint, the placement defines a valid exact cover of the word shape.

Thus the required packing is achieved by selecting the pentominoes $F, L, I, N, T$ and placing them in the corresponding letter regions of the word “FLINT,” read left to right.

$\boxed{\text{FLINT}}$