\documentclass[11pt]{scrartcl}
\usepackage[sexy]{evan}
\ihead{\footnotesize\textbf{\thetitle}}
\ohead{\footnotesize\theauthor}
\begin{document}

\title{TSTST 2014 Solution Notes}
\subtitle{Lincoln, Nebraska}
\date{\today}

\maketitle
\begin{abstract}
This is a compilation of solutions
for the 2014 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
Let $\leftarrow$ denote the left arrow key on a standard keyboard. If
one opens a text editor and types the keys
``ab$\leftarrow$ cd $\leftarrow \leftarrow$ e $\leftarrow \leftarrow$ f'',
the result is ``faecdb''.
We say that a string $B$ is \emph{reachable} from a string $A$ if
it is possible to insert some amount of $\leftarrow$'s in $A$,
such that typing the resulting characters produces $B$.
So, our example shows that ``faecdb'' is reachable from ``abcdef''.

Prove that for any two strings $A$ and $B$,
$A$ is reachable from $B$ if and only if $B$ is reachable from $A$.

\item %% Problem 2
Consider a convex pentagon circumscribed about a circle.
We name the lines that connect vertices of the pentagon with
the opposite points of tangency with the circle \emph{gergonnians}.
\begin{enumerate}
  \ii[(a)] Prove that if four gergonnians are concurrent,
    then all five of them are concurrent.
  \ii[(b)] Prove that if there is a triple of gergonnians
    that are concurrent, then there is another triple
    of gergonnians that are concurrent.
\end{enumerate}

\item %% Problem 3
Find all polynomials $P(x)$ with real coefficients that satisfy
\[ P(x \sqrt 2) = P(x + \sqrt{1-x^2}) \]
for all real numbers $x$ with $\lvert x \rvert \le 1$.

\item %% Problem 4
Let $P(x)$ and $Q(x)$ be arbitrary polynomials with real coefficients,
with $P \neq 0$, and let $d = \deg P$.
Prove that there exist polynomials $A(x)$ and $B(x)$,
not both zero, such that $\max \{ \deg A, \deg B \} \le d/2$
and $P(x) \mid A(x) + Q(x) \cdot B(x)$.

\item %% Problem 5
Find the maximum number $E$ such that the following holds:
there is an edge-colored graph with $60$ vertices and $E$ edges,
with each edge colored either red or blue, such that in that coloring,
there is no monochromatic cycles of length $3$
and no monochromatic cycles of length $5$.

\item %% Problem 6
Suppose we have distinct positive integers $a$, $b$, $c$, $d$
and an odd prime $p$ not dividing any of them,
and an integer $M$ such that if one considers the infinite sequence
\begin{align*}
  ca &- db \\
  ca^2 &- db^2 \\
  ca^3 &- db^3 \\
  ca^4 &- db^4 \\
  &\vdots
\end{align*}
and looks at the highest power of $p$ that divides each of them,
these powers are not all zero, and are all at most $M$.
Prove that there exists some $T$ (which may depend on $a,b,c,d,p,M$)
such that whenever $p$ divides an element of this sequence,
the maximum power of $p$ that divides that element is exactly $p^T$.

\end{enumerate}
\pagebreak

