[Solutions] United States of America Team Selection Test 2016

1. Let $S = \{1, \dots, n\}$. Given a bijection $f : S \to S$ an orbit of $f$ is a set of the form $\{x, f(x), f(f(x)), \dots \}$ 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(f_1) + \dots + c(f_k) \le n(k-1) + c(f)$where $f : S \to S$ is the composed function $f_1 \circ \dots \circ f_k$.
2. Let $ABC$ be a scalene triangle with circumcircle $\Omega$, and suppose the incircle of $ABC$ touches $BC$ at $D$. The angle bisector of $\angle A$ meets $BC$ and $\Omega$ at $E$ and $F$. The circumcircle of $\triangle DEF$ intersects the $A$-excircle at $S_1$, $S_2$, and $\Omega$ at $T \neq F$. Prove that line $AT$ passes through either $S_1$ or $S_2$.
3. 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] \to \mathbb F_p[x]$ by $\Psi\left( \sum_{i=0}^n a_i x^i \right) = \sum_{i=0}^n a_i x^{p^i}.$ Prove that for nonzero polynomials $F,G \in \mathbb F_p[x]$, $\Psi(\gcd(F,G)) = \gcd(\Psi(F), \Psi(G)).$Here, a polynomial $Q$ divides $P$ if there exists $R \in \mathbb F_p[x]$ such that $P(x) - Q(x) R(x)$ is the polynomial with all coefficients $0$ (with all addition and multiplication in the coefficients taken modulo $p$), and the gcd of two polynomials is the highest degree polynomial with leading coefficient $1$ which divides both of them. A non-zero polynomial is a polynomial with not all coefficients $0$. As an example of multiplication, $$(x+1)(x+2)(x+3) = x^3+x^2+x+1$$ in $\mathbb F_5[x]$.
4. Let $\sqrt 3 = 1.b_1b_2b_3 \dots _{(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}$, $\dots$, $b_{2n}$ equals $1$.
5. Let $n \ge 4$ be an integer. Find all functions $W : \{1, \dots, n\}^2 \to \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|.$
6. Let $ABC$ 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 $BC$, $CA$, $AB$, respectively. Find the locus of points $P$ such that $AA_1$, $BB_1$, $CC_1$ are concurrent and $\angle PAB + \angle PBC + \angle PCA = 90^{\circ}$.
 MOlympiad.NET là dự án thu thập và phát hành các đề thi tuyển sinh và học sinh giỏi toán. Quý bạn đọc muốn giúp chúng tôi chỉnh sửa đề thi này, xin hãy để lại bình luận facebook (có thể đính kèm hình ảnh) hoặc google (có thể sử dụng $\LaTeX$) bên dưới. BBT rất mong bạn đọc ủng hộ UPLOAD đề thi và đáp án mới hoặc liên hệbbt.molympiad@gmail.comChúng tôi nhận tất cả các định dạng của tài liệu: $\TeX$, PDF, WORD, IMG,...