\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{USAMO 2021/4}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 65}
\maketitle
\section*{Problem}
A finite set $S$ of positive integers has the property that,
for each $s\in S$, and each positive integer divisor $d$ of $s$,
there exists a unique element $t\in S$ satisfying $\gcd(s,t) = d$.
(The elements $s$ and $t$ could be equal.)
Given this information, find all possible values for the
number of elements of $S$.
\section*{Video}
\href{https://www.youtube.com/watch?v=9WNgDETHOlI}{\texttt{https://youtu.be/Nc4E8-QtjHk}}
\newpage
\section*{Solution}
The answer is that $|S|$ must be a power of $2$ (including $1$),
or $|S| = 0$ (a trivial case we do not discuss further).
\medskip
\textbf{Construction}:
For any nonnegative integer $k$,
a construction for $|S| = 2^k$ is given
by
\[ S = \left\{
(p_1 \text{ or } q_1)
\times
(p_2 \text{ or } q_2)
\times
\dots
\times
(p_k \text{ or } q_k)
\right\}
\]
for $2k$ distinct primes $p_1$, \dots, $p_k$, $q_1$, \dots, $q_k$.
\medskip
\textbf{Converse}: the main claim is as follows.
\begin{claim*}
In any valid set $S$,
for any prime $p$ and $x \in S$, $\nu_p(x) \le 1$.
\end{claim*}
\begin{proof}
Assume for contradiction $e = \nu_p(x) \ge 2$.
\begin{itemize}
\ii On the one hand, by taking $x$ in the statement,
we see $\frac{e}{e+1}$ of the elements of $S$ are divisible by $p$.
\ii On the other hand, consider a $y \in S$ such that
$\nu_p(y)=1$ which must exist (say if $\gcd(x,y) = p$).
Taking $y$ in the statement,
we see $\half$ of the elements of $S$ are divisible by $p$.
\end{itemize}
So $e=1$, contradiction.
\end{proof}
Now since $|S|$ equals the number of divisors of any element of $S$,
we are done.
\end{document}