Olimpiadas de Matemáticas
Página de preparación y problemas

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 se lee de arriba a abajo y cada fila contenga una palabra de $\mathcal{D}$ cuando se lee 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}$?