\documentclass[11pt]{scrartcl}
\usepackage[sexy]{evan}
\ihead{\footnotesize\textbf{\thetitle}}
\ohead{\footnotesize\theauthor}
\begin{document}
\title{TSTST 2012 Solution Notes}
\subtitle{Lincoln, Nebraska}
\date{\today}
\maketitle
\begin{abstract}
This is a compilation of solutions
for the 2012 TSTST.
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
Determine all infinite strings of letters with the following properties:
\begin{enumerate}
\item[(a)] Each letter is either $T$ or $S$,
\item[(b)] If position $i$ and $j$ both have the letter $T$,
then position $i+j$ has the letter $S$,
\item[(c)] There are infinitely many integers $k$ such that position $2k-1$ has the $k$th $T$.
\end{enumerate}
\item %% Problem 2
Let $ABCD$ be a quadrilateral with $AC = BD$.
Diagonals $AC$ and $BD$ meet at $P$.
Let $\omega_1$ and $O_1$ denote the circumcircle and circumcenter of triangle $ABP$.
Let $\omega_2$ and $O_2$ denote the circumcircle and circumcenter of triangle $CDP$.
Segment $BC$ meets $\omega_1$ and $\omega_2$ again at $S$ and $T$
(other than $B$ and $C$), respectively.
Let $M$ and $N$ be the midpoints of minor arcs $\arc{SP}$ (not including $B$)
and $\arc{TP}$ (not including $C$).
Prove that $\ol{MN} \parallel \ol{O_1O_2}$.
\item %% Problem 3
Let $\NN$ be the set of positive integers.
Let $f \colon \NN \to \NN$ be a function satisfying the following two conditions:
\begin{enumerate}[(a)]
\ii $f(m)$ and $f(n)$ are relatively prime whenever $m$ and $n$ are relatively prime.
\ii $n \le f(n) \le n+2012$ for all $n$.
\end{enumerate}
Prove that for any natural number $n$ and any prime $p$,
if $p$ divides $f(n)$ then $p$ divides $n$.
\item %% Problem 4
In scalene triangle $ABC$, let the feet of the perpendiculars
from $A$ to $\ol{BC}$, $B$ to $\ol{CA}$, $C$ to $\ol{AB}$
be $A_1, B_1, C_1$, respectively.
Denote by $A_2$ the intersection of lines $BC$ and $B_1C_1$.
Define $B_2$ and $C_2$ analogously.
Let $D$, $E$, $F$ be the respective midpoints
of sides $\ol{BC}$, $\ol{CA}$, $\ol{AB}$.
Show that the perpendiculars from $D$ to $\ol{AA_2}$,
$E$ to $\ol{BB_2}$ and $F$ to $\ol{CC_2}$ are concurrent.
\item %% Problem 5
A rational number $x$ is given.
Prove that there exists a sequence
$x_0, x_1, x_2, \dots$ of rational numbers
with the following properties:
\begin{enumerate}[(a)]
\item $x_0=x$;
\item for every $n\ge1$, either $x_n = 2x_{n-1}$ or $x_n = 2x_{n-1} + \frac{1}{n}$;
\item $x_n$ is an integer for some $n$.
\end{enumerate}
\item %% Problem 6
Positive real numbers $x, y, z$ satisfy $xyz+xy+yz+zx = x+y+z+1$.
Prove that
\[ \frac{1}{3} \left( \sqrt{\frac{1+x^2}{1+x}}
+ \sqrt{\frac{1+y^2}{1+y}}
+ \sqrt{\frac{1+z^2}{1+z}} \right)
\le \left( \frac{x+y+z}{3} \right)^{5/8} . \]
\item %% Problem 7
Triangle $ABC$ is inscribed in circle $\Omega$.
The interior angle bisector of angle $A$ intersects side $BC$
and $\Omega$ at $D$ and $L$ (other than $A$), respectively.
Let $M$ be the midpoint of side $BC$.
The circumcircle of triangle $ADM$ intersects sides
$AB$ and $AC$ again at $Q$ and $P$ (other than $A$), respectively.
Let $N$ be the midpoint of segment $PQ$,
and let $H$ be the foot of the perpendicular from $L$ to line $ND$.
Prove that line $ML$ is tangent to the circumcircle of triangle $HMN$.
\item %% Problem 8
Let $n$ be a positive integer.
Consider a triangular array of nonnegative integers as follows:
\begin{center}
\begin{asy}
size(8cm);
defaultpen(fontsize(10pt));
label(scale(0.8)*"Row $1$:", (-6, 2.9));
label(scale(0.8)*"Row $2$:", (-6, 2.2));
label(scale(0.8)*"$\vdots$", (-6, 1.5));
label(scale(0.8)*"Row $n-1$:", (-6, 0.8));
label(scale(0.8)*"Row $n$:", (-6, 0.1));
label("$a_{0,1}$", (0,2.8));
label("$a_{0,2}$", (-1,2.1));
label("$a_{1,2}$", ( 1,2.1));
label(rotate(90)*"$\ddots$", (-2,1.5));
label("$\vdots$", ( 0,1.5));
label("$\ddots$", ( 2,1.5));
label("$a_{0,n-1}$", (-3,0.7));
label("$a_{1,n-1}$", (-1,0.7));
label("$\dots$", (1,0.7));
label("$a_{n-2,n-1}$", (3,0.7));
label("$a_{0,n}$", (-4,0));
label("$a_{1,n}$", (-2,0));
label("$a_{2,n}$", (-0,0));
label("$\dots$", (2,0));
label("$a_{n-1,n}$", (4,0));
\end{asy}
\end{center}
Call such a triangular array \textit{stable} if for every $0 \le i < j < k \le n$ we have
\[ a_{i,j} + a_{j,k} \le a_{i,k} \le a_{i,j} + a_{j,k} + 1. \]
For $s_1$, \dots, $s_n$ any nondecreasing sequence of nonnegative integers,
prove that there exists a unique stable triangular array such that
the sum of all of the entries in row $k$ is equal to $s_k$.
\item %% Problem 9
Given a set $S$ of $n$ variables, a binary operation $\times$ on $S$ is called
\textit{simple} if it satisfies $(x \times y) \times z = x \times (y \times z)$
for all $x,y,z \in S$ and $x \times y \in \{x,y\}$ for all $x,y \in S$.
Given a simple operation $\times$ on $S$, any string of elements in $S$
can be reduced to a single element, such as $xyz \to x \times (y \times z)$.
A string of variables in $S$ is called \textit{full}
if it contains each variable in $S$ at least once,
and two strings are \textit{equivalent} if they evaluate to the
same variable regardless of which simple $\times$ is chosen.
For example $xxx$, $xx$, and $x$ are equivalent, but these are only full if $n=1$.
Suppose $T$ is a set of full strings such that any full string is
equivalent to exactly one element of $T$. Determine the number of elements of $T$.
\end{enumerate}
\pagebreak
\section{Solutions to Day 1}
\subsection{TSTST 2012/1, proposed by Palmer Mebane}
\textsl{Available online at \url{https://aops.com/community/p2745864}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Determine all infinite strings of letters with the following properties:
\begin{enumerate}
\item[(a)] Each letter is either $T$ or $S$,
\item[(b)] If position $i$ and $j$ both have the letter $T$,
then position $i+j$ has the letter $S$,
\item[(c)] There are infinitely many integers $k$ such that position $2k-1$ has the $k$th $T$.
\end{enumerate}
\end{mdframed}
We wish to find all infinite sequences $a_1, a_2, \dots$
of positive integers satisfying the following properties:
\begin{enumerate}[(a)]
\item $a_1 < a_2 < a_3 < \dotsb$,
\item there are no positive integers $i$, $j$, $k$, not necessarily distinct, such that $a_i+a_j=a_k$,
\item there are infinitely many $k$ such that $a_k = 2k-1$.
\end{enumerate}
If $a_k=2k-1$ for some $k>1$, let $A_k=\{a_1,a_2,\dots,a_k\}$.
By (b) and symmetry, we have
\[ 2k-1
\ge \frac{|A_k-A_k|-1}{2}+|A_k|
\ge \frac{2|A_k|-2}{2}+|A_k| = 2k-1. \]
But in order for $|A_k-A_k|=2|A_k|-1$,
we must have $A_k$ an arithmetic progression,
whence $a_n=2n-1$ for all $n$ by taking $k$ arbitrarily large.
\pagebreak
\subsection{TSTST 2012/2}
\textsl{Available online at \url{https://aops.com/community/p2745851}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $ABCD$ be a quadrilateral with $AC = BD$.
Diagonals $AC$ and $BD$ meet at $P$.
Let $\omega_1$ and $O_1$ denote the circumcircle and circumcenter of triangle $ABP$.
Let $\omega_2$ and $O_2$ denote the circumcircle and circumcenter of triangle $CDP$.
Segment $BC$ meets $\omega_1$ and $\omega_2$ again at $S$ and $T$
(other than $B$ and $C$), respectively.
Let $M$ and $N$ be the midpoints of minor arcs $\arc{SP}$ (not including $B$)
and $\arc{TP}$ (not including $C$).
Prove that $\ol{MN} \parallel \ol{O_1O_2}$.
\end{mdframed}
Let $Q$ be the second intersection point of $\omega_1$, $\omega_2$.
Suffice to show $\ol{QP} \perp \ol{MN}$.
Now $Q$ is the center of a spiral \emph{congruence}
which sends $\ol{AC} \mapsto \ol{BD}$.
So $\triangle QAB$ and $\triangle QCD$ are similar isosceles.
Now, \[ \dang QPA = \dang QBA = \dang DCQ = \dang DPQ \]
and so $\ol{QP}$ is bisects $\angle BPC$.
\begin{center}
\begin{asy}
size(12cm);
pair Q = dir(80);
pair B = dir(190);
pair C = dir(350);
pair A = shift(Q)*rotate(-40)*shift(-Q)*B;
pair D = shift(Q)*rotate(40)*shift(-Q)*C;
pair P = extension(A, C, B, D);
draw(circumcircle(A, B, P));
draw(circumcircle(C, D, P));
filldraw(A--B--C--D--cycle, opacity(0.1)+lightcyan, lightcyan);
filldraw(Q--A--C--cycle, opacity(0.1)+lightgreen, lightblue);
filldraw(Q--B--D--cycle, opacity(0.1)+lightgreen, lightblue);
pair O_1 = circumcenter(A, B, P);
pair O_2 = circumcenter(C, D, P);
pair S = -B+2*foot(O_1, B, C);
pair T = -C+2*foot(O_2, B, C);
pair M = circumcenter(S, P, incenter(B, S, P));
pair N = circumcenter(T, P, incenter(C, T, P));
draw(M--N, blue);
draw(O_1--O_2, blue);
pair I = incenter(P, B, C);
draw(Q--I, blue);
draw(B--I--C, blue);
dot("$Q$", Q, dir(Q));
dot("$B$", B, dir(B));
dot("$C$", C, dir(C));
dot("$A$", A, dir(A));
dot("$D$", D, dir(D));
dot("$P$", P, dir(60));
dot("$O_1$", O_1, dir(150));
dot("$O_2$", O_2, dir(10));
dot("$S$", S, dir(-90));
dot("$T$", T, dir(-90));
dot("$M$", M, dir(100));
dot("$N$", N, dir(35));
dot("$I$", I, dir(45));
/* TSQ Source:
Q = dir 80
B = dir 190
C = dir 350
A = shift(Q)*rotate(-40)*shift(-Q)*B
D = shift(Q)*rotate(40)*shift(-Q)*C
P = extension A C B D
circumcircle A B P
circumcircle C D P
A--B--C--D--cycle 0.1 lightcyan / lightcyan
Q--A--C--cycle 0.1 lightgreen / lightblue
Q--B--D--cycle 0.1 lightgreen / lightblue
O_1 = circumcenter A B P
O_2 = circumcenter C D P
S = -B+2*foot O_1 B C
T = -C+2*foot O_2 B C
M = circumcenter S P incenter B S P
N = circumcenter T P incenter C T P
M--N blue
O_1--O_2 blue
I = incenter P B C
Q--I blue
B--I--C blue
*/
\end{asy}
\end{center}
Now, let $I = \ol{BM} \cap \ol{CN} \cap \ol{PQ}$
be the incenter of $\triangle PBC$.
Then $IM \cdot IB = IP \cdot IQ = IN \cdot IC$, so $BMNC$ is cyclic,
meaning $\ol{MN}$ is antiparallel to $\ol{BC}$ through $\angle BIC$.
Since $\ol{QPI}$ passes through the circumcenter of $\triangle BIC$,
it follows now $\ol{QPI} \perp \ol{MN}$ as desired.
\pagebreak
\subsection{TSTST 2012/3}
\textsl{Available online at \url{https://aops.com/community/p2745877}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $\NN$ be the set of positive integers.
Let $f \colon \NN \to \NN$ be a function satisfying the following two conditions:
\begin{enumerate}[(a)]
\ii $f(m)$ and $f(n)$ are relatively prime whenever $m$ and $n$ are relatively prime.
\ii $n \le f(n) \le n+2012$ for all $n$.
\end{enumerate}
Prove that for any natural number $n$ and any prime $p$,
if $p$ divides $f(n)$ then $p$ divides $n$.
\end{mdframed}
\paragraph{First short solution, by Jeffrey Kwan.}
Let $p_0$, $p_1$, $p_2$, \dots\ denote the
sequence of all prime numbers, in any order.
Pick \emph{any} primes $q_i$ such that
\[ q_0 \mid f(p_0), \quad q_1 \mid f(p_1), \quad
q_2 \mid f(p_2), \; \text{ etc}. \]
This is possible since each $f$ value above exceeds $1$.
Also, since by hypothesis the $f(p_i)$ are pairwise coprime,
the primes $q_i$ are all pairwise distinct.
\begin{claim*}
We must have $q_i = p_i$ for each $i$.
(Therefore, $f(p_i)$ is a power of $p_i$ for each $i$.)
\end{claim*}
\begin{proof}
Assume to the contrary that $q_0 \neq p_0$.
By changing labels if necessary, assume
$\min(p_1, p_2, \dots, p_{2012}) > 2012$.
Then by Chinese remainder theorem we can choose
an integer $m$ such that
\begin{align*}
m+i &\equiv 0 \pmod{q_i} \\
m &\not\equiv 0 \pmod{p_i}
\end{align*}
for $0 \le i \le 2012$.
But now $f(m)$ should be coprime to all $f(p_i)$,
ergo coprime to $q_0 q_1 \dots q_{2012}$,
violating $m \le f(m) \le m+2012$.
\end{proof}
All that is left to do is note that whenever $p \nmid n$,
we have $\gcd(f(p), f(n)) = 1$, hence $p \nmid f(n)$.
This is the contrapositive of the problem statement.
\paragraph{Second solution with a grid.}
Fix $n$ and $p$, and assume for contradiction $p \nmid n$.
\begin{claim*}
There exists a large integer $N$ with $f(N) = N$,
that also satisfies $N \equiv 1 \pmod n$ and $N \equiv 0 \pmod p$.
\end{claim*}
\begin{proof}
We'll need to pick both $N$ and an ancillary integer $M$.
Here is how: pick $2012 \cdot 2013$ distinct primes $q_{i,j} > n+p+2013$
for every $i=1,\dots,2012$ and $j=0,\dots,2012$,
and use it to fill in the following table:
\[
\begin{array}{c|cccc}
& N+1 & N+2 & \dots & N+2012 \\ \hline
M & q_{0,1} & q_{0,2} & \dots & q_{0,2012} \\
M+1 & q_{1,1} & q_{1,2} & \dots & q_{1,2012} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
M+2012 & q_{2012,1} & q_{2012,2} & \dots & q_{2012,2012}
\end{array}.
\]
By the Chinese Remainder Theorem, we can construct $N$
such that $N+1 \equiv 0 \pmod{q_{i,1}}$ for every $i$,
and similarly for $N+2$, and so on.
Moreover, we can also tack on the extra conditions
$N \equiv 0 \pmod p$ and $N \equiv 1 \pmod n$ we wanted.
Notice that $N$ cannot be divisible by any of the $q_{i,j}$'s,
since the $q_{i,j}$'s are greater than $2012$.
After we've chosen $N$, we can pick $M$ such that $M \equiv 0 \pmod{q_{0,j}}$ for every $j$,
and similarly $M+1 \equiv 0 \pmod{q_{1,j}}$, et cetera.
Moreover, we can tack on the condition $M \equiv 1 \pmod N$,
which ensures $\gcd(M,N) = 1$.
What does this do?
We claim that $f(N) = N$ now.
Indeed $f(M)$ and $f(N)$ are relatively prime; but look at the table!
The table tells us that $f(M)$ must have a common factor
with each of $N+1, \dots, N+2012$.
So the only possibility is that $f(N) = N$.
\end{proof}
Now we're basically done.
Since $N \equiv 1 \pmod n$, we have $\gcd(N,n) = 1$
and hence $1 = \gcd(f(N), f(n)) = \gcd(N, f(n))$.
But $p \mid N$ and $p \mid f(n)$, contradiction.
\pagebreak
\section{Solutions to Day 2}
\subsection{TSTST 2012/4}
\textsl{Available online at \url{https://aops.com/community/p2745854}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
In scalene triangle $ABC$, let the feet of the perpendiculars
from $A$ to $\ol{BC}$, $B$ to $\ol{CA}$, $C$ to $\ol{AB}$
be $A_1, B_1, C_1$, respectively.
Denote by $A_2$ the intersection of lines $BC$ and $B_1C_1$.
Define $B_2$ and $C_2$ analogously.
Let $D$, $E$, $F$ be the respective midpoints
of sides $\ol{BC}$, $\ol{CA}$, $\ol{AB}$.
Show that the perpendiculars from $D$ to $\ol{AA_2}$,
$E$ to $\ol{BB_2}$ and $F$ to $\ol{CC_2}$ are concurrent.
\end{mdframed}
We claim that they pass through the orthocenter $H$.
Indeed, consider the circle with diameter $\ol{BC}$,
which circumscribes quadrilateral $BCB_1C_1$ and has center $D$.
Then by Brokard theorem, $\ol{AA_2}$ is the polar of line $H$.
Thus $\ol{DH} \perp \ol{AA_2}$.
\pagebreak
\subsection{TSTST 2012/5}
\textsl{Available online at \url{https://aops.com/community/p2745867}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
A rational number $x$ is given.
Prove that there exists a sequence
$x_0, x_1, x_2, \dots$ of rational numbers
with the following properties:
\begin{enumerate}[(a)]
\item $x_0=x$;
\item for every $n\ge1$, either $x_n = 2x_{n-1}$ or $x_n = 2x_{n-1} + \frac{1}{n}$;
\item $x_n$ is an integer for some $n$.
\end{enumerate}
\end{mdframed}
Think of the sequence as a process over time.
We'll show that:
\begin{claim*}
At any given time $t$,
if the denominator of $x_t$ has some odd prime power $q = p^e$,
then we can delete a factor of $p$ from the denominator,
while only adding powers of two to the denominator.
\end{claim*}
(Thus we can just delete off all the odd primes one by one
and then double appropriately many times.)
\begin{proof}
The idea is to add only fractions of the form $(2^k q)\inv$.
Indeed, let $n$ be large,
and suppose $t < 2^{r+1} q < 2^{r+2} q < \dots < 2^{r+m} q < n$.
For some binary variables $\eps_i \in \{0,1\}$ we can have
\[ x_n = 2^{n-t} x_t
+ c_1 \cdot \frac{\eps_1}{q}
+ c_2 \cdot \frac{\eps_2}{q}
\dots
+ c_s \cdot \frac{\eps_m}{q}
\]
where $c_i$ is some power of $2$
(to be exact, $c_i = \frac{2^{n-2^{r+i}q}}{2^{r+1}}$,
but the exact value doesn't matter).
If $m$ is large enough the set $\{0,c_1\} + \{0,c_2\} + \dots + \{0, c_m\}$
spans everything modulo $p$.
(Actually, Cauchy-Davenport implies $m=p$ is enough,
but one can also just use Pigeonhole to notice some residue appears
more than $p$ times, for $m = O(p^2)$.)
Thus we can eliminate one factor of $p$ from the denominator, as desired.
\end{proof}
\pagebreak
\subsection{TSTST 2012/6, proposed by Sung-Yoon Kim}
\textsl{Available online at \url{https://aops.com/community/p2745861}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Positive real numbers $x, y, z$ satisfy $xyz+xy+yz+zx = x+y+z+1$.
Prove that
\[ \frac{1}{3} \left( \sqrt{\frac{1+x^2}{1+x}}
+ \sqrt{\frac{1+y^2}{1+y}}
+ \sqrt{\frac{1+z^2}{1+z}} \right)
\le \left( \frac{x+y+z}{3} \right)^{5/8} . \]
\end{mdframed}
The key is the identity
\begin{align*}
\frac{x^2+1}{x+1} &= \frac{(x^2+1)(y+1)(z+1)}{(x+1)(y+1)(z+1)} \\
&= \frac{x(xyz+xy+xz)+x^2+yz+y+z+1}{2(1+x+y+z)} \\
&= \frac{x(x+y+z+1-yz) + x^2+yz+y+z+1}{2(1+x+y+z)} \\
&= \frac{(x+y)(x+z) + x^2 + \left( x-xyz+y+z+1 \right)}{2(1+x+y+z)} \\
&= \frac{2(x+y)(x+z)}{2(1+x+y+z)} \\
&= \frac{(x+y)(x+z)}{1+x+y+z}.
\end{align*}
\begin{remark*}
The ``trick'' can be rephrased as
$(x^2+1)(y+1)(z+1) = 2(x+y)(x+z)$.
\end{remark*}
After this, straight Cauchy in the obvious way will do it
(reducing everything to an inequality in $s = x+y+z$).
One writes
\begin{align*}
\left( \sum_{\text{cyc}} \frac{\sqrt{(x+y)(x+z)}}{\sqrt{1+s}} \right)^2
&\le \frac{\left( \sum_{\text{cyc}} x+y \right)
\left( \sum_{\text{cyc}} x+z \right)}{1+s} \\
&= \frac{4s^2}{1+s}
\end{align*}
and so it suffices to check that $\frac{4s^2}{1+s} \le 9(s/3)^{5/4}$,
which is true because
\[ (s/3)^5 \cdot 9^4 \cdot (1+s)^4 - (4s^2)^4
= s^5 (s-3)^2 (27s^2 + 14s + 3) \ge 0. \]
\pagebreak
\section{Solutions to Day 3}
\subsection{TSTST 2012/7}
\textsl{Available online at \url{https://aops.com/community/p2745857}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Triangle $ABC$ is inscribed in circle $\Omega$.
The interior angle bisector of angle $A$ intersects side $BC$
and $\Omega$ at $D$ and $L$ (other than $A$), respectively.
Let $M$ be the midpoint of side $BC$.
The circumcircle of triangle $ADM$ intersects sides
$AB$ and $AC$ again at $Q$ and $P$ (other than $A$), respectively.
Let $N$ be the midpoint of segment $PQ$,
and let $H$ be the foot of the perpendicular from $L$ to line $ND$.
Prove that line $ML$ is tangent to the circumcircle of triangle $HMN$.
\end{mdframed}
By angle chasing, equivalent to show $\ol{MN} \parallel \ol{AD}$,
so discard the point $H$.
We now present a three solutions.
\paragraph{First solution using vectors.}
We first contend that:
\begin{claim*}
We have $QB = PC$.
\end{claim*}
\begin{proof}
Power of a Point gives $BM \cdot BD = AB \cdot QB$.
Then use the angle bisector theorem.
\end{proof}
Now notice that the vector
\[ \overrightarrow{MN}
= \half \left( \overrightarrow{BQ} + \overrightarrow{CP} \right) \]
which must be parallel to the angle bisector
since $\overrightarrow{BQ}$ and $\overrightarrow{CP}$
have the same magnitude.
\paragraph{Second solution using spiral similarity.}
let $X$ be the arc midpoint of $BAC$.
Then $ADMX$ is cyclic with diameter $\ol{AM}$,
and hence $X$ is the Miquel point $X$ of $QBPC$
is the midpoint of arc $BAC$.
Moreover $\ol{XND}$ collinear (as $XP=XQ$, $DP=DQ$) on $(APQ)$.
\begin{center}
\begin{asy}
pair A = dir(130);
pair B = dir(210);
pair C = dir(330);
draw(A--B--C--cycle, lightblue);
filldraw(unitcircle, opacity(0.1)+lightblue, blue);
pair L = dir(-90);
pair D = extension(A, L, B, C);
pair M = midpoint(B--C);
path w = circumcircle(A,D,M);
draw(w, dashed+orange);
pair Q = OP(A--B, w);
pair P = IP(A--C, w);
pair N = midpoint(P--Q);
pair H = foot(L, N, D);
pair X = dir(90);
draw(A--L, blue);
draw(circumcircle(H, D, M), lightblue+dotted);
draw(P--Q, blue);
draw(Q--X--C, blue);
draw(N--H, lightblue+dotted);
draw(M--L, lightblue+dotted);
filldraw(X--N--M--cycle, opacity(0.1)+lightgreen, heavygreen);
filldraw(X--P--C--cycle, opacity(0.1)+lightgreen, heavygreen);
filldraw(X--Q--B--cycle, opacity(0.1)+lightgreen, heavygreen);
dot("$A$", A, dir(A));
dot("$B$", B, dir(B));
dot("$C$", C, dir(C));
dot("$L$", L, dir(L));
dot("$D$", D, dir(D));
dot("$M$", M, dir(-90));
dot("$Q$", Q, dir(Q));
dot("$P$", P, dir(10));
dot("$N$", N, dir(130));
dot("$H$", H, dir(H));
dot("$X$", X, dir(X));
/* TSQ Source:
A = dir 130
B = dir 210
C = dir 330
A--B--C--cycle lightblue
unitcircle 0.1 lightblue / blue
L = dir -90
D = extension A L B C
M = midpoint B--C R-90
!path w = circumcircle(A,D,M);
w dashed orange
Q = OP A--B w
P = IP A--C w R10
N = midpoint P--Q R130
H = foot L N D
X = dir 90
A--L blue
circumcircle H D M lightblue dotted
P--Q blue
Q--X--C blue
N--H lightblue dotted
M--L lightblue dotted
X--N--M--cycle 0.1 lightgreen / heavygreen
X--P--C--cycle 0.1 lightgreen / heavygreen
X--Q--B--cycle 0.1 lightgreen / heavygreen
*/
\end{asy}
\end{center}
Then $\triangle XNM \sim \triangle XPC$ spirally, and
\[ \dang XMN = \dang XCP = \dang XCA = \dang XLA \]
thus done.
\paragraph{Third solution using barycentrics (mine).}
Once reduced to $\ol{MN} \parallel \ol{AB}$,
straight bary will also work.
By power of a point one obtains
\begin{align*}
P &= \left( a^2 : 0 : 2b(b+c)-a^2 \right) \\
Q &= \left( a^2 : 2c(b+c)-a^2 : 0 \right) \\
\implies N &= \left( a^2(b+c) : 2bc(b+c) - ba^2 : 2bc(b+c)-ca^2 \right).
\end{align*}
Now the point at infinity along $\ol{AD}$ is $(-(b+c):b:c)$
and so we need only verify
\[
\det \begin{bmatrix}
a^2(b+c) & 2bc(b+c) - ba^2 & 2bc(b+c)-ca^2 \\
0 & 1 & 1 \\
-(b+c) & b & c
\end{bmatrix}
= 0
\]
which follows since the first row is $-a^2$
times the third row plus $2bc(b+c)$ times the second row.
\pagebreak
\subsection{TSTST 2012/8, proposed by Palmer Mebane}
\textsl{Available online at \url{https://aops.com/community/p2745872}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $n$ be a positive integer.
Consider a triangular array of nonnegative integers as follows:
\begin{center}
\begin{asy}
size(8cm);
defaultpen(fontsize(10pt));
label(scale(0.8)*"Row $1$:", (-6, 2.9));
label(scale(0.8)*"Row $2$:", (-6, 2.2));
label(scale(0.8)*"$\vdots$", (-6, 1.5));
label(scale(0.8)*"Row $n-1$:", (-6, 0.8));
label(scale(0.8)*"Row $n$:", (-6, 0.1));
label("$a_{0,1}$", (0,2.8));
label("$a_{0,2}$", (-1,2.1));
label("$a_{1,2}$", ( 1,2.1));
label(rotate(90)*"$\ddots$", (-2,1.5));
label("$\vdots$", ( 0,1.5));
label("$\ddots$", ( 2,1.5));
label("$a_{0,n-1}$", (-3,0.7));
label("$a_{1,n-1}$", (-1,0.7));
label("$\dots$", (1,0.7));
label("$a_{n-2,n-1}$", (3,0.7));
label("$a_{0,n}$", (-4,0));
label("$a_{1,n}$", (-2,0));
label("$a_{2,n}$", (-0,0));
label("$\dots$", (2,0));
label("$a_{n-1,n}$", (4,0));
\end{asy}
\end{center}
Call such a triangular array \textit{stable} if for every $0 \le i < j < k \le n$ we have
\[ a_{i,j} + a_{j,k} \le a_{i,k} \le a_{i,j} + a_{j,k} + 1. \]
For $s_1$, \dots, $s_n$ any nondecreasing sequence of nonnegative integers,
prove that there exists a unique stable triangular array such that
the sum of all of the entries in row $k$ is equal to $s_k$.
\end{mdframed}
Firstly, here are illustrative examples showing the arrays
for $(s_1, s_2, s_3, s_4) = (2, 5, 9, x)$ where $9 \le x \le 14$.
(The array has been left justified.)
\[
\begin{bmatrix}
2 & \swarrow \\
4 & 1 & \swarrow \\
5 & 3 & 1 & \swarrow \\
5 & 3 & 1 & 0
\end{bmatrix}
\begin{bmatrix}
2 & \swarrow \\
4 & 1 & \swarrow \\
5 & 3 & 1 & \swarrow \\
\mathbf{\color{red} 6} & 3 & 1 & 0
\end{bmatrix}
\begin{bmatrix}
2 & \swarrow \\
4 & 1 & \swarrow \\
5 & 3 & 1 & \swarrow \\
6 & 3 & \mathbf{\color{red} 2} & 0
\end{bmatrix}
\]
\[
\begin{bmatrix}
2 & \swarrow \\
4 & 1 & \swarrow \\
5 & 3 & 1 & \swarrow \\
6 & \mathbf{\color{red} 4} & 2 & 0
\end{bmatrix}
\begin{bmatrix}
2 & \swarrow \\
4 & 1 & \swarrow \\
5 & 3 & 1 & \swarrow \\
6 & 4 & 2 & \mathbf{\color{red} 1}
\end{bmatrix}
\begin{bmatrix}
2 & \swarrow \\
4 & 1 & \swarrow \\
5 & 3 & 1 & \swarrow \\
\mathbf{\color{red} 7} & 4 & 2 & 1
\end{bmatrix}
\]
Now we outline the proof.
By induction on $n$, we may assume the first $n-1$ rows are fixed.
Now, let $N = s_n$ vary.
Now, we prove our result by (another) induction on $N \ge s_{n-1}$.
The base case $N = s_{n-1}$ is done by copying
the $n-1$st row and adding a zero at the end.
This is also unique,
since $a_{i,n} \ge a_{i-1,n} + a_{n-1,n}$ for all $i=0, \dots, n-2$,
whence $\sum a_{i,n} \ge s_{n-1}$ follows.
Now the inductive step is based on the following lemma,
which illustrates the idea of a ``unique increasable entry''.
\begin{lemma*}
Fix a stable array
Construct a tournament on the $n$ entries
of the last row as follows: for $i < j$,
\begin{itemize}
\ii $a_{i,n} \to a_{j,n}$
if $a_{i,n} = a_{i,j} + a_{j,n}$, and
\ii $a_{j,n} \to a_{i,n}$
if $a_{i,n} = a_{i,j} + a_{j,n} + 1$.
\end{itemize}
Then this tournament is transitive.
Also, except for $N = s_{n-1}$, a $0$ entry is never a source.
\end{lemma*}
Intuitively, $a_{i,n} \to a_{j,n}$
if $a_{i,n}$ blocks $a_{j,n}$ from increasing.
For instance, in the example
\[
\begin{bmatrix}
2 & \swarrow \\
4 & 1 & \swarrow \\
5 & 3 & 1 & \swarrow \\
\mathbf 6 & 3 & 1 & 0
\end{bmatrix}
\]
the tournament is $1 \to 3 \to 0 \to 6$.
\begin{proof}
[Proof of lemma]
Let $0 \le i < j < k < n$ be indices.
Let $x = a_{i,n}$, $y = a_{j,n}$, $z = a_{k,n}$,
$p = a_{i,j}$, $s = a_{i,k}$, $q = a_{j,k}$. Picture:
\[
\begin{bmatrix}
p & \swarrow \\
s & q & \swarrow \\
x & y & z
\end{bmatrix}
\]
If $x \to y \to z \to x$ happens, that means
$x = y+p$, $y = q+z$, $x = s+z+1$,
which gives $s=p+q-1$, contradiction.
Similarly if $x \leftarrow y \leftarrow z \leftarrow x$ then
$x = y+p+1$, $y = q+z+1$, $x = s+z$,
which gives $s=p+q+2$, also contradiction.
\end{proof}
Now this allows us to perform our induction.
Indeed, to show existence from $N$ to $N+1$
we take a source of the tournament above and increase it.
Conversely, to show uniqueness for $N$,
note that we can take the (nonzero) sink of the tournament and decrement it,
which gives $N-1$; our uniqueness inductive hypothesis now finishes.
\begin{remark*}
Colin Tang found a nice proof of uniqueness:
\[
s_k + \sum_{i=1}^{k-1} a_{0,i} \le ka_{0,k}
\le s_k + \sum_{i=1} \left( a_{0,i} + 1 \right)
\]
and similarly for other entries.
\end{remark*}
\pagebreak
\subsection{TSTST 2012/9, proposed by John Berman}
\textsl{Available online at \url{https://aops.com/community/p2745874}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Given a set $S$ of $n$ variables, a binary operation $\times$ on $S$ is called
\textit{simple} if it satisfies $(x \times y) \times z = x \times (y \times z)$
for all $x,y,z \in S$ and $x \times y \in \{x,y\}$ for all $x,y \in S$.
Given a simple operation $\times$ on $S$, any string of elements in $S$
can be reduced to a single element, such as $xyz \to x \times (y \times z)$.
A string of variables in $S$ is called \textit{full}
if it contains each variable in $S$ at least once,
and two strings are \textit{equivalent} if they evaluate to the
same variable regardless of which simple $\times$ is chosen.
For example $xxx$, $xx$, and $x$ are equivalent, but these are only full if $n=1$.
Suppose $T$ is a set of full strings such that any full string is
equivalent to exactly one element of $T$. Determine the number of elements of $T$.
\end{mdframed}
The answer is $(n!)^2$.
In fact it is possible to essentially find all $\times$:
one assigns a real number to each variable in $S$.
Then $x \times y$ takes the larger of $\{x,y\}$,
and in the event of a tie picks either ``left'' or ``right'',
where the choice of side is fixed among elements of each size.
\paragraph{First solution (Steven Hao).}
The main trick is the two lemmas, which are not hard to show
(and are motivated by our conjecture).
\begin{align*}
xx &= x \\
xyxzx &= xyzx.
\end{align*}
Consequently, define a \textbf{double rainbow}
to be the concatenation of two full strings of length $n$,
of which there are $(n!)^2$.
We claim that these form equivalence classes for $T$.
To see that any string $s$ is equivalent to a double rainbow,
note that $s = ss$, and hence using the second identity above
repeatedly lets us reduce $ss$ to a double rainbow.
To see two distinct double rainbows $R_1$ and $R_2$ aren't equivalent,
one can use the construction mentioned in the beginning.
Specifically, take two variables $a$ and $b$ which do not
appear in the same order in $R_1$ and $R_2$.
Then it's not hard to see that $abab$, $abba$, $baab$, $baba$
are pairwise non-equivalent by choosing ``left'' or ``right'' appropriately.
Now construct $\times$ on the whole set
by having $a$ and $b$ be the largest variables,
so the rest of the variables don't matter in the evaluation of the string.
\paragraph{Second solution outline (Ankan Bhattacharya).}
We outline a proof of the characterization claimed earlier,
which will also give the answer $(n!)^2$.
We say $a \sim b$ if $ab \neq ba$.
Also, say $a > b$ if $ab = ba = a$.
The following are proved by finite casework,
using the fact that $\{ab, bc, ca\}$ always has exactly
two distinct elements for any different $a$, $b$, $c$.
\begin{itemize}
\ii If $a > b$ and $b > c$ then $a > c$.
\ii If $a \sim b$ and $b \sim c$
then $ab = a$ if and only if $bc = b$.
\ii If $a \sim b$ and $b \sim c$ then $a \sim c$.
\ii If $a \sim b$ and $a > c$ then $b > c$.
\ii If $a \sim b$ and $c > a$ then $c > b$.
\end{itemize}
This gives us the total ordering on the elements
and the equivalence classes by $\sim$.
In this we way can check the claimed operations are the only ones.
We can then (as in the first solution) verify that every full string
is equivalent to a unique double rainbow --- but this
time we prove it by simply considering all possible $\times$,
because we have classified them all.
\pagebreak
\end{document}