\documentclass[11pt]{scrartcl}
\usepackage{evan}

\begin{document}
\title{EGMO 2023/3}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 123}
\maketitle

\section*{Problem}
Let $k$ be a fixed 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}$?

\section*{Video}
\href{https://www.youtube.com/watch?v=PcPjYpkwY_g&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/PcPjYpkwY\_g}}

\section*{External Link}
\url{https://aops.com/community/p27522967}

\newpage

\section*{Solution}
Answer: $|\mathbb{D}| \ge 2^{k-1}$ is sufficient to fill the grid.

\paragraph{Counterexample where $|\mathbb{D}| = 2^{k-1}-1$.}
Let $\mathbb{D}$ be all the words that start with $A$
other than the all-$A$ string.
There can't be any construction because the first row would contain a $B$,
but no words in $\mathbb{D}$ start with $B$.

\paragraph{Sufficiency proof when $|\mathbb{D}| \ge 2^{k-1}$.}
If $\mathbb{D}$ contains either the all-$A$ or all-$B$ string, we're done.

Otherwise, pair the remaining $2^k-2$ possible strings into $2^{k-1}-1$ pairs
where we pair two strings if they have no overlapping letters in the same
position (i.e.\ they are \emph{opposites}, like $ABBAA$ and $BAABB$).
Because $|\mathbb{D}| > 2^{k-1}-1$, it follows $\mathbb{D}$ has a pair of
such opposites in it.

Then it's possible to fill the grid with just those two words,
e.g.\ $ABBAA$ gives the grid
\[
  \begin{bmatrix}
    A & B & B & A & A \\
    B & A & A & B & B \\
    B & A & A & B & B \\
    A & B & B & A & A \\
    A & B & B & A & A
  \end{bmatrix}.
\]

\end{document}
