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.
 
Copyright BB © 2024
Авторски права ББ © 2024