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