Problem 3.
Let

be a positive integer. Lexi has a dictionary

consisting of some
-letter strings containing only the letters

and
. Lexi would like to write either the letter

or the letter

in each cell of a

grid so that each column contains a string from

when read from top-to-bottom and each row contains a string from

when read from left-to-right.
What is the smallest integer

such that if

contains at least

different strings, then Lexi can fill her grid in this manner, no matter what strings are in
?