EGMO 2023 | Problem 3 - 17 April 2023

Problem 3.
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}$ ?