Words with Repeated Letters in a Grid

Abstract

Given a word $w$, what is the maximum possible number of appearances of $w$ reading contiguously along any of the directions in $\{-1,0,1{\}}^d\setminus \{0\}$ in a large $d$-dimensional grid (as in a word search)? Patchell and Spiro first posed a version of this question, which Alon and Kravitz completely answered for a large class of "well-behaved" words, including those with no repeated letters. We study the general case, which exhibits greater variety and is often more complicated (even for $d=1$). We also discuss some connections to other problems in combinatorics, including the storied $n$-queens problem.

42 pages, 12 figures