\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{Iberoamerican 2021/1}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 87}
\maketitle
\section*{Problem}
Let $P = \{p_1,p_2,\ldots, p_{10}\}$ be a set of $10$ different prime
numbersand let $A$ be the set of all the integers greater than $1$
so that their prime decomposition only contains primes of $P$.
The elements of $A$ are colored in such a way that:
\begin{itemize}
\item each element of $P$ has a different color,
\item if $m,n \in A$, then $mn$ is the same color of $m$ or $n$,
\item for any pair of different colors $\mathcal{R}$ and $\mathcal{S}$,
there are no $j,k,m,n\in A$ (not necessarily distinct from one another),
with $j,k$ colored $\mathcal{R}$ and $m,n$ colored $\mathcal{S}$,
so that $j$ is a divisor of $m$ and $n$ is a divisor of $k$, simultaneously.
\end{itemize}
Prove that there exists a prime of $P$ so that all its multiples in $A$ are the same color.
\section*{Video}
\href{https://www.youtube.com/watch?v=Wx4-fscAMB8&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ&index=2}{\texttt{https://youtu.be/Wx4-fscAMB8}}
\newpage
\section*{Solution}
By abuse of notation, we identify colors as subsets of $A$.
Let's say color $\mathcal A$ is \emph{recessive} to
color $\mathcal B$
if there exists $a \in \mathcal A$ and $b \in \mathcal B$
such that $a \mid b$.
We write this as $\mathcal A \lessdot \mathcal B$.
\begin{claim*}
[Anti-symmetry]
We can't have both
$\mathcal A \lessdot \mathcal B$ and
$\mathcal B \lessdot \mathcal A$.
\end{claim*}
\begin{proof}
This is the third condition.
\end{proof}
\begin{claim*}
If $\mathcal A \lessdot \mathcal B$,
then for any $a \in \mathcal A$ and $b \in \mathcal B$,
we have $ab \in \mathcal B$.
\end{claim*}
\begin{proof}
By second condition,
we know $ab$ is colored either $\mathcal A$ or $\mathcal B$,
but the former case would cause $\mathcal B \lessdot \mathcal A$
since $b \mid ab$.
\end{proof}
\begin{claim*}
[Transitivity]
If $\mathcal A \lessdot \mathcal B$,
and $\mathcal B \lessdot \mathcal C$,
then $\mathcal A \lessdot \mathcal C$.
\end{claim*}
\begin{proof}
Suppose $a \mid b$ and $b' \mid c$ witnesses
the first two relations.
Now, $bb' \in \mathcal B$, and $bc \in \mathcal C$.
So $a \mid bb' \mid bc$ and we get $\mathcal A \lessdot \mathcal C$.
\end{proof}
It follows $\lessdot$ is a total order.
So it has a maximal element,
that is, a color $\mathcal M$ which is not recessive to any other.
Let $p \in \mathcal M$ be the prime of $P$ in $\mathcal M$,
promised by the first condition.
It now follows all multiples of $p$ are in $\mathcal M$,
via the second claim.
\end{document}