US-TST 2011

In an acute scalene triangle $ABC$ , points $D,E,F$ lie on sides $BC, CA, AB$ , respectively, such that $AD \perp BC, BE \perp CA, CF \perp AB$ . Altitudes $AD, BE, CF$ meet at orthocenter $H$ . Points $P$ and $Q$ lie on segment $EF$ such that $AP \perp EF$ and $HQ \perp EF$ . Lines $DP$ and $QH$ intersect at point $R$ . Compute $HQ/HR$ .

Proposed by Zuming Feng

In the nation of Onewaynia, certain pairs of cities are connected by roads. Every road connects exactly two cities (roads are allowed to cross each other, e.g., via bridges). Some roads have a traffic capacity of 1 unit and other roads have a traffic capacity of 2 units. However, on every road, traffic is only allowed to travel in one direction. It is known that for every city, the sum of the capacities of the roads connected to it is always odd. The transportation minister needs to assign a direction to every road. Prove that he can do it in such a way that for every city, the difference between the sum of the capacities of roads entering the city and the sum of the capacities of roads leaving the city is always exactly one.

Proposed by Zuming Feng and Yufei Zhao

Let $p$ be a prime. We say that a sequence of integers $\{z_n\}_{n=0}^\infty$ is a $p$ -pod if for each $e \geq 0$ , there is an $N \geq 0$ such that whenever $m \geq N$ , $p^e$ divides the sum $$\sum_{k=0}^m (-1)^k {m \choose k} z_k.$$ Prove that if both sequences $\{x_n\}_{n=0}^\infty$ and $\{y_n\}_{n=0}^\infty$ are $p$ -pods, then the sequence $\{x_ny_n\}_{n=0}^\infty$ is a $p$ -pod.

Find a real number $t$ such that for any set of 120 points $P_1, \ldots P_{120}$ on the boundary of a unit square, there exists a point $Q$ on this boundary with $|P_1Q| + |P_2Q| + \cdots + |P_{120}Q| = t$ .

Let $c_n$ be a sequence which is defined recursively as follows: $c_0 = 1$ , $c_{2n+1} = c_n$ for $n \geq 0$ , and $c_{2n} = c_n + c_{n-2^e}$ for $n > 0$ where $e$ is the maximal nonnegative integer such that $2^e$ divides $n$ . Prove that $$\sum_{i=0}^{2^n-1} c_i = \frac{1}{n+2} {2n+2 \choose n+1}.$$

A polynomial $P(x)$ is called nice if $P(0) = 1$ and the nonzero coefficients of $P(x)$ alternate between $1$ and $-1$ when written in order. Suppose that $P(x)$ is nice, and let $m$ and $n$ be two relatively prime positive integers. Show that $$Q(x) = P(x^n) \cdot \frac{(x^{mn} - 1)(x-1)}{(x^m-1)(x^n-1)}$$ is nice as well.

Let $ABC$ be an acute scalene triangle inscribed in circle $\Omega$ . Circle $\omega$ , centered at $O$ , passes through $B$ and $C$ and intersects sides $AB$ and $AC$ at $E$ and $D$ , respectively. Point $P$ lies on major arc $BAC$ of $\Omega$ . Prove that lines $BD, CE, OP$ are concurrent if and only if triangles $PBD$ and $PCE$ have the same incenter.

Let $n \geq 1$ be an integer, and let $S$ be a set of integer pairs $(a,b)$ with $1 \leq a < b \leq 2^n$ . Assume $|S| > n \cdot 2^{n+1}$ . Prove that there exists four integers $a < b < c < d$ such that $S$ contains all three pairs $(a,c)$ , $(b,d)$ and $(a,d)$ .

Determine whether or not there exist two different sets $A,B$ , each consisting of at most $2011^2$ positive integers, such that every $x$ with $0 < x < 1$ satisfies the following inequality: $$\left| \sum_{a \in A} x^a - \sum_{b \in B} x^b \right| < (1-x)^{2011}.$$