USAMO 2009

Given circles $\omega_1$ and $\omega_2$ intersecting at points $X$ and $Y$, let $\ell_1$ be a line through the center of $\omega_1$ intersecting $\omega_2$ at points $P$ and $Q$ and let $\ell_2$ be a line through the center of $\omega_2$ intersecting $\omega_1$ at points $R$ and $S$. Prove that if $P, Q, R$ and $S$ lie on a single circle then the center of this circle lies on line $XY$.

Let $n$ be a positive integer. Determine the size of the largest subset of $\{ -n, -n+1, \dots, n-1, n\}$ which does not contain three elements $a$ , $b$ , $c$ (not necessarily distinct) satisfying $a+b+c=0$ .

We define a chessboard polygon to be a polygon whose sides are situated along lines of the form $x = a$ or $y = b$ , where $a$ and $b$ are integers. These lines divide the interior into unit squares, which are shaded alternately grey and white so that adjacent squares have different colors. To tile a chessboard polygon by dominoes is to exactly cover the polygon by non-overlapping $1 \times 2$ rectangles. Finally, a tasteful tiling is one which avoids the two configurations of dominoes shown on the left below. Two tilings of a $3 \times 4$ rectangle are shown; the first one is tasteful, while the second is not, due to the vertical dominoes in the upper right corner.

[asy]size(300); pathpen = linewidth(2.5); void chessboard(int a, int b, pair P){ for(int i = 0; i < a; ++i) for(int j = 0; j < b; ++j) if((i+j) % 2 == 1) fill(shift(P.x+i,P.y+j)*unitsquare,rgb(0.6,0.6,0.6)); D(P--P+(a,0)--P+(a,b)--P+(0,b)--cycle); } chessboard(2,2,(2.5,0));fill(unitsquare,rgb(0.6,0.6,0.6));fill(shift(1,1)*unitsquare,rgb(0.6,0.6,0.6)); chessboard(4,3,(6,0)); chessboard(4,3,(11,0)); MP("\mathrm{Distasteful\ tilings}",(2.25,3),fontsize(12));

/* draw lines */ D((0,0)--(2,0)--(2,2)--(0,2)--cycle); D((1,0)--(1,2)); D((2.5,1)--(4.5,1)); D((7,0)--(7,2)--(6,2)--(10,2)--(9,2)--(9,0)--(9,1)--(7,1)); D((8,2)--(8,3)); D((12,0)--(12,2)--(11,2)--(13,2)); D((13,1)--(15,1)--(14,1)--(14,3)); D((13,0)--(13,3));[/asy] a) Prove that if a chessboard polygon can be tiled by dominoes, then it can be done so tastefully.

b) Prove that such a tasteful tiling is unique.

For $n \ge 2$ let $a_1, a_2, \dots, a_n$ be positive real numbers such that $$(a_1 + a_2 + \dots + a_n) \left( \frac{1}{a_1} + \frac{1}{a_2} + \dots + \frac{1}{a_n} \right) \le \left( n + \frac{1}{2} \right)^2.$$ Prove that $\max(a_1, a_2, \dots, a_n) \le 4 \min(a_1, a_2, \dots, a_n)$.

Trapezoid $ABCD$, with $AB \parallel CD$, is inscribed in circle $\omega$ and point $G$ lies inside triangle $BCD$. Rays $AG$ and $BG$ meet $\omega$ again at points $P$ and $Q$, respectively. Let the line through $G$ parallel to line $AB$ intersect segment $BD$ and $BC$ at points $R$ and $S$, respectively. Prove that quadrilateral $PQRS$ is cyclic if and only if ray $BG$ bisects $\angle CBD$.

Let $s_1, s_2, s_3, \dots$ be an infinite, non-constant sequence of rational numbers, meaning it is not the case that $s_1 = s_2 = s_3 = \dots$. Suppose that $t_1, t_2, t_3, \dots$ is also an infinite, non-constant sequence of rational numbers with the property that $(s_i - s_j)(t_i - t_j)$ is an integer for all $i$ and $j$. Prove that there exists a rational number $r$ such that $(s_i - s_j)r$ and $(t_i - t_j)/r$ are integers for all $i$ and $j$.