EGMO

Sea $k$ un entero positivo. Alexa tiene un diccionario $\mathcal D$ que contiene algunas palabras de $k$ letras formadas sólo con las letras $A$ y $B$. En cada casilla de un tablero de tamaño $k\times k$, Alexa quiere escribir sólo la letra $A$ o la letra $B$, de tal manera que cada columna contenga una palabra de $\mathcal D$ cuando es leída de arriba a abajo y cada fila contenga una palabra de $\mathcal D$ cuando es leída de izquierda a derecha. ¿Cuál es el menor entero $m$ tal que si $\mathcal D$ contiene por lo menos $m$ palabras diferentes, entonces Alexa siempre puede llenar su tablero de esta manera, sin importar cuáles son las palabras que están en el diccionario $\mathcal D$?