TSTST 2014

Let $\leftarrow$ denote the left arrow key on a standard keyboard. If one opens a text editor and types the keys "ab $\leftarrow \mathrm{cd} \leftarrow \leftarrow \mathrm{e} \leftarrow \leftarrow \mathrm{f}$ ", the result is "faecdb". We say that a string $B$ is 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$.

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 gergonnians. (a) Prove that if four gergonnians are concurrent, then all five of them are concurrent. (b) Prove that if there is a triple of gergonnians that are concurrent, then there is another triple of gergonnians that are concurrent.

Find all polynomials $P(x)$ with real coefficients that satisfy $$P(x \sqrt{2})=P\left(x+\sqrt{1-x^{2}}\right)$$ for all real numbers $x$ with $|x| \leq 1$.

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

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 .

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{gathered} c a-d b \\ c a^{2}-d b^{2} \\ c a^{3}-d b^{3} \\ c a^{4}-d b^{4} \end{gathered}$$ 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}$.