2018 TSTST Problems

Day 1

Problem 1

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] \to {\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)$.

Solution

Problem 2

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 \ge 1$). Solution

Problem 3

Let $ABC$ be an acute triangle with incenter $I$, circumcenter $O$, and circumcircle $\Gamma$. Let $M$ be the midpoint of $\overline{AB}$. Ray $AI$ meets $\overline{BC}$ at $D$. Denote by $\omega$ and $\gamma$ the circumcircles of $\triangle BIC$ and $\triangle BAD$, respectively. Line $MO$ meets $\omega$ at $X$ and $Y$, while line $CO$ meets $\omega$ at $C$ and $Q$. Assume that $Q$ lies inside $\triangle ABC$ and $\angle AQM = \angle ACB$.

Consider the tangents to $\omega$ at $X$ and $Y$ and the tangents to $\gamma$ at $A$ and $D$. Given that $\angle BAC \neq 60^{\circ}$, prove that these four lines are concurrent on $\Gamma$. Solution

Day 2

Problem 4

For an integer $n > 0$, denote by $\mathcal F(n)$ the set of integers $m > 0$ for which the polynomial $p(x) = x^2 + mx + n$ has an integer root.

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 1n \le 1.\]

Prove that there are infinitely many positive integers $n$ such that $\mathcal F(n)$ contains three consecutive integers.

Solution

Problem 5

Let $ABC$ be an acute triangle with circumcircle $\omega$, and let $H$ be the foot of the altitude from $A$ to $\overline{BC}$. Let $P$ and $Q$ be the points on $\omega$ with $PA = PH$ and $QA = QH$. The tangent to $\omega$ at $P$ intersects lines $AC$ and $AB$ at $E_1$ and $F_1$ respectively; the tangent to $\omega$ at $Q$ intersects lines $AC$ and $AB$ at $E_2$ and $F_2$ respectively. Show that the circumcircles of $\triangle AE_1F_1$ and $\triangle AE_2F_2$ are congruent, and the line through their centers is parallel to the tangent to $\omega$ at $A$.


Solution

Problem 6

Let $S = \left\{ 1, \dots, 100 \right\}$, and for every positive integer $n$ define\[T_n = \left\{ (a_1, \dots, a_n) \in S^n 		\mid a_1 + \dots + a_n \equiv 0 \pmod{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. Solution

Day 3

Problem 7

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 $\{1, 2, \dots, 2^n-1\}$, each at most once.

The length of each hop is in $\{2^0, 2^1, 2^2, \dots\}$. (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$?

Solution

Problem 8

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

Problem 9

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$. Solution