\section{Solutions to Day 1}
\subsection{TSTST 2014/1}
\textsl{Available online at \url{https://aops.com/community/p3549404}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $\leftarrow$ denote the left arrow key on a standard keyboard. If
one opens a text editor and types the keys
``ab$\leftarrow$ cd $\leftarrow \leftarrow$ e $\leftarrow \leftarrow$ f'',
the result is ``faecdb''.
We say that a string $B$ is \emph{reachable} from a string $A$ if
it is possible to insert some amount of $\leftarrow$'s in $A$,
such that typing the resulting characters produces $B$.
So, our example shows that ``faecdb'' is reachable from ``abcdef''.

Prove that for any two strings $A$ and $B$,
$A$ is reachable from $B$ if and only if $B$ is reachable from $A$.
\end{mdframed}
Obviously $A$ and $B$ should have the
same multiset of characters, and we focus only on that situation.

\begin{claim*}
  If $A = 123 \dots n$
  and $B = \sigma(1) \sigma(2) \dots \sigma(n)$
  is a permutation of $A$,
  then $B$ is reachable if and only if
  it is \textbf{213-avoiding},
  i.e.\ there are no indices $i < j < k$
  such that $\sigma(j) < \sigma(i) < \sigma(k)$.
\end{claim*}
\begin{proof}
  This is clearly necessary.
  To see its sufficient, one can just type $B$ inductively:
  after typing $k$, the only way to get stuck is if
  $k+1$ is to the right of $k$ and there is some character in the way;
  this gives a 213 pattern.
\end{proof}

\begin{claim*}
  A permutation $\sigma$ on $\{1, \dots, n\}$
  is 213-avoiding if and only if the inverse $\sigma\inv$ is.
\end{claim*}
\begin{proof}
  Suppose $i < j < k$ and $\sigma(j) < \sigma(i) < \sigma(k)$.
  Let $i' = \sigma(j)$, $j' = \sigma(i)$, $k' = \sigma(k)$;
  then $i' < j' < k'$ and $\sigma\inv(j') < \sigma\inv(i') < \sigma\inv(k')$.
\end{proof}

This essentially finishes the problem.
Suppose $B$ is reachable from $A$.
By using the typing pattern,
we get some permutation $\sigma \colon \{1, \dots, n\}$
such that the $i$th character of $A$
is the $\sigma(i)$th character of $B$,
and which is 213-avoiding by the claim.
(The permutation is unique if $A$ has all distinct characters,
but there could be multiple if $A$ has repeated ones.)
Then $\sigma\inv$ is 213-avoiding too
and gives us a way to change $B$ into $A$.
\pagebreak

\subsection{TSTST 2014/2}
\textsl{Available online at \url{https://aops.com/community/p3549405}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Consider a convex pentagon circumscribed about a circle.
We name the lines that connect vertices of the pentagon with
the opposite points of tangency with the circle \emph{gergonnians}.
\begin{enumerate}
  \ii[(a)] Prove that if four gergonnians are concurrent,
    then all five of them are concurrent.
  \ii[(b)] Prove that if there is a triple of gergonnians
    that are concurrent, then there is another triple
    of gergonnians that are concurrent.
\end{enumerate}
\end{mdframed}
This problem is insta-killed by taking a homography
sending the concurrency point (in either part)
to the center of the circle while fixing the incircle.
Alternatively, one may send any four of the tangency points to a rectangle.

Here are the details.
Let $ABCDE$ be a pentagon with gergonnians
$\ol{AV}$, $\ol{BW}$, $\ol{CX}$, $\ol{DY}$, $\ol{EZ}$.
We prove the following lemma, which
(up to a suitable permutation of point names)
solves both parts (a) and (b).
\begin{lemma*}
  The gergonnians $\ol{AV}$, $\ol{CX}$, $\ol{DY}$
  are concurrent if and only if the gergonnians
  $\ol{AV}$, $\ol{BW}$, $\ol{EZ}$ are concurrent.
\end{lemma*}
\begin{proof}
  We prove the first set implies the second
  (the converse direction being identical).
  Suppose $\ol{AV}$, $\ol{CX}$, $\ol{DY}$ intersect at $P$
  and take a homography fixing the circle
  and moving $P$ to its center.

  \begin{center}
  \begin{asy}
  size(7cm);
  pair Y = dir(115);
  pair X = -conj(Y);
  pair V = dir(270);
  pair Z = X*X/V;
  pair W = Y*Y/V;

  pair A = 2*X*Y/(X+Y);
  pair B = 2*Y*Z/(Y+Z);
  pair C = 2*Z*V/(Z+V);
  pair D = 2*V*W/(V+W);
  pair E = 2*W*X/(W+X);

  filldraw(A--B--C--D--E--cycle, opacity(0.1)+lightblue, blue);
  filldraw(unitcircle, opacity(0.1)+lightcyan, blue);

  pair P = origin;
  draw(C--X, red);
  draw(D--Y, red);
  draw(A--V, red);

  draw(B--W, heavygreen+dashed);
  draw(E--Z, heavygreen+dashed);

  dot("$Y$", Y, dir(Y));
  dot("$X$", X, dir(X));
  dot("$V$", V, dir(V));
  dot("$Z$", Z, dir(Z));
  dot("$W$", W, dir(W));
  dot("$A$", A, dir(A));
  dot("$B$", B, dir(B));
  dot("$C$", C, dir(C));
  dot("$D$", D, dir(D));
  dot("$E$", E, dir(E));
  dot("$P$", P, dir(0));

  /* Source generated by TSQ */
  \end{asy}
  \end{center}

  Then $X$ and $Y$ are symmetric around $\ol{APV}$
  by hypothesis.
  Since $D = \ol{VV} \cap \ol{PY}$, $C = \ol{VV} \cap \ol{PX}$,
  it follows that $C$ and $D$,
  and hence $Z$ and $W$,
  are also symmetric around $\ol{APV}$.
  Consequently $B$ and $E$ are symmetric too.
  So $\ol{BW}$ and $\ol{EZ}$ meet on $\ol{AV}$.
\end{proof}
\pagebreak

\subsection{TSTST 2014/3}
\textsl{Available online at \url{https://aops.com/community/p3549407}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Find all polynomials $P(x)$ with real coefficients that satisfy
\[ P(x \sqrt 2) = P(x + \sqrt{1-x^2}) \]
for all real numbers $x$ with $\lvert x \rvert \le 1$.
\end{mdframed}
The answer is any polynomial of the form
$P(x) = f(U(x/\sqrt2))$,
where $f \in \RR[x]$
and $U$ is the unique polynomial satisfying
$U(\cos\theta) = \cos(8\theta)$.

Let $Q(x) = P(x \sqrt 2)$,
then the condition reads
\[
  Q(\cos\theta) = Q\left( \frac{1}{\sqrt2}(\cos\theta+\sin\theta) \right)
  = Q(\cos(\theta-45\dg))
  \qquad \forall \; 0 \le \theta \le 180\dg.
\]
We call a polynomial \emph{good} if it satisfies this
functional equation.
\begin{lemma*}
  The minimal (by degree) good nonconstant
  polynomial is $U$.
\end{lemma*}
\begin{proof}
  Since $U$ works, it suffices to show
  that $\deg Q \ge 8$.
  Note that:
  \begin{align*}
    Q(\cos136\dg) &= Q(\cos91\dg)
    = Q(\cos46\dg) = Q(\cos1\dg) = Q(\cos-44\dg) \\
    &= Q(\cos44\dg) = Q(\cos89\dg) = Q(\cos134\dg) = Q(\cos179\dg).
  \end{align*}
  Hence $Q$ is equal at eight distinct values
  (not nine since $\cos -44\dg = \cos44\dg$ is repeated),
  so $\deg Q \ge 8$ (unless $Q$ is constant).
\end{proof}

Now, we claim $Q(x) \equiv f(U(x))$ for some $f \in \RR[x]$.
Indeed, if $Q$ is good,
then by minimality the quotient $Q \bmod U$ must be constant,
so $Q(x) = \wt Q(x) \cdot U(x) + c$ for some constant $c$,
but then $\wt Q(x)$ is good too and we finish iteratively.
\pagebreak

\section{Solutions to Day 2}
\subsection{TSTST 2014/4}
\textsl{Available online at \url{https://aops.com/community/p3549409}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Let $P(x)$ and $Q(x)$ be arbitrary polynomials with real coefficients,
with $P \neq 0$, and let $d = \deg P$.
Prove that there exist polynomials $A(x)$ and $B(x)$,
not both zero, such that $\max \{ \deg A, \deg B \} \le d/2$
and $P(x) \mid A(x) + Q(x) \cdot B(x)$.
\end{mdframed}
Let $V$ be the vector space of real polynomials with degree at most $d/2$.
Consider maps of linear spaces
\begin{align*}
  V^{\oplus 2} &\to \RR[x] / (P(x)) \\
  \text{by} \qquad (A,B) &\mapsto A+QB \pmod P.
\end{align*}
The domain has dimension
\[ 2 \left( \left\lfloor d/2 \right\rfloor + 1 \right) \]
while the codomain has dimension $d$.
For dimension reasons it has nontrivial kernel.
\pagebreak

\subsection{TSTST 2014/5}
\textsl{Available online at \url{https://aops.com/community/p3549412}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Find the maximum number $E$ such that the following holds:
there is an edge-colored graph with $60$ vertices and $E$ edges,
with each edge colored either red or blue, such that in that coloring,
there is no monochromatic cycles of length $3$
and no monochromatic cycles of length $5$.
\end{mdframed}
The answer is $E = 30^2 + 2 \cdot 15^2 = 6 \cdot 15^2 = 1350$.

First, we prove $E \le 1350$.  Observe that:
\begin{claim*}
  $G$ contains no $K_5$.
\end{claim*}
\begin{proof}
  It's a standard fact that the only triangle-free two-coloring
  of the edges of $K_5$ is the union of two monochromatic $C_5$'s.
\end{proof}
Hence by Tur\'{a}n theorem we have $E \le \binom42 \cdot 15^2 = 1350$.

To show this is achievable, take a red $K_{30,30}$,
and on each side draw a blue $K_{15,15}$.
This graph has no monochromatic odd cycles at all as desired.
\pagebreak

\subsection{TSTST 2014/6}
\textsl{Available online at \url{https://aops.com/community/p3549417}.}
\begin{mdframed}[style=mdpurplebox,frametitle={Problem statement}]
Suppose we have distinct positive integers $a$, $b$, $c$, $d$
and an odd prime $p$ not dividing any of them,
and an integer $M$ such that if one considers the infinite sequence
\begin{align*}
  ca &- db \\
  ca^2 &- db^2 \\
  ca^3 &- db^3 \\
  ca^4 &- db^4 \\
  &\vdots
\end{align*}
and looks at the highest power of $p$ that divides each of them,
these powers are not all zero, and are all at most $M$.
Prove that there exists some $T$ (which may depend on $a,b,c,d,p,M$)
such that whenever $p$ divides an element of this sequence,
the maximum power of $p$ that divides that element is exactly $p^T$.
\end{mdframed}
By orders, the indices of terms divisible by $p$
is an arithmetic subsequence of $\NN$:
say they are $\kappa$, $\kappa + \lambda$, $\kappa + 2\lambda$, \dots,
where $\lambda$ is the order of $a/b$.
That means we want
\[ \nu_p \left( c a^{\kappa + n\lambda} - d b^{\kappa + n \lambda} \right)
  = \nu_p \left(
    \left( \frac{a^\lambda}{b^\lambda} \right)^n
    - \frac{d a^\kappa}{c b^{\kappa}} \right)
\]
to be constant.
Thus, we have reduced the problem to the following proposition:
\begin{proposition*}
  Let $p$ be an odd prime.
  Let $x, y \in \QQ_{>0}$ such that $x \equiv y \equiv 1 \pmod p$.
  If the sequence $\nu_p\left( x^n - y \right)$ of positive integers
  is nonconstant, then it is unbounded.
\end{proposition*}

For this it would be sufficient to prove the following claim.
\begin{claim*}
  Let $p$ be an odd prime.
  Let $x, y \in \QQ_{>0}$ such that $x \equiv y \equiv 1 \pmod p$.
  Suppose $m$ and $n$ are positive integers such that
  \[ d = \nu_p(x^n-y) < \nu_p(x^m-y) = e. \]
  Then there exists $\ell$ such that $\nu_p(x^\ell - y) \ge e + 1$.
\end{claim*}
\begin{proof}
First, note that
$\nu_p(x^m - x^n) = \nu_p\left( (x^m-y) - (x^n-y) \right) = d$
and so by exponent lifting we can find \emph{some} $k$ such that
\[ \nu_p(x^k-1) = e \]
namely $k = p^{e-d}|m-n|$.
(In fact, one could also choose more carefully
$k = p^{e-d} \cdot \gcd(m-n, p^\infty)$,
so that $k$ is a power of $p$.)

Suppose we set $x^k = p^e u + 1$ and $x^m = p^e v + y$
where $u,v \in \QQ$ aren't divisible by $p$.
Now for any integer $1 \le r \le p-1$ we consider
\begin{align*}
  x^{kr+m}-y &= (p^e u + 1)^r \cdot (p^e v + y) - y \\
  &= p^e \left( v + yu \cdot r \right) + p^{2e} \left( \dots \right).
\end{align*}
By selecting $r$ with $r \equiv -v/u \pmod p$,
we ensure $p^{e+1} \mid x^{kr+m} - y$,
hence $\ell = kr+m$ is as desired.
\end{proof}

\begin{remark*}
  One way to motivate the proof of the claim is as follows.
  Suppose we are given $\nu_p(x^m-y) = e$,
  and we wish to find $\ell$ such that $\nu_p(x^\ell - y) > e$.
  Then, it is necessary (albeit insufficient) that
  \[ x^{\ell-m} \equiv 1 \pmod{p^e} \text{ but }
    x^{\ell-m} \not\equiv 1 \pmod{p^{e+1}}. \]
  In particular, we need $\nu_p(x^{\ell-m}-1) = e$ exactly.
  So the $k$ in the claim must exist if we are going to succeed.

  On the other hand, if $k$ is \emph{some} integer for which
  $\nu_p(x^k-1) = e$, then by choosing $\ell-m$ to be some
  multiple of $k$ with no extra factors of $p$,
  we hope that we can get $\nu_p(x^\ell-y) = e+1$.
  That's why we write $\ell = kr+m$ and see what happens when we expand.
\end{remark*}
\pagebreak


\end{document}
