On the pentomino exclusion problem (Q5953077)

The pentomino exclusion problem, due to \textit{S. W. Golomb} [Polyominoes: puzzles, patterns, problems, and packings (Princeton University Press, Princeton, NJ) (1994; Zbl 0831.05020)], asks for the minimum number of squares in an arrangement \({\mathcal A}\) of unit squares on a \(k\times n\) chessboard \({\mathcal C}_{k,n}\) that has the property that its complement \(\overline{\mathcal A}\) in \({\mathcal C}_{k,n}\) does not contain a pentamino (connected polyomino composed of five unit squares). Such an arrangement \({\mathcal A}\) is said to exclude all pentominoes. Using an appropriate concept of density for infinite plane tilings by polyominoes, the authors derive an asymptotic value for this minimum. They also determine this minimum explicitly for small values of \(k\), \(k\leq 4\).