Minimum Size of Word Search Containing All Strings of Length $l$

For notational ease, let $W(k,l)$ be defined to be the size of the smallest grid that holds all $k^l$ strings as specified.

A clear solution for $(k,l) = (2,2)$ is \begin{pmatrix} AB \\ BA \end{pmatrix} though this is by no means difficult to find. This structure can be used to find more upper bounds for $W(k,2)$. An example for $k = 4$ is given below.

\begin{pmatrix} DCAB \\ CDBA \end{pmatrix}

It is clear that $W(k,l) \geq l^2$, and for odd $l$, $W(k,l) > l^2$. The proof of the second of these follows form the observation that placing the string of all A's in any orientation in an $l \times l$ grid forces an A into every other possible string of length $l$ if $l$ is odd and allows only for the other diagonal to be the string of all Bs if $l$ is even. In the case $k = l = 2$, the construction succeeds, and it obviously fails if $k > 2$. If $l > 2$, then the attempted construction would look like

\begin{pmatrix} A X X & \dots & X X B \\ \vdots & AB & \vdots \\ \vdots & BA & \vdots \\ B X X & \dots & X X A \\ \end{pmatrix}

Now, every column and row contains an A and a B. Consider inserting the string with 2 central Bs and all other characters A. There is no place this can be inserted, as stated. Therefore, $W(k,l) > l^2$ for all $k,l > 2$.

This proof lead me to attempt non-square solutions, and I have found the following solution for $(k,l) = (2,3)$;

\begin{pmatrix} ABBB \\ AABX \\ ABAX \end{pmatrix}

where X is an arbitrary character. This suggests that $W(2,3) = 12$, and certainly that $W(2,3) \leq 12$. The shape of this construction would lead to a conjecture that for $l > 2, W(2,l) \leq l(l+1)$. An inductive proof would be natural to continue the problem. Now, we argue for this statement by demonstrating an algorithm to lift a construction for $l$ to $l+1$ (note: this construction is slightly flawed, see comments at end)

Consider the solution given above for the case $l = 3$. Now, lift the first column and row of the $3 \times 4$ region to create a $4 \times 5$ region (we place O where new space appears)

\begin{pmatrix} ABBBO \\ AOOOO \\ AOABX \\ OOBAX \\ \end{pmatrix}

Now, clearly the bottom left O must be an A and the top right O must be a B. We also suppose that the O furthest right is arbitrary, and denote this with X. Now, we have

\begin{pmatrix} ABBBB \\ AOOOX \\ AOABX \\ AOBAX \\ \end{pmatrix}

Observe that this process has recreated each all-A and all-B strings and has effectively split every string 123 from the previous construction into the string 1023 (or alternatively 3201). Let the corner O be an A (chosen to maintain symmetry) and, starting from the bottom of L shape of Os, chose the Os to be B or A, starting with B and alternating. We then obtain

\begin{pmatrix} ABBBB \\ AABAX \\ AAABX \\ ABBAX \end{pmatrix}

which contains every string of length 4 in two letters. This strategy works because the columns and rows of this grid share a symmetry - before the insertion, row 4 and column 3 were opposite strings, so inserting B in each guarantees a different string for each, and similarly with row 3 and column 4. I believe that this sort of algorithm (creating an L and filling it in) will generate all solutions, but I cannot pin down what the algorithm is precisely for higher $l$.

Now, for $k = 3$, I have found that $W(3,2) = 6$ (not hard to find). I the problem continues to have the same kind of structure as it did for $k=2$, I would conjecture that $W(3,3) = (3+1)(3+2) = 20$.

A similar pattern seems to hold for $k = 4$, simply because constructions for $k=2,3,4$ and $l = 2$ are very similar. However, for $k > 4$, it becomes less obvious what $W(k,2)$ might be. From messing around, I am inclined to believe that $W(5,2) = 12$, given the construction

\begin{pmatrix} ABBD \\ AEED \\ DCCA \end{pmatrix}

and the difficulties in trying to establish any other grid that works.

NOTE: I realize now that my "proof" that $W(2,l) \leq l(l+1)$ is flawed. However, I have decided to leave the faulty proof up as a reference, because I believe that, algorithmically, the method of creating L shapes is a good greedy algorithm for this problem. This is similar in many ways to the algorithm offered by the author, except that the L created is internal and that we start work with a near-square instead of a square.

The best genuine upper bound I can think of as of yet would be the following;

Given a copy of a grid solving $W(k,l-1)$, we can create a copy of this grid, rotate it 90 degrees, and place it to the right of the initial copy with one column of empty space. Fill that empty column with Bs and cap the right and left ends of the shape with columns of As. This process is a geometric means of achieving the property that all length $l$ words consist of a starting A or B with any $l-1$ word following. If we let $W(k,l-1) = rc$ with $r$ representing rows of the grid and $c$ representing columns, we can write the inequality

$$W(2,l) \leq (2r+3)c = 2W(2,l) + 3c$$

Clearly, this is a very inefficient method, and it is recursive, which is doubly annoying and not useful. But it is the strongest upper bound I could rigorously construct. This inequality could easily be extended to $k$ other than 2, but it wouldn't really be that helpful.

Given my greedy algorithm, I would make the following conjecture about the true value of $W(k,l)$;

There exists some function $a : (k,l) \to \mathbb{N}$ such that when one of $k,l$ is bigger than 2; $$W(k,l) = (l + k - 2 + a)(l + k - 1 + a)$$

which is to say that the best scenario is always a square with a single column added.