US-TST 2016

Let $S=\{1, \ldots, n\}$. Given a bijection $f: S \rightarrow S$ an orbit of $f$ is a set of the form $\{x, f(x), f(f(x)), \ldots\}$ for some $x \in S$. We denote by $c(f)$ the number of distinct orbits of $f$. For example, if $n=3$ and $f(1)=2, f(2)=1, f(3)=3$, the two orbits are $\{1,2\}$ and $\{3\}$, hence $c(f)=2$. Given $k$ bijections $f_{1}, \ldots, f_{k}$ from $S$ to itself, prove that $$c\left(f_{1}\right)+\cdots+c\left(f_{k}\right) \leq n(k-1)+c(f)$$ where $f: S \rightarrow S$ is the composed function $f_{1} \circ \cdots \circ f_{k}$.

Let $A B C$ be a scalene triangle with circumcircle $\Omega$, and suppose the incircle of $A B C$ touches $B C$ at $D$. The angle bisector of $\angle A$ meets $B C$ and $\Omega$ at $K$ and $M$. The circumcircle of $\triangle D K M$ intersects the $A$-excircle at $S_{1}, S_{2}$, and $\Omega$ at $T \neq M$. Prove that line $A T$ passes through either $S_{1}$ or $S_{2}$.

Let $p$ be a prime number. Let $\mathbb{F}_{p}$ denote the integers modulo $p$, and let $\mathbb{F}_{p}[x]$ be the set of polynomials with coefficients in $\mathbb{F}_{p}$. Define $\Psi: \mathbb{F}_{p}[x] \rightarrow \mathbb{F}_{p}[x]$ by $$\Psi\left(\sum_{i=0}^{n} a_{i} x^{i}\right)=\sum_{i=0}^{n} a_{i} x^{x^{i}} .$$ Prove that for nonzero polynomials $F, G \in \mathbb{F}_{p}[x]$, $$\Psi(\operatorname{gcd}(F, G))=\operatorname{gcd}(\Psi(F), \Psi(G))$$

Let $\sqrt{3}=1 . b_{1} b_{2} b_{3} \cdots(2)$ be the binary representation of $\sqrt{3}$. Prove that for any positive integer $n$, at least one of the digits $b_{n}, b_{n+1}, \ldots, b_{2 n}$ equals 1 .

Let $n \geq 4$ be an integer. Find all functions $W:\{1, \ldots, n\}^{2} \rightarrow \mathbb{R}$ such that for every partition $[n]=A \cup B \cup C$ into disjoint sets, $$\sum_{a \in A} \sum_{b \in B} \sum_{c \in C} W(a, b) W(b, c)=|A||B||C| .$$

Let $A B C$ be an acute scalene triangle and let $P$ be a point in its interior. Let $A_{1}$, $B_{1}, C_{1}$ be projections of $P$ onto triangle sides $B C, C A, A B$, respectively. Find the locus of points $P$ such that $A A_{1}, B B_{1}, C C_{1}$ are concurrent and $\angle P A B+\angle P B C+$ $\angle P C A=90^{\circ}$.