TSTST 2012

Determine all infinite strings of letters with the following properties: (a) Each letter is either $T$ or $S$, (b) If position $i$ and $j$ both have the letter $T$, then position $i+j$ has the letter $S$, (c) There are infinitely many integers $k$ such that position $2 k-1$ has the $k$ th $T$.

Let $\mathbb{N}$ be the set of positive integers. Let $f: \mathbb{N} \rightarrow \mathbb{N}$ be a function satisfying the following two conditions: (a) $f(m)$ and $f(n)$ are relatively prime whenever $m$ and $n$ are relatively prime. (b) $n \leq f(n) \leq n+2012$ for all $n$. Prove that for any natural number $n$ and any prime $p$, if $p$ divides $f(n)$ then $p$ divides $n$.

In scalene triangle $A B C$, let the feet of the perpendiculars from $A$ to $\overline{B C}, B$ to $\overline{C A}$, $C$ to $\overline{A B}$ be $A_{1}, B_{1}, C_{1}$, respectively. Denote by $A_{2}$ the intersection of lines $B C$ and $B_{1} C_{1}$. Define $B_{2}$ and $C_{2}$ analogously. Let $D, E, F$ be the respective midpoints of sides $\overline{B C}, \overline{C A}, \overline{A B}$. Show that the perpendiculars from $D$ to $\overline{A A_{2}}, E$ to $\overline{B B_{2}}$ and $F$ to $\overline{C C_{2}}$ are concurrent.

A rational number $x$ is given. Prove that there exists a sequence $x_{0}, x_{1}, x_{2}, \ldots$ of rational numbers with the following properties: (a) $x_{0}=x$; (b) for every $n \geq 1$, either $x_{n}=2 x_{n-1}$ or $x_{n}=2 x_{n-1}+\frac{1}{n}$; (c) $x_{n}$ is an integer for some $n$.

Positive real numbers $x, y, z$ satisfy $x y z+x y+y z+z x=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) \leq\left(\frac{x+y+z}{3}\right)^{5 / 8} .$$

Triangle $A B C$ is inscribed in circle $\Omega$. The interior angle bisector of angle $A$ intersects side $B C$ and $\Omega$ at $D$ and $L$ (other than $A$ ), respectively. Let $M$ be the midpoint of side $B C$. The circumcircle of triangle $A D M$ intersects sides $A B$ and $A C$ again at $Q$ and $P$ (other than $A$ ), respectively. Let $N$ be the midpoint of segment $P Q$, and let $H$ be the foot of the perpendicular from $L$ to line $N D$. Prove that line $M L$ is tangent to the circumcircle of triangle $H M N$.

Let $n$ be a positive integer. Consider a triangular array of nonnegative integers as follows: Call such a triangular array stable if for every $0 \leq i<j<k \leq n$ we have $$a_{i, j}+a_{j, k} \leq a_{i, k} \leq a_{i, j}+a_{j, k}+1$$ For $s_{1}, \ldots, 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}$.

Given a set $S$ of $n$ variables, a binary operation $\times$ on $S$ is called 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 $x y z \rightarrow x \times(y \times z)$. A string of variables in $S$ is called full if it contains each variable in $S$ at least once, and two strings are equivalent if they evaluate to the same variable regardless of which simple $\times$ is chosen. For example $x x x, x x$, 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$.