US-TST 2007

Circles $\omega_1$ and $\omega_2$ meet at $P$ and $Q$ . Segments $AC$ and $BD$ are chords of $\omega_1$ and $\omega_2$ respectively, such that segment $AB$ and ray $CD$ meet at $P$ . Ray $BD$ and segment $AC$ meet at $X$ . Point $Y$ lies on $\omega_1$ such that $PY \parallel BD$ . Point $Z$ lies on $\omega_2$ such that $PZ \parallel AC$ . Prove that points $Q,X,Y,Z$ are collinear.

Let $n$ be a positive integer and let $a_1 \le a_2 \le \dots \le a_n$ and $b_1 \le b_2 \le \dots \le b_n$ be two nondecreasing sequences of real numbers such that $$a_1 + \dots + a_i \le b_1 + \dots + b_i \text{ for every } i = 1, \dots, n$$ and $$a_1 + \dots + a_n = b_1 + \dots + b_n.$$ Suppose that for every real number $m$ , the number of pairs $(i,j)$ with $a_i-a_j=m$ equals the numbers of pairs $(k,\ell)$ with $b_k-b_\ell = m$ . Prove that $a_i = b_i$ for $i=1,\dots,n$ .

Let $\theta$ be an angle in the interval $(0,\pi/2)$ . Given that $\cos \theta$ is irrational, and that $\cos k \theta$ and $\cos[(k + 1)\theta ]$ are both rational for some positive integer $k$ , show that $\theta = \pi/6$ .

Determine whether or not there exist positive integers $a$ and $b$ such that $a$ does not divide $b^n - n$ for all positive integers $n$ .

Triangle $ABC$ is inscribed in circle $\omega$ . The tangent lines to $\omega$ at $B$ and $C$ meet at $T$ . Point $S$ lies on ray $BC$ such that $AS \perp AT$ . Points $B_1$ and $C_1$ lie on ray $ST$ (with $C_1$ in between $B_1$ and $S$ ) such that $B_1T = BT = C_1T$ . Prove that triangles $ABC$ and $AB_1C_1$ are similar to each other.

For a polynomial $P(x)$ with integer coefficients, $r(2i - 1)$ (for $i = 1,2,3,\ldots,512$ ) is the remainder obtained when $P(2i - 1)$ is divided by $1024$ . The sequence $$(r(1),r(3),\ldots,r(1023))$$ is called the remainder sequence of $P(x)$ . A remainder sequence is called complete if it is a permutation of $(1,3,5,\ldots,1023)$ . Prove that there are no more than $2^{35}$ different complete remainder sequences.