HMIC 2016

Theseus starts at the point $(0,0)$ in the plane. If Theseus is standing at the point $(x, y)$ in the plane, he can step one unit to the north to point $(x, y+1)$, one unit to the west to point $(x-1, y)$, one unit to the south to point $(x, y-1)$, or one unit to the east to point $(x+1, y)$. After a sequence of more than two such moves, starting with a step one unit to the south (to point $(0,-1)$ ), Theseus finds himself back at the point $(0,0)$. He never visited any point other than $(0,0)$ more than once, and never visited the point $(0,0)$ except at the start and end of this sequence of moves.

Let $X$ be the number of times that Theseus took a step one unit to the north, and then a step one unit to the west immediately afterward. Let $Y$ be the number of times that Theseus took a step one unit to the west, and then a step one unit to the north immediately afterward. Prove that $|X-Y|=1$.

Let $A B C$ be an acute triangle with circumcenter $O$, orthocenter $H$, and circumcircle $\Omega$. Let $M$ be the midpoint of $A H$ and $N$ the midpoint of $B H$. Assume the points $M, N, O, H$ are distinct and lie on a circle $\omega$. Prove that the circles $\omega$ and $\Omega$ are internally tangent to each other.

Denote by $\mathbb{N}$ the positive integers. Let $f: \mathbb{N} \rightarrow \mathbb{N}$ be a function such that, for any $w, x, y, z \in \mathbb{N}$,

$$f(f(f(z))) f(w x f(y f(z)))=z^{2} f(x f(y)) f(w)$$

Show that $f(n!) \geq n$ ! for every positive integer $n$.

Let $P$ be an odd-degree integer-coefficient polynomial. Suppose that $x P(x)=y P(y)$ for infinitely many pairs $x, y$ of integers with $x \neq y$. Prove that the equation $P(x)=0$ has an integer root.

Let $S=\left\{a_{1}, \ldots, a_{n}\right\}$ be a finite set of positive integers of size $n \geq 1$, and let $T$ be the set of all positive integers that can be expressed as sums of perfect powers (including 1) of distinct numbers in $S$, meaning

$$T=\left\{\sum_{i=1}^{n} a_{i}^{e_{i}} \mid e_{1}, e_{2}, \ldots, e_{n} \geq 0\right\}$$

Show that there is a positive integer $N$ (only depending on $n$ ) such that $T$ contains no arithmetic progression of length $N$.