US-TST 2019

Let $A B C$ be a triangle and let $M$ and $N$ denote the midpoints of $\overline{A B}$ and $\overline{A C}$, respectively. Let $X$ be a point such that $\overline{A X}$ is tangent to the circumcircle of triangle $A B C$. Denote by $\omega_{B}$ the circle through $M$ and $B$ tangent to $\overline{M X}$, and by $\omega_{C}$ the circle through $N$ and $C$ tangent to $\overline{N X}$. Show that $\omega_{B}$ and $\omega_{C}$ intersect on line $B C$.

Let $\mathbb{Z} / n \mathbb{Z}$ denote the set of integers considered modulo $n$ (hence $\mathbb{Z} / n \mathbb{Z}$ has $n$ elements). Find all positive integers $n$ for which there exists a bijective function $g: \mathbb{Z} / n \mathbb{Z} \rightarrow \mathbb{Z} / n \mathbb{Z}$, such that the 101 functions $$g(x), g(x)+x, g(x)+2 x, \ldots, g(x)+100 x$$ are all bijections on $\mathbb{Z} / n \mathbb{Z}$.

A snake of length $k$ is an animal which occupies an ordered $k$-tuple $\left(s_{1}, \ldots, s_{k}\right)$ of cells in an $n \times n$ grid of square unit cells. These cells must be pairwise distinct, and $s_{i}$ and $s_{i+1}$ must share a side for $i=1, \ldots, k-1$. If the snake is currently occupying $\left(s_{1}, \ldots, s_{k}\right)$ and $s$ is an unoccupied cell sharing a side with $s_{1}$, the snake can move to occupy ( $s, s_{1}, \ldots, s_{k-1}$ ) instead. The snake has turned around if it occupied $\left(s_{1}, s_{2}, \ldots, s_{k}\right)$ at the beginning, but after a finite number of moves occupies $\left(s_{k}, s_{k-1}, \ldots, s_{1}\right)$ instead. Determine whether there exists an integer $n>1$ such that one can place some snake of length at least $0.9 n^{2}$ in an $n \times n$ grid which can turn around.

We say a function $f: \mathbb{Z}_{\geq 0} \times \mathbb{Z}_{\geq 0} \rightarrow \mathbb{Z}$ is great if for any nonnegative integers $m$ and $n$, $$f(m+1, n+1) f(m, n)-f(m+1, n) f(m, n+1)=1$$ If $A=\left(a_{0}, a_{1}, \ldots\right)$ and $B=\left(b_{0}, b_{1}, \ldots\right)$ are two sequences of integers, we write $A \sim B$ if there exists a great function $f$ satisfying $f(n, 0)=a_{n}$ and $f(0, n)=b_{n}$ for every nonnegative integer $n$ (in particular, $a_{0}=b_{0}$ ). Prove that if $A, B, C$, and $D$ are four sequences of integers satisfying $A \sim B$, $B \sim C$, and $C \sim D$, then $D \sim A$.

Let $n$ be a positive integer. Tasty and Stacy are given a circular necklace with $3 n$ sapphire beads and $3 n$ turquoise beads, such that no three consecutive beads have the same color. They play a cooperative game where they alternate turns removing three consecutive beads, subject to the following conditions: - Tasty must remove three consecutive beads which are turquoise, sapphire, and turquoise, in that order, on each of his turns. - Stacy must remove three consecutive beads which are sapphire, turquoise, and sapphire, in that order, on each of her turns. They win if all the beads are removed in $2 n$ turns. Prove that if they can win with Tasty going first, they can also win with Stacy going first.

Let $A B C$ be a triangle with incenter $I$, and let $D$ be a point on line $B C$ satisfying $\angle A I D=90^{\circ}$. Let the excircle of triangle $A B C$ opposite the vertex $A$ be tangent to $\overline{B C}$ at point $A_{1}$. Define points $B_{1}$ on $\overline{C A}$ and $C_{1}$ on $\overline{A B}$ analogously, using the excircles opposite $B$ and $C$, respectively. Prove that if quadrilateral $A B_{1} A_{1} C_{1}$ is cyclic, then $\overline{A D}$ is tangent to the circumcircle of $\triangle D B_{1} C_{1}$.