US-EGMO-TST 2019

A $3 \times 3$ grid of unit cells is given. A snake of length $k$ is an animal which occupies an ordered $k$ -tuple of cells in this grid, say $(s_1, \dots, s_k)$ . These cells must be pairwise distinct, and $s_i$ and $s_{i+1}$ must share a side for $i = 1, \dots, k-1$ . After being placed in a finite $n \times n$ grid, if the snake is currently occupying $(s_1, \dots, s_k)$ and $s$ is an unoccupied cell sharing a side with $s_1$ , the snake can move to occupy $(s, s_1, \dots, s_{k-1})$ instead. The snake has turned around if it occupied $(s_1, s_2, \dots, s_k)$ at the beginning, but after a finite number of moves occupies $(s_k, s_{k-1}, \dots, s_1)$ instead.

Find the largest integer $k$ such that one can place some snake of length $k$ in a $3 \times 3$ grid which can turn around.

Let $n$ be a positive integer such that the number $$\frac{1^k + 2^k + \dots + n^k}{n}$$ is an integer for any $k \in \{1, 2, \dots, 99\}$ . Prove that $n$ has no divisors between 2 and 100, inclusive.

For every pair $(m, n)$ of positive integers, a positive real number $a_{m, n}$ is given. Assume that $$a_{m+1, n+1} = \frac{a_{m, n+1} a_{m+1, n} + 1}{a_{m, n}}$$ for all positive integers $m$ and $n$ . Suppose further that $a_{m, n}$ is an integer whenever $\min(m, n) \le 2$ . Prove that $a_{m, n}$ is an integer for all positive integers $m$ and $n$ .

Let the excircle of a triangle $ABC$ opposite the vertex $A$ be tangent to the side $BC$ at the point $A_1$ . Define points $B_1$ on $\overline{CA}$ and $C_1$ on $\overline{AB}$ analogously, using the excircles opposite $B$ and $C$ , respectively. Denote by $\gamma$ the circumcircle of triangle $A_1B_1C_1$ and assume that $\gamma$ passes through vertex $A$ . [list = a] [] Show that $\overline{AA_1}$ is a diameter of $\gamma$ . [] Show that the incenter of $\triangle ABC$ lies on line $B_1C_1$ . [/list]