US-TST 2006

A communications network consisting of some terminals is called a $3$ -connector if among any three terminals, some two of them can directly communicate with each other. A communications network contains a windmill with $n$ blades if there exist $n$ pairs of terminals $\{x_{1},y_{1}\},\{x_{2},y_{2}\},\ldots,\{x_{n},y_{n}\}$ such that each $x_{i}$ can directly communicate with the corresponding $y_{i}$ and there is a hub terminal that can directly communicate with each of the $2n$ terminals $x_{1}, y_{1},\ldots,x_{n}, y_{n}$ . Determine the minimum value of $f (n)$ , in terms of $n$ , such that a $3$ -connector with $f (n)$ terminals always contains a windmill with $n$ blades.

In acute triangle $ABC$ , segments $AD; BE$ , and $CF$ are its altitudes, and $H$ is its orthocenter. Circle $\omega$ , centered at $O$ , passes through $A$ and $H$ and intersects sides $AB$ and $AC$ again at $Q$ and $P$ (other than $A$ ), respectively. The circumcircle of triangle $OPQ$ is tangent to segment $BC$ at $R$ . Prove that $\frac{CR}{BR}=\frac{ED}{FD}.$

Find the least real number $k$ with the following property: if the real numbers $x$ , $y$ , and $z$ are not all positive, then $$k(x^{2}-x+1)(y^{2}-y+1)(z^{2}-z+1)\geq (xyz)^{2}-xyz+1.$$

Let $n$ be a positive integer. Find, with proof, the least positive integer $d_{n}$ which cannot be expressed in the form $$\sum_{i=1}^{n}(-1)^{a_{i}}2^{b_{i}},$$ where $a_{i}$ and $b_{i}$ are nonnegative integers for each $i.$

Let $n$ be a given integer with $n$ greater than $7$ , and let $\mathcal{P}$ be a convex polygon with $n$ sides. Any set of $n-3$ diagonals of $\mathcal{P}$ that do not intersect in the interior of the polygon determine a triangulation of $\mathcal{P}$ into $n-2$ triangles. A triangle in the triangulation of $\mathcal{P}$ is an interior triangle if all of its sides are diagonals of $\mathcal{P}$ . Express, in terms of $n$ , the number of triangulations of $\mathcal{P}$ with exactly two interior triangles, in closed form.

Let $ABC$ be a triangle. Triangles $PAB$ and $QAC$ are constructed outside of triangle $ABC$ such that $AP = AB$ and $AQ = AC$ and $\angle{BAP}= \angle{CAQ}$ . Segments $BQ$ and $CP$ meet at $R$ . Let $O$ be the circumcenter of triangle $BCR$ . Prove that $AO \perp PQ.$