US-TST 2008

There is a set of $n$ coins with distinct integer weights $w_1, w_2, \ldots , w_n$ . It is known that if any coin with weight $w_k$ , where $1 \leq k \leq n$ , is removed from the set, the remaining coins can be split into two groups of the same weight. (The number of coins in the two groups can be different.) Find all $n$ for which such a set of coins exists.

Let $P$ , $Q$ , and $R$ be the points on sides $BC$ , $CA$ , and $AB$ of an acute triangle $ABC$ such that triangle $PQR$ is equilateral and has minimal area among all such equilateral triangles. Prove that the perpendiculars from $A$ to line $QR$ , from $B$ to line $RP$ , and from $C$ to line $PQ$ are concurrent.

For a pair $A = (x_1, y_1)$ and $B = (x_2, y_2)$ of points on the coordinate plane, let $d(A,B) = |x_1 - x_2| + |y_1 - y_2|$ . We call a pair $(A,B)$ of (unordered) points harmonic if $1 < d(A,B) \leq 2$ . Determine the maximum number of harmonic pairs among 100 points in the plane.

Two sequences of integers, $a_1, a_2, a_3, \ldots$ and $b_1, b_2, b_3, \ldots$ , satisfy the equation $$(a_n - a_{n - 1})(a_n - a_{n - 2}) + (b_n - b_{n - 1})(b_n - b_{n - 2}) = 0$$ for each integer $n$ greater than $2$ . Prove that there is a positive integer $k$ such that $a_k = a_{k + 2008}$ .

Let $ABC$ be a triangle with $G$ as its centroid. Let $P$ be a variable point on segment $BC$ . Points $Q$ and $R$ lie on sides $AC$ and $AB$ respectively, such that $PQ \parallel AB$ and $PR \parallel AC$ . Prove that, as $P$ varies along segment $BC$ , the circumcircle of triangle $AQR$ passes through a fixed point $X$ such that $\angle BAG = \angle CAX$ .

Mr. Fat and Ms. Taf play a game. Mr. Fat chooses a sequence of positive integers $k_1, k_2, \ldots , k_n$ . Ms. Taf must guess this sequence of integers. She is allowed to give Mr. Fat a red card and a blue card, each with an integer written on it. Mr. Fat replaces the number on the red card with $k_1$ times the number on the red card plus the number on the blue card, and replaces the number on the blue card with the number originally on the red card. He repeats this process with number $k_2$ . (That is, he replaces the number on the red card with $k_2$ times the number now on the red card plus the number now on the blue card, and replaces the number on the blue card with the number that was just placed on the red card.) He then repeats this process with each of the numbers $k_3, \ldots k_n$ , in this order. After has has gone through the sequence of integers, Mr. Fat then gives the cards back to Ms. Taf. How many times must Ms. Taf submit the red and blue cards in order to be able to determine the sequence of integers $k_1, k_2, \ldots k_n$ ?

Let $n$ be a positive integer. Given an integer coefficient polynomial $f(x)$ , define its signature modulo $n$ to be the (ordered) sequence $f(1), \ldots , f(n)$ modulo $n$ . Of the $n^n$ such $n$ -term sequences of integers modulo $n$ , how many are the signature of some polynomial $f(x)$ if a) $n$ is a positive integer not divisible by the square of a prime. b) $n$ is a positive integer not divisible by the cube of a prime.