\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{Rioplatense 2019/L2/3}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 132}
\maketitle
\section*{Problem}
Let $n$ be a positive integer.
Let $S$ be a multiset of $2n+1$ numbers less or equal
than $2^n$ with the following property: the product of any $n$ numbers of $S$
divides the product of the $n+1$ remaining numbers of $S$.
Prove that $S$ has at least $2$ equal numbers.
\section*{Video}
\href{https://www.youtube.com/watch?v=3X6YcQybomM&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/3X6YcQybomM}}
\section*{External Link}
\url{https://aops.com/community/p28630932}
\newpage
\section*{Solution}
We start by analyzing a particular prime:
\begin{claim*}
Let $p$ be a fixed prime,
and let \[ e_0 \leq \dots \leq e_{2n} \] be the $\nu_p$'s of the elements of $S$.
There exists an index $k$ such that
\[ e_{k+1} = e_{k+2} \dots = e_{k+2n-e_0}. \]
\end{claim*}
\begin{proof}
Write the above inequality as
\[ \sum_{i=1}^{n} \left( e_n - e_i \right)
+ \sum_{i=n+1}^{2n} \left( e_i - e_n \right) \le e_0 \]
where
\begin{align*}
0 &= e_n-e_n \leq e_n-e_{n-1} \leq e_n-e_{n-2} \leq \dots \leq e_n-e_1 \\
0 &\leq e_{n+1}-e_n \le e_{n+2}-e_n \leq \dots \leq e_{2n}-e_n.
\end{align*}
If we set $A = \sum_{i=1}^{n} \left( e_n - e_i \right)$
and $B = \sum_{i=n+1}^{2n} \left( e_i - e_n \right)$, then
in fact the smallest $n-A$ summands of $A$
and the smallest $n-B$ summands of $B$ must all be zero.
These produce the $A+B \leq 2n-e_0$ required indices.
\end{proof}
We now proceed in two cases, by induction on $n$.
The base cases $n=0,1,2$ are clear, so assume $n \geq 3$.
\begin{itemize}
\ii Assume there is a prime $p$ that doesn't divide every element of $S$
(i.e.\ $e_0=0$ for some prime $p$ in the claim's notation).
Then by the above, in fact there is one element of $S$ not divisible by $p$, say $x$,
and all other elements of $S$ have the same exponent of $p$.
Pick any $y \in S$ with $y \neq x$
and apply induction hypothesis onto $\frac1p \cdot (S \setminus \{x,y\})$.
\ii Otherwise, assume we're in a situation where the primes $p_1$, \dots, $p_m$
appear with nonzero minimum multiplicities $u_1$, \dots, $u_m$, respectively.
Obviously we may assume $\sum u_i \leq n-1$,
otherwise even the GCD of all the elements is at least $2^{u_1 + \dots + u_m}$.
In particular, $\max(u_i) \le n-1$; also (as $u_i \ge 1$) we have $m \leq n-1$.
Imagine the following algorithm.
Write all elements of $S$ on the blackboard.
Then for $i=1,\dots,m$, take the index promised by the claim for the prime $p_i$,
and draw an X on all $u_i+1$ elements not corresponding to those $e_i$'s.
If, after the algorithm ends, there are at least two numbers not X'ed out, we win.
However, the total number of X's is $\sum(u_i+1) \leq (n-1) + m = 2n-2$.
\end{itemize}
\end{document}