US-TST 2023

Let $A B C$ be an acute triangle. Let $M$ be the midpoint of side $B C$, and let $E$ and $F$ be the feet of the altitudes from $B$ and $C$, respectively. Suppose that the common external tangents to the circumcircles of triangles $B M E$ and $C M F$ intersect at a point $K$, and that $K$ lies on the circumcircle of $A B C$. Prove that line $A K$ is perpendicular to line $B C$.

Consider pairs $(f, g)$ of functions from the set of nonnegative integers to itself such that - $f(0) \geq f(1) \geq f(2) \geq \cdots \geq f(300) \geq 0 ;$ - $f(0)+f(1)+f(2)+\cdots+f(300) \leq 300$; - for any 20 nonnegative integers $n_{1}, n_{2}, \ldots, n_{20}$, not necessarily distinct, we have $$g\left(n_{1}+n_{2}+\cdots+n_{20}\right) \leq f\left(n_{1}\right)+f\left(n_{2}\right)+\cdots+f\left(n_{20}\right) .$$ Determine the maximum possible value of $g(0)+g(1)+\cdots+g(6000)$ over all such pairs of functions.

For nonnegative integers $a$ and $b$, denote their bitwise xor by $a \oplus b$. (For example, $9 \oplus 10=1001_{2} \oplus 1010_{2}=0011_{2}=3$.) Find all positive integers $a$ such that for any integers $x>y \geq 0$, we have $$x \oplus a x \neq y \oplus a y .$$

Let $m$ and $n$ be fixed positive integers. Tsvety and Freyja play a game on an infinite grid of unit square cells. Tsvety has secretly written a real number inside of each cell so that the sum of the numbers within every rectangle of size either $m \times n$ or $n \times m$ is zero. Freyja wants to learn all of these numbers. One by one, Freyja asks Tsvety about some cell in the grid, and Tsvety truthfully reveals what number is written in it. Freyja wins if, at any point, Freyja can simultaneously deduce the number written in every cell of the entire infinite grid. (If this never occurs, Freyja has lost the game and Tsvety wins.) In terms of $m$ and $n$, find the smallest number of questions that Freyja must ask to win, or show that no finite number of questions can suffice.

Fix a function $f: \mathbb{N} \rightarrow \mathbb{N}$ and for any $m, n \in \mathbb{N}$ define $$\Delta(m, n)=\underbrace{f(f(\ldots f}_{f(n) \text { times }}(m) \ldots))-\underbrace{f(f(\ldots f}_{f(m) \text { times }}(n) \ldots)) .$$ Suppose $\Delta(m, n) \neq 0$ for any distinct $m, n \in \mathbb{N}$. Show that $\Delta$ is unbounded, meaning that for any constant $C$ there exist $m, n \in \mathbb{N}$ with $|\Delta(m, n)|>C$.