12th European Girls' Mathematical Olympiad (EGMO 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}$ ?

Solution
Replace $A$ with $0$ and $B$ with $1$ .

The answer is $m=2^{k-1}$ . To show that $m=2^{k-1}-1$ does not work, take $\mathcal{D}$ containing all strings other than $00 \cdots 0$ starting with $0$ . Then, the top row of the grid must contain a $1$ , but no string in $\mathcal{D}$ starts with $1$ , a contradiction.

Let two strings be complementary if the corresponding digits in each position are opposite. Notice that $\mathcal{D}$ cannot contain either $00 \cdots 0$ or $11 \cdots 1$ , otherwise we can fill the grid with either zeroes or ones. Since there are $2^{k-1}-1$ remaining complementary pairs and $2^{k-1}$ strings in $\mathcal{D}$ , there must be a pair of complementary strings in $\mathcal{D}$ . Let $s=a_1a_2 \cdots a_k$ be one of these strings. Fill the grid such that the cell in the $i^\text{th}$ row and $j^\text{th}$ column is congruent to $a_i+a_j \pmod 2$ . This construction ensures that each row and each column is either $s$ or its complement, so we are done.