US-TST 2020

Choose positive integers $b_{1}, b_{2}, \ldots$ satisfying $$1=\frac{b_{1}}{1^{2}}>\frac{b_{2}}{2^{2}}>\frac{b_{3}}{3^{2}}>\frac{b_{4}}{4^{2}}>\cdots$$ and let $r$ denote the largest real number satisfying $\frac{b_{n}}{n^{2}} \geq r$ for all positive integers $n$. What are the possible values of $r$ across all possible choices of the sequence $\left(b_{n}\right)$ ?

Two circles $\Gamma_{1}$ and $\Gamma_{2}$ have common external tangents $\ell_{1}$ and $\ell_{2}$ meeting at $T$. Suppose $\ell_{1}$ touches $\Gamma_{1}$ at $A$ and $\ell_{2}$ touches $\Gamma_{2}$ at $B$. A circle $\Omega$ through $A$ and $B$ intersects $\Gamma_{1}$ again at $C$ and $\Gamma_{2}$ again at $D$, such that quadrilateral $A B C D$ is convex. Suppose lines $A C$ and $B D$ meet at point $X$, while lines $A D$ and $B C$ meet at point $Y$. Show that $T, X, Y$ are collinear.

Let $\alpha \geq 1$ be a real number. Hephaestus and Poseidon play a turn-based game on an infinite grid of unit squares. Before the game starts, Poseidon chooses a finite number of cells to be flooded. Hephaestus is building a levee, which is a subset of unit edges of the grid, called walls, forming a connected, non-self-intersecting path or loop. The game then begins with Hephaestus moving first. On each of Hephaestus's turns, he adds one or more walls to the levee, as long as the total length of the levee is at most $\alpha n$ after his $n$th turn. On each of Poseidon's turns, every cell which is adjacent to an already flooded cell and with no wall between them becomes flooded as well. Hephaestus wins if the levee forms a closed loop such that all flooded cells are contained in the interior of the loop - hence stopping the flood and saving the world. For which $\alpha$ can Hephaestus guarantee victory in a finite number of turns no matter how Poseidon chooses the initial cells to flood?

For a finite simple graph $G$, we define $G^{\prime}$ to be the graph on the same vertex set as $G$, where for any two vertices $u \neq v$, the pair $\{u, v\}$ is an edge of $G^{\prime}$ if and only if $u$ and $v$ have a common neighbor in $G$. Prove that if $G$ is a finite simple graph which is isomorphic to $\left(G^{\prime}\right)^{\prime}$, then $G$ is also isomorphic to $G^{\prime}$.

Find all integers $n \geq 2$ for which there exists an integer $m$ and a polynomial $P(x)$ with integer coefficients satisfying the following three conditions: - $m>1$ and $\operatorname{gcd}(m, n)=1$; - the numbers $P(0), P^{2}(0), \ldots, P^{m-1}(0)$ are not divisible by $n$; and - $P^{m}(0)$ is divisible by $n$. Here $P^{k}$ means $P$ applied $k$ times, so $P^{1}(0)=P(0), P^{2}(0)=P(P(0))$, etc.

Let $P_{1} P_{2} \ldots P_{100}$ be a cyclic 100-gon, and let $P_{i}=P_{i+100}$ for all $i$. Define $Q_{i}$ as the intersection of diagonals $\overline{P_{i-2} P_{i+1}}$ and $\overline{P_{i-1} P_{i+2}}$ for all integers $i$. Suppose there exists a point $P$ satisfying $\overline{P P_{i}} \perp \overline{P_{i-1} P_{i+1}}$ for all integers $i$. Prove that the points $Q_{1}, Q_{2}, \ldots, Q_{100}$ are concyclic.