MathDB

Let

k

be a positive integer. Lexi has a dictionary

\mathbb{D}

consisting of some

k

-letter strings containing only the letters

A

and

B

. Lexi would like to write either the letter

A

or the letter

B

in each cell of a

k \times k

grid so that each column contains a string from

\mathbb{D}

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

\mathbb{D}

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

m

such that if

\mathbb{D}

contains at least

m

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

\mathbb{D}

3