TSTST 2018

As usual, let $\mathbb{Z}[x]$ denote the set of single-variable polynomials in $x$ with integer coefficients. Find all functions $\theta: \mathbb{Z}[x] \rightarrow \mathbb{Z}$ such that for any polynomials $p, q \in$ $\mathbb{Z}[x]$, - $\theta(p+1)=\theta(p)+1$, and - if $\theta(p) \neq 0$ then $\theta(p)$ divides $\theta(p \cdot q)$.

In the nation of Onewaynia, certain pairs of cities are connected by one-way roads. Every road connects exactly two cities (roads are allowed to cross each other, e.g., via bridges), and each pair of cities has at most one road between them. Moreover, every city has exactly two roads leaving it and exactly two roads entering it. We wish to close half the roads of Onewaynia in such a way that every city has exactly one road leaving it and exactly one road entering it. Show that the number of ways to do so is a power of 2 greater than 1 (i.e. of the form $2^{n}$ for some integer $n \geq 1$ ).

Let $A B C$ be an acute triangle with incenter $I$, circumcenter $O$, and circumcircle $\Gamma$. Let $M$ be the midpoint of $\overline{A B}$. Ray $A I$ meets $\overline{B C}$ at $D$. Denote by $\omega$ and $\gamma$ the circumcircles of $\triangle B I C$ and $\triangle B A D$, respectively. Line $M O$ meets $\omega$ at $X$ and $Y$, while line $C O$ meets $\omega$ at $C$ and $Q$. Assume that $Q$ lies inside $\triangle A B C$ and $\angle A Q M=\angle A C B$. Consider the tangents to $\omega$ at $X$ and $Y$ and the tangents to $\gamma$ at $A$ and $D$. Given that $\angle B A C \neq 60^{\circ}$, prove that these four lines are concurrent on $\Gamma$.

For an integer $n>0$, denote by $\mathcal{F}(n)$ the set of integers $m>0$ for which the polynomial $p(x)=x^{2}+m x+n$ has an integer root. (a) Let $S$ denote the set of integers $n>0$ for which $\mathcal{F}(n)$ contains two consecutive integers. Show that $S$ is infinite but $$\sum_{n \in S} \frac{1}{n} \leq 1$$ (b) Prove that there are infinitely many positive integers $n$ such that $\mathcal{F}(n)$ contains three consecutive integers.

Let $A B C$ be an acute triangle with circumcircle $\omega$, and let $H$ be the foot of the altitude from $A$ to $\overline{B C}$. Let $P$ and $Q$ be the points on $\omega$ with $P A=P H$ and $Q A=Q H$. The tangent to $\omega$ at $P$ intersects lines $A C$ and $A B$ at $E_{1}$ and $F_{1}$ respectively; the tangent to $\omega$ at $Q$ intersects lines $A C$ and $A B$ at $E_{2}$ and $F_{2}$ respectively. Show that the circumcircles of $\triangle A E_{1} F_{1}$ and $\triangle A E_{2} F_{2}$ are congruent, and the line through their centers is parallel to the tangent to $\omega$ at $A$.

Let $S=\{1, \ldots, 100\}$, and for every positive integer $n$ define $$T_{n}=\left\{\left(a_{1}, \ldots, a_{n}\right) \in S^{n} \mid a_{1}+\cdots+a_{n} \equiv 0 (\bmod 100)\right\}$$ Determine which $n$ have the following property: if we color any 75 elements of $S$ red, then at least half of the $n$-tuples in $T_{n}$ have an even number of coordinates with red elements.

Let $n$ be a positive integer. A frog starts on the number line at 0 . Suppose it makes a finite sequence of hops, subject to two conditions: - The frog visits only points in $\left\{1,2, \ldots, 2^{n}-1\right\}$, each at most once. - The length of each hop is in $\left\{2^{0}, 2^{1}, 2^{2}, \ldots\right\}$. (The hops may be either direction, left or right.) Let $S$ be the sum of the (positive) lengths of all hops in the sequence. What is the maximum possible value of $S$ ?

For which positive integers $b>2$ do there exist infinitely many positive integers $n$ such that $n^{2}$ divides $b^{n}+1$ ?

Show that there is an absolute constant $c<1$ with the following property: whenever $\mathcal{P}$ is a polygon with area 1 in the plane, one can translate it by a distance of $\frac{1}{100}$ in some direction to obtain a polygon $\mathcal{Q}$, for which the intersection of the interiors of $\mathcal{P}$ and $\mathcal{Q}$ has total area at most $c$.