% © Evan Chen
% Downloaded from https://web.evanchen.cc/

\documentclass[11pt]{scrartcl}
\usepackage[sexy]{evan}
\ihead{\footnotesize\textbf{\thetitle}}
\ohead{\footnotesize\href{http://web.evanchen.cc}{\ttfamily web.evanchen.cc},
    updated \today}
\title{USAMO 2012 Solution Notes}
\date{\today}

\begin{document}

\maketitle

\begin{abstract}
This is a compilation of solutions
for the 2012 USAMO.
The ideas of the solution are a mix of my own work,
the solutions provided by the competition organizers,
and solutions found by the community.
However, all the writing is maintained by me.

These notes will tend to be a bit more advanced and terse than the ``official''
solutions from the organizers.
In particular, if a theorem or technique is not known to beginners
but is still considered ``standard'', then I often prefer to
use this theory anyways, rather than try to work around or conceal it.
For example, in geometry problems I typically use directed angles
without further comment, rather than awkwardly work around configuration issues.
Similarly, sentences like ``let $\mathbb{R}$ denote the set of real numbers''
are typically omitted entirely.

Corrections and comments are welcome!
\end{abstract}

\tableofcontents
\newpage

\addtocounter{section}{-1}
\section{Problems}
\begin{enumerate}[\bfseries 1.]
\item %% Problem 1
Find all integers $n \ge 3$ such that
among any $n$ positive real numbers
$a_1$, $a_2$, \dots, $a_n$ with
\[ \max(a_1,a_2,\dots,a_n)
  \le n \cdot \min(a_1,a_2,\dots,a_n), \]
there exist three that are the side lengths
of an acute triangle.

\item %% Problem 2
A circle is divided into congruent arcs by $432$ points.
The points are colored in four colors such that
some $108$ points are colored red,
some $108$ points are colored green,
some $108$ points are colored blue,
and the remaining $108$ points are colored yellow.
Prove that one can choose three points of each color in such a way
that the four triangles formed by the chosen points
of the same color are congruent.

\item %% Problem 3
Determine which integers $n > 1$ have the property
that there exists an infinite sequence $a_1$, $a_2$, $a_3$, \dots
of nonzero integers such that the equality
\[ a_k + 2a_{2k} + \dots + na_{nk} = 0 \]
holds for every positive integer $k$.

\item %% Problem 4
Find all functions $f \colon \NN \to \NN$ such that
$f(n!) = f(n)!$ for all positive integers $n$ and such that
$m-n$ divides $f(m) - f(n)$ for all distinct positive integers $m$, $n$.

\item %% Problem 5
Let $P$ be a point in the plane of $\triangle ABC$,
and $\gamma$ a line through $P$.
Let $A'$, $B'$, $C'$ be the points where the
reflections of lines $PA$, $PB$, $PC$ with respect to $\gamma$
intersect lines $BC$, $CA$, $AB$ respectively.
Prove that $A'$, $B'$, $C'$ are collinear.

\item %% Problem 6
For integer $n \ge 2$,
let $x_1$, $x_2$, \dots, $x_n$ be real numbers satisfying
\[ x_1 + x_2 +  \dots + x_n = 0
  \quad\text{and}\quad x_1^2 + x_2^2 + \dots + x_n^2 = 1. \]
For each subset $A\subseteq\{1, 2, \dots, n\}$, define $S_A=\sum_{i\in A} x_i$.
(If $A$ is the empty set, then $S_A=0$.)
Prove that for any positive number $\lambda$,
the number of sets $A$ satisfying $S_A\geq\lambda$ is at most $2^{n-3}/\lambda^2$.
For which choices of $x_1$, $x_2$, \dots, $x_n$, $\lambda$ does equality hold?

\end{enumerate}
\pagebreak

\section{Solutions to Day 1}
\subsection{USAMO 2012/1, proposed by Titu Andreescu}
\textsl{Available online at \url{https://aops.com/community/p2669112}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Find all integers $n \ge 3$ such that
among any $n$ positive real numbers
$a_1$, $a_2$, \dots, $a_n$ with
\[ \max(a_1,a_2,\dots,a_n)
  \le n \cdot \min(a_1,a_2,\dots,a_n), \]
there exist three that are the side lengths
of an acute triangle.
\end{mdframed}
The answer is all $n \ge 13$.

Define $(F_n)$ as the sequence of Fibonacci numbers,
by $F_1 = F_2 = 1$ and $F_{n+1} = F_n + F_{n-1}$.
We will find that Fibonacci numbers show up naturally
when we work through the main proof,
so we will isolate the following calculation now
to make the subsequent solution easier to read.
\begin{claim*}
  For positive integers $m$, we have $F_m \le m^2$ if and only if $m \le 12$.
\end{claim*}
\begin{proof}
  A table of the first $14$ Fibonacci numbers is given below.
  \[
    \begin{array}{rrrrr rrrrr rrrr}
      F_1 & F_2 & F_3 & F_4 & F_5 & F_6 & F_7 & F_8 & F_9
        & F_{10} & F_{11} & F_{12} & F_{13} & F_{14} \\ \hline
      1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 & 89 & 144 & 233 & 377
    \end{array}
  \]
  By examining the table, we see that $F_m \le m^2$ is true for $m = 1, 2, \dots 12$,
  and in fact $F_{12} = 12^2 = 144$.
  However, $F_m > m^2$ for $m = 13$ and $m = 14$.

  Now it remains to prove that $F_m > m^2$ for $m \ge 15$.
  The proof is by induction with base cases
  $m = 13$ and $m = 14$ being checked already.
  For the inductive step, if $m \ge 15$ then we have
  \begin{align*}
    F_m &= F_{m-1} + F_{m-2} > (m-1)^2 + (m-2)^2 \\
    &= 2m^2 - 6m + 5 = m^2 + (m-1)(m-5) > m^2
  \end{align*}
  as desired.
\end{proof}

We now proceed to the main problem.
The hypothesis $\max(a_1,a_2,\dots,a_n)
\le n \cdot \min(a_1,a_2,\dots,a_n)$
will be denoted by $(\dagger)$.

\medskip

\textbf{Proof that all $n \ge 13$ have the property.}
We first show now that every $n \ge 13$ has the desired property.
Suppose for contradiction that no three numbers are the sides of an acute triangle.
Assume without loss of generality (by sorting the numbers)
that $a_1 \le a_2 \le \dots \le a_n$.
Then since $a_{i-1}$, $a_i$, $a_{i+1}$ are not the sides of an acute triangle
for each $i \ge 2$, we have that $a_{i+1}^2 \ge a_i^2 + a_{i-1}^2$;
writing this out gives
\begin{align*}
  a_3^2 &\ge a_2^2 + a_1^2 \ge 2a_1^2 \\
  a_4^2 &\ge a_3^2 + a_2^2 \ge 2a_1^2 + a_1^2 = 3a_1^2 \\
  a_5^2 &\ge a_4^2 + a_3^2 \ge 3a_1^2 + 2a_1^2 = 5a_1^2 \\
  a_6^2 &\ge a_5^2 + a_4^2 \ge 5a_1^2 + 3a_1^2 = 8a_1^2
\end{align*}
and so on.
The Fibonacci numbers appear naturally and by induction,
we conclude that $a_i^2 \ge F_i a_1^2$.
In particular, $a_n^2 \ge F_n a_1^2$.

However, we know $\max(a_1, \dots, a_n) = a_n$
and $\min(a_1, \dots, a_n) = a_1$,
so $(\dagger)$ reads $a_n \le n \cdot a_1$.
Therefore we have $F_n \le n^2$, and so $n \le 12$, contradiction!

\medskip

\textbf{Proof that no $n \le 12$ have the property.}
Assume that $n \le 12$.
The above calculation also suggests a way to pick the counterexample:
we choose $a_i = \sqrt{F_i}$ for every $i$.
Then $\min(a_1, \dots, a_n) = a_1 = 1$
and $\max(a_1, \dots, a_n) = \sqrt{F_n}$,
so $(\dagger)$ is true as long as $n \le 12$.
And indeed no three numbers form the sides of an acute triangle:
if $i < j < k$,
then $a_k^2 = F_k = F_{k-1} + F_{k-2} \ge F_j + F_i = a_j^2 + a_i^2$.
\pagebreak

\subsection{USAMO 2012/2, proposed by Gregory Galperin}
\textsl{Available online at \url{https://aops.com/community/p2669115}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
A circle is divided into congruent arcs by $432$ points.
The points are colored in four colors such that
some $108$ points are colored red,
some $108$ points are colored green,
some $108$ points are colored blue,
and the remaining $108$ points are colored yellow.
Prove that one can choose three points of each color in such a way
that the four triangles formed by the chosen points
of the same color are congruent.
\end{mdframed}
First, consider the $431$ possible non-identity rotations
of the red points, and count overlaps with green points.
If we select a rotation randomly,
then each red point lies over a green point
with probability $\frac{108}{431}$;
hence the expected number of red-green incidences is
\[ \frac{108}{431} \cdot 108 > 27 \]
and so by pigeonhole, we can find a red $28$-gon
and a green $28$-gon which are rotations of each other.

Now, look at the $430$ rotations of this $28$-gon
(that do not give the all-red or all-green configuration)
and compare it with the blue points.
The same approach gives
\[ \frac{108}{430} \cdot 28 > 7 \]
incidences, so we can find red, green, blue $8$-gons
which are similar under rotation.

Finally, the $429$ nontrivial rotations of this $8$-gon expect
\[ \frac{108}{429} \cdot 8 > 2 \]
incidences with yellow.
So finally we have four monochromatic $3$-gons,
one of each color, which are rotations of each other.
\pagebreak

\subsection{USAMO 2012/3, proposed by Gabriel Carroll}
\textsl{Available online at \url{https://aops.com/community/p2669119}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Determine which integers $n > 1$ have the property
that there exists an infinite sequence $a_1$, $a_2$, $a_3$, \dots
of nonzero integers such that the equality
\[ a_k + 2a_{2k} + \dots + na_{nk} = 0 \]
holds for every positive integer $k$.
\end{mdframed}
Answer: all $n > 2$.

For $n = 2$, we have $a_k + 2a_{2k} = 0$,
which is clearly not possible,
since it implies $a_{2^k} = \frac{a_1}{2^{k-1}}$
for all $k \ge 1$.

For $n \ge 3$ we will construct a \emph{completely multiplicative} sequence
(meaning $a_{ij} = a_i a_j$ for all $i$ and $j$).
Thus $(a_i)$ is determined by its value on primes,
and satisfies the condition as long as
$a_1 + 2a_2 + \dots + na_n = 0$.
The idea is to take two large primes and use Bezout's theorem,
but the details require significant care.

We start by solving the case where $n \ge 9$.
In that case, by Bertrand postulate there exists primes $p$ and $q$ such that
\[
  \left\lceil n/2 \right\rceil < q < 2\left\lceil n/2 \right\rceil
  \quad\text{and}\quad
  \half(q-1) < p < q-1.
\]
Clearly $p \neq q$, and $q \ge 7$, so $p > 3$.
Also, $p < q < n$ but $2q > n$, and $4p \ge 4\left( \half(q+1) \right) > n$.
We now stipulate that $a_r = 1$ for any prime $r \neq p,q$
(in particular including $r=2$ and $r=3$).
There are now three cases, identical in substance.
\begin{itemize}
  \ii If $p, 2p, 3p \in [1,n]$ then we would like to
  choose nonzero $a_p$ and $a_q$ such that
  \[ 6p \cdot a_p + q \cdot a_q = 6p + q - \half n (n+1) \]
  which is possible by B\'{e}zout lemma, since $\gcd(6p,q) = 1$.

  \ii Else if $p, 2p \in [1,n]$ then we would like to
  choose nonzero $a_p$ and $a_q$ such that
  \[ 3p \cdot a_p + q \cdot a_q = 3p + q - \half n (n+1) \]
  which is possible by B\'{e}zout lemma, since $\gcd(3p, q) = 1$.

  \ii Else if $p \in [1,n]$ then we would like to
  choose nonzero $a_p$ and $a_q$ such that
  \[ p \cdot a_p + q \cdot a_q = p + q - \half n (n+1) \]
  which is possible by B\'{e}zout lemma, since $\gcd(p, q) = 1$.
  (This case is actually possible in a few edge cases,
  for example when $n=9$, $q=7$, $p=5$.)
\end{itemize}

It remains to resolve the cases where $3 \le n \le 8$.
We enumerate these cases manually:
\begin{itemize}
  \ii For $n = 3$, let $a_n = (-1)^{\nu_3(n)}$.
  \ii For $n = 4$, let $a_n = (-1)^{\nu_2(n) + \nu_3(n)}$.
  \ii For $n = 5$, let $a_n = (-2)^{\nu_5(n)}$.
  \ii For $n = 6$, let $a_n =  5^{\nu_2(n)} \cdot 3^{\nu_3(n)} \cdot (-42)^{\nu_5(n)}$.
  \ii For $n = 7$, let $a_n = (-3)^{\nu_7(n)}$.
  \ii For $n = 8$, we can choose $(p,q) = (5,7)$ in the prior construction.
\end{itemize}

This completes the constructions for all $n > 2$.
\pagebreak

\section{Solutions to Day 2}
\subsection{USAMO 2012/4, proposed by Gabriel Dospinescu}
\textsl{Available online at \url{https://aops.com/community/p2669997}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Find all functions $f \colon \NN \to \NN$ such that
$f(n!) = f(n)!$ for all positive integers $n$ and such that
$m-n$ divides $f(m) - f(n)$ for all distinct positive integers $m$, $n$.
\end{mdframed}
Answer: $f \equiv 1$, $f \equiv 2$, and $f$ the identity.
As these obviously work, we prove these are the only ones.

By putting $n=1$ and $n=2$ we give $f(1), f(2) \in \{1,2\}$.
Also, we will use the condition
\[ m!-n! \text{ divides } f(m)! - f(n)!. \]
We consider four cases on $f(1)$ and $f(2)$,
and dispense with three of them.
\begin{itemize}
  \ii If $f(2) = 1$ then for all $m \ge 3$ we have
  $m!-2$ divides $f(m)! - 1$, so $f(m) = 1$
  for modulo $2$ reasons.
  Then clearly $f(1) = 1$.
  \ii If $f(1) = f(2) = 2$ we first obtain
  $3!-1 \mid f(3)!-2$, which implies $f(3) = 2$.
  Then $m! - 3 \mid f(m)! - 2$ for $m \ge 4$
  implies $f(m)=2$ for modulo $3$ reasons.
\end{itemize}
Hence we are left with the case where $f(1) = 1$ and $f(2) = 2$.
Continuing, we have
\[ 3!-1 \mid f(3)! - 1 \quad\text{and}\quad
  3!-2 \mid f(3)!-2 \implies f(3) = 3. \]

Continuing by induction, suppose $f(1) = 1$, \dots, $f(k) = k$.
\[ k! \cdot k = (k+1)! - k! \mid f(k+1)! - k! \]
and thus we deduce that $f(k+1) \ge k$, and hence
\[ k \mid \frac{f(k+1)!}{k!} - 1. \]
Then plainly $f(k+1) \le 2k$ for mod $k$ reasons,
but also $f(k+1) \equiv 1 \pmod k$ so we conclude $f(k+1) = k+1$.

\begin{remark*}
  Shankar Padmanabhan gives the following way
  to finish after verifying that $f(3) = 3$.
  Note that if
  \[ M = ( ( ( (3!)! )! )! \dots )! \]
  for any number of iterated factorials
  then $f(M) = M$.
  Thus for any $n$, we have
  \[ M-n \mid f(M) - f(n) = M - f(n) \implies M - n \mid n - f(n) \]
  and so taking $M$ large enough implies $f(n) = n$.
\end{remark*}
\pagebreak

\subsection{USAMO 2012/5, proposed by Titu Andreescu, Cosmin Pohoata}
\textsl{Available online at \url{https://aops.com/community/p2669960}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $P$ be a point in the plane of $\triangle ABC$,
and $\gamma$ a line through $P$.
Let $A'$, $B'$, $C'$ be the points where the
reflections of lines $PA$, $PB$, $PC$ with respect to $\gamma$
intersect lines $BC$, $CA$, $AB$ respectively.
Prove that $A'$, $B'$, $C'$ are collinear.
\end{mdframed}
We present three solutions.

\paragraph{First solution (complex numbers).}
Let $p=0$ and set $\gamma$ as the real line.
Then $A'$ is the intersection of $bc$ and $p\ol a$.
So, we get
\[ a' = \frac{\ol a(\ol b c - b \ol c)}{(\ol b - \ol c)\ol a-(b-c) a}. \]

\begin{center}
  \begin{asy}
    size(4cm);
    pair A = dir(110), B = dir(210), C = dir(330);
    Drawing("A", A, A);
    Drawing("B", B, dir(-90));
    Drawing("C", C, dir(-90));
    draw(A--B--C--cycle);
    pair P = Drawing("P", 0.1*dir(40), dir(-35));
    pair X1 = P + .5 * dir(10);
    pair X2 = P - .5 * dir(10);
    Drawing(Line(X1,X2), dashed, Arrows);
    pair T = 2*foot(A,X1,X2)-A;
    pair A1 = Drawing("A'", extension(P,T,B,C), dir(-40));
    draw(A--P--A1);
  \end{asy}
\end{center}

Note that
\[ \ol a' = \frac{a (b \ol c - \ol b c)}{(b-c) a - (\ol b - \ol c)\ol a}. \]
Thus it suffices to prove
\[ 0 = \det
\begin{bmatrix}
  \frac{\ol a(\ol b c-b \ol c)}{(\ol b - \ol c)\ol a - (b-c) a} & \frac{a (b \ol c - \ol b c)}{(b-c) a - (\ol b - \ol c) \ol a} & 1 \\
  \frac{\ol b(\ol c a-c \ol a)}{(\ol c - \ol a)\ol b - (c-a) b} & \frac{b (c \ol a - \ol c a)}{(c-a) b - (\ol c - \ol a) \ol b} & 1 \\
  \frac{\ol c(\ol a b-a \ol b)}{(\ol a - \ol b)\ol c - (a-b) c} & \frac{c (a \ol b - \ol a b)}{(a-b) c - (\ol a - \ol b)\ol c} & 1
\end{bmatrix}.
\]
This is equivalent to
\[ 0 = \det
\begin{bmatrix}
  \ol a(\ol b c -b \ol c) & a (\ol b c - b \ol c) & (\ol b - \ol c) \ol a - (b-c) a \\
  \ol b(\ol c a -c \ol a) & b (\ol c a - c \ol a) & (\ol c - \ol a) \ol b - (c-a) b \\
  \ol c(\ol a b -a \ol b) & c (\ol a b - a \ol b) & (\ol a - \ol b) \ol c - (a-b) c \\
\end{bmatrix}. \]
This determinant has the property that the rows sum to zero, and we're done.
\begin{remark*}
  Alternatively, if you don't notice that you could just blindly expand:
  \begin{align*}
    &\phantom{=} \sum_{\text{cyc}} ((\ol b - \ol c) \ol a - (b-c) a) \cdot
    - \det
    \begin{bmatrix}
      b & \ol b \\
      c & \ol c
    \end{bmatrix}
    \left( \ol c a - c \ol a \right)\left( \ol a b - a \ol b \right) \\
    &= (\ol b c - c \ol b)(\ol c a - c \ol a)(\ol a b - a \ol b)
    \sum_{\text{cyc}} \left( ab - ac + \ol c \ol a - \ol b \ol a \right) = 0.
  \end{align*}
\end{remark*}

\paragraph{Second solution (Desargues involution).}
We let $C'' = \ol{A'B'} \cap \ol{AB}$.
Consider complete quadrilateral $ABCA'B'C''C$.
We see that there is an involutive pairing $\tau$ at $P$
swapping $(PA,PA')$, $(PB,PB')$, $(PC,PC'')$.
From the first two, we see $\tau$ coincides with reflection
about $\ell$, hence conclude $C'' = C$.

\paragraph{Third solution (barycentric), by Catherine Xu.}
We will perform barycentric coordinates on the triangle $PCC'$,
with $P=(1,0,0)$, $C'=(0,1,0)$, and $C=(0,0,1)$.
Set $a = CC'$, $b = CP$, $c = C'P$ as usual.
Since $A$, $B$, $C'$ are collinear,
we will define $A = (p : k : q)$ and $B = (p : \ell : q)$.

\begin{claim*}
  Line $\gamma$ is the angle bisector of
  $\angle APA' $, $\angle BPB'$, and $\angle CPC'$.
\end{claim*}
\begin{proof}
  Since $A'P$ is the reflection of $AP$ across $\gamma$, etc.
\end{proof}

Thus $B'$ is the intersection of the isogonal of $B$ with respect to $\angle P$
with the line $CA$; that is,
\[ B' = \left( \frac pk \frac{b^2}{\ell}
  : \frac{b^2}{\ell} : \frac{c^2}{q} \right). \]
Analogously, $A'$ is the intersection of the isogonal of $A$ with respect to $\angle P$
with the line $CB$; that is,
\[ A' = \left( \frac{p}{\ell} \frac{b^2}{k}
    : \frac{b^2}{k} : \frac{c^2}{q} \right). \]
The ratio of the first to third coordinate in these two points
is both $b^2pq : c^2k\ell$, so it follows $A'$, $B'$, and $C'$ are collinear.

\begin{remark*}
  [Problem reference]
  The converse of this problem appears as problem 1052
  attributed S.\ V.\ Markelov in the book
  \emph{Geometriya: 9--11 Klassy: Ot Uchebnoy Zadachi k Tvorcheskoy, 1996},
  by I.\ F.\ Sharygin.
\end{remark*}
\pagebreak

\subsection{USAMO 2012/6, proposed by Gabriel Carroll}
\textsl{Available online at \url{https://aops.com/community/p2670037}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
For integer $n \ge 2$,
let $x_1$, $x_2$, \dots, $x_n$ be real numbers satisfying
\[ x_1 + x_2 +  \dots + x_n = 0
  \quad\text{and}\quad x_1^2 + x_2^2 + \dots + x_n^2 = 1. \]
For each subset $A\subseteq\{1, 2, \dots, n\}$, define $S_A=\sum_{i\in A} x_i$.
(If $A$ is the empty set, then $S_A=0$.)
Prove that for any positive number $\lambda$,
the number of sets $A$ satisfying $S_A\geq\lambda$ is at most $2^{n-3}/\lambda^2$.
For which choices of $x_1$, $x_2$, \dots, $x_n$, $\lambda$ does equality hold?
\end{mdframed}
Let $\eps_i$ be a coin flip of $0$ or $1$.
Then we have
\begin{align*} \mathbb E[S_A^2]
  &= \mathbb E\left[ \left( \sum \eps_i x_i \right)^2 \right]
  = \sum_i \mathbb E[\eps_i^2] x_i^2
  + \sum_{i < j} \mathbb E[\eps_i\eps_j] 2x_i x_j \\
  &= \half \sum x_i^2 + \half \sum x_i x_j
  = \half + \half \sum_{i<j} x_i x_j
  = \half + \half \left( -\half \right) = \frac 14.
\end{align*}
In other words, $\sum_A S_A^2 = 2^{n-2}$.
Since can always pair $A$ with its complement, we conclude
\[ \sum_{S_A > 0} S_A^2 = 2^{n-3}. \]

Equality holds iff $S_A \in \{\pm \lambda, 0\}$ for every $A$.
This occurs when $x_1 = 1/\sqrt2$, $x_2 = -1/\sqrt2$,
$x_3 = \dots = 0$ (or permutations), and $\lambda = 1/\sqrt2$.
\pagebreak


\end{document}
