\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&t=1008}{\texttt{https://youtu.be/9WNgDETHOlI}}

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

\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).

\paragraph{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$.

\paragraph{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}
