The Maximum Number of Appearances of a Word in a Grid

Abstract

How can you fill a $3\times 3$ grid with the letters A and M so that the word ``AMM'' appears as many times as possible in the grid? More generally, given a word $w$ of length $n$, how can you fill an $n\times n$ grid so that $w$ appears as many times as possible? We solve this problem exactly for several families of words, and we asymptotically solve this problem in higher-dimensional grids.

21 pages, American Mathematically Monthly