\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{graphicx}

%convert this all to options for the geometry package
\setlength{\textheight}{9.00in}
\setlength{\textwidth}{6.75in}
\setlength{\topmargin}{0.0in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\leftmargin}{0.0in}
\setlength{\oddsidemargin}{-0.3in}
\setlength{\parindent}{1pc}

%\usepackage[papersize={?,?},
%			top=0.0in, left=.12in, 

\newcommand\dg{\raisebox{.15pt}{$^{\circ}$}}
\def\rd{^{\mbox{\scriptsize rd}}}
\newtheorem{claim}{Claim}
\newtheorem{lemma}{Lemma}

\pagestyle{empty}
\begin{document}

\begin{center}
${\bf 33\rd}$ \textbf{United States of America Mathematical Olympiad}
\end{center}

\bigskip
\begin{enumerate}

\item %AND1
Let $ABCD$ be a quadrilateral circumscribed about a circle, whose
interior and exterior angles are at least $60\dg$. Prove that
\[
\frac{1}{3}|AB^3 - AD^3| \le |BC^3 - CD^3| \le 3|AB^3 - AD^3|.
\]
When does equality hold?

\noindent\textbf{Solution:}
By symmetry, we only need to prove the first inequality.

Because quadrilateral $ABCD$ has an incircle, we have $AB + CD = BC +
AD$, or $AB - AD = BC - CD$. It suffices to prove that
\[
\frac{1}{3}(AB^2 + AB\cdot AD + AD^2) \le BC^2 + BC\cdot CD + CD^2.
\]
By the given condition, $60\dg \le \angle A, \angle C \le 120\dg$, and so
$\frac{1}{2} \ge \cos A, \cos C \ge -\frac{1}{2}$. Applying the
law of cosines to triangle $ABD$ yields
\begin{eqnarray*}
BD^2 & = & AB^2 - 2AB\cdot AD\cos A + AD^2 \ge AB^2 - AB\cdot AD + AD^2
\\
& \ge & \frac{1}{3} (AB^2 + AB\cdot AD + AD^2).
\end{eqnarray*}
The last inequality is equivalent to the inequality $3AB^2 - 3AB\cdot
AD + 3AD^2 \ge AB^2 + AB\cdot AD + AD^2$, or $AB^2 - 2AB\cdot AD + AD^2
\ge 0$, which is evident. The last equality holds if and only if $AB =
AD$.

On the other hand, applying the Law of Cosines to triangle $BCD$ yields
\[
BD^2 = BC^2 - 2BC\cdot CD \cos C + CD^2 \le BC^2 + BC\cdot CD + CD^2.
\]
Combining the last two inequalities gives the desired result.

For the given inequalities to hold, we must have $AB = AD$. This condition
is also sufficient, because all the entries in the equalities are 0.
Thus, the given inequalities hold if and only if $ABCD$ is a kite with
$AB = AD$ and $BC = CD$.

Problem originally by Titu Andreescu.

\vspace{5mm}

\item %KED1
Suppose $a_1, \dots, a_n$ are integers
whose greatest common divisor is 1. Let $S$ be a set of integers with the
following properties.
\begin{enumerate}
\item[(a)] For $i=1, \dots, n$, $a_i \in S$.
\item[(b)] For $i,j = 1, \dots, n$ (not necessarily distinct), 
$a_i - a_j \in S$.
\item[(c)] For any integers $x,y \in S$, if $x+y \in S$, then $x-y \in S$.
\end{enumerate}
Prove that $S$ must be equal to the set of all integers.

\noindent\textbf{Solution:}
We may as well assume that none of the $a_i$ is equal to 0.
We start with the following observations.
\begin{itemize}
\item[(d)] $0 = a_1 - a_1 \in S$ by (b).
\item[(e)] $-s = 0 - s \in S$ whenever $s \in S$, by (a) and (d).
\item[(f)] If $x,y \in S$ and $x-y \in S$, then $x+y \in S$ by (b) and (e).
\end{itemize}
By (f) plus strong induction on $m$, we have that
$ms \in S$ for any $m \geq 0$ whenever $s \in S$. By (d) and (e),
the same holds even if $m \leq 0$, and so we have the following.
\begin{itemize}
\item[(g)] For $i=1, \dots, n$, $S$ contains all multiples of $a_i$.
\end{itemize}

We next verify that
\begin{itemize}
\item[(h)] For $i,j \in \{1, \dots, n\}$ and any integers $c_i, c_j$,
$c_i a_i + c_j a_j \in S$.
\end{itemize}
We do this by induction on $|c_i| + |c_j|$.
If $|c_i| \leq 1$ and $|c_j| \leq 1$, this follows from (b), (d), (f),
so we may assume that $\max\{|c_i|, |c_j| \} \geq 2$. Suppose without
loss of generality (by switching $i$ with $j$ and/or negating
both $c_i$ and $c_j$) that $c_i \geq 2$;
then
\[
c_i a_i + c_j a_j = a_i + ((c_i-1) a_i + c_j a_j)
\]
and we have $a_i \in S$, $(c_i-1)a_i + c_ja_j \in S$ by the induction
hypothesis, and $(c_i-2)a_i + c_ja_j \in S$ again by the induction
hypothesis. So $c_i a_i + c_j a_j \in S$ by (f), and (h) is verified.

Let $e_i$ be the largest integer such that $2^{e_i}$ divides $a_i$;
without loss of generality we may
assume that $e_1 \geq e_2 \geq \cdots \geq e_n$.
Let $d_i$ be the greatest common divisor of $a_1, \dots, a_i$.
We prove by induction on $i$ that $S$ contains all multiples of $d_i$
for $i=1, \dots, n$; the case $i=n$ is the desired result.
Our base cases are $i=1$ and $i=2$,
which follow from (g) and (h), respectively.

Assume that $S$ contains all multiples of $d_i$, for some $2 \leq i<n$.
Let $T$ be the set of integers $m$ such that $m$ is divisible by $d_i$
and $m + r a_{i+1} \in S$ for all integers $r$. Then
$T$ contains nonzero positive and negative numbers, namely any multiple
of $a_i$ by (h).
By (c),
if $t \in T$ and $s$ divisible by $d_i$ (so in $S$)
satisfy $t-s \in T$, then $t+s \in T$.
By taking $t=s=d_i$, we deduce that
$2d_i \in T$; by induction
(as in the proof of (g)),
we have $2md_i \in T$ for any integer $m$ (positive, negative or zero).

From the way we ordered the $a_i$, we see that the highest power of 2
dividing $d_i$ is greater than or equal to the highest power of 2
dividing $a_{i+1}$. In other words, $a_{i+1}/d_{i+1}$ is odd.
We can thus find integers $f,g$ with $f$ even such that
$fd_i + ga_{i+1} = d_{i+1}$. (Choose such a pair without any restriction
on $f$, and replace $(f,g)$ with $(f-a_{i+1}/d_{i+1}, g
+ d_i/d_{i+1})$ if needed to get an even $f$.) Then for any
integer $r$, we have $rfd_i \in T$ and so $rd_{i+1} \in S$.
This completes the induction and the proof of the desired result.

\vspace{8pt}
\centerline{\textbf{Alternate solution by student 219 (Matthew Ince)}}
\vspace{4pt}

For integers $a_1, \dots, a_n \in \mathbb{Z}$ with greatest common divisor 1,
we say that \emph{$S$ is generated by $a_1, \dots, a_n$} if conditions
(a), (b), (c) in the problem hold. As in the proposer's solution, we deduce
that if $S$ is generated by $a_1, \dots, a_n$, then
\begin{enumerate}
\item[(d)] $0 = a_1 - a_1 \in S$ by (b).
\item[(e)] $-s = 0 - s \in S$ whenever $s \in S$, by (a) and (d).
\end{enumerate}

\begin{lemma}
If $S$ is generated by $a_1, \dots, a_n$, then $S$ is generated by
$a_1, a_2-a_1, \dots, a_n - a_1$.
\end{lemma}
\begin{proof}
Property (c) does not refer to the generators, so we need only check
(a) and (b).
\begin{enumerate}
\item[(a)] We have $a_s - a_1 \in S$ for $s>1$ by (b).
\item[(b)] The difference $a_1 - (a_s - a_1)$ is in $S$ for $s>1$
by (c), as is its negative by (e). The other
differences are of the form
$(a_s - a_1) - (a_t - a_1) = a_s - a_t$ for $s,t > 1$, which are in $S$ by (b).
\end{enumerate}
\end{proof}

\begin{lemma}
If $S$ is generated by $a_1, \dots, a_n$, then $S$ is generated by
$-a_1, a_2, \dots, a_n$.
\end{lemma}
\begin{proof}
Again, we need to check the new (a) and (b).
\begin{enumerate}
\item[(a)] We have $-a_1 \in S$ by (e).
\item[(b)] For $s > 1$, we have $a_s - (-a_1) \in S$ by
(b) (since $a_s - a_1 \in S$ by (b)), as is its negative by (e).
The other differences are in $S$ by (b).
\end{enumerate}
\end{proof}

Now suppose $S$ is generated by $a_1, \dots, a_n$ (and that none of the
$a_i$ are zero, without loss of generality); by Lemma 2, we may
assume without loss of generality that $a_i > 0$ for each $i$.
Choose integers $b_1, \dots, b_k > 0$ with greatest common divisor 1
such that $S$ is generated by
$b_1, \dots, b_k$ and $b_1 + \cdots + b_k$ is as small as possible.
Note that the $b_i$ must all be distinct (otherwise we could have omitted
one), so we may assume without loss of generality that $b_1$ is smaller
than the others.

Suppose $k>1$, and put $c_1 = b_1$ and $c_s = b_s - b_1$ for $s=2, \dots, k$.
Then $\gcd(c_1, \dots, c_k) = \gcd(b_1, \dots, b_k) = 1$, and
$S$ is generated by $c_1, \dots, c_k$ by Lemma 1. But
\[
c_1 + \cdots + c_k = (b_1 + \cdots + b_k) - (k-1)b_1 < b_1 + \cdots + b_k,
\]
contradiction. Hence $k=1$ and $b_1 = 1$.

All that remains is to check that if $S$ is generated by 1, then $S =
\mathbb{Z}$.  We show that $0,1,\dots,k \in S$ for all positive integers $k$,
by induction on $k$.  Note that $-1, 0, 1 \in S$ by (d) and (e), so the base
case $k=1$ is okay.  As for the induction step, if $0,1,\dots,k \in S$, then
$k+1 = k - (-1) \in S$ by (c). Thus the induction goes through, and all
nonnegative integers are in $S$. By (e), all negative integers are also is in
$S$. Hence $S = \mathbb{Z}$, and we are done.

Problem originally by Kiran Kedlaya.

\vspace{5mm}

\item %LIU1
For what real values of $k>0$ is it possible to dissect a $1 \times k$
rectangle into two similar, but noncongruent, polygons?

\noindent\textbf{Solution:}
We will show that a dissection
satisfying the requirements of the problems is possible if and only
if $k \neq 1$.

\medskip

We first show by contradiction that such a dissection is not
possible when $k=1$. Assume that we have such a dissection. The
common boundary of the two dissecting polygons must be a single
broken line connecting two points on the boundary of the square
(otherwise either the square is subdivided in more than two pieces
or one of the polygons is inside the other). The two dissecting
polygons must have the same number of vertices. They share all the
vertices on the common boundary, so they have to use the same
number of corners of the square as their own vertices. Therefore,
the common boundary must connect two opposite sides of the square
(otherwise one of the polygons will contain at least three corners
of the square, while the other at most two). However, this means
that each of the dissecting polygons must use an entire side of
the square as one of its sides, and thus each polygon has a side
of length 1. A side of longest length in one of the polygons is
either a side on the common boundary or, if all those sides have
length less than 1, it is a side of the square. But this is also
true of the other polygon, which means that the longest side
length in the two polygons is the same. This is impossible since
they are similar but not congruent, so we have a contradiction.

\medskip

We now construct a dissection satisfying the requirements of the
problem when $k \neq 1$. Notice that we may assume that $k>1$,
because a $1 \times k$ rectangle is similar to a $1 \times
\frac{1}{k}$ rectangle.

We first construct a dissection of an appropriately chosen
rectangle (denoted by $ABCD$ below) into two similar noncongruent polygons. The
construction depends on two parameters ($n$ and $r$ below). By
appropriate choice of these parameters we show that the constructed
rectangle can be made similar to a $1\times k$ rectangle, for any $k>1$.
The construction follows.

Let $r>1$ be a real number. For any positive integer $n$, consider
the following sequence of $2n+2$ points:
\[ A_0=(0,~0), ~A_1=(1,~0),~A_2=(1,~r), ~A_3=(1+r^2,~r), \]
\[ ~A_4=(1+r^2,~r+r^3), ~A_5=(1+r^2+r^4,~r+r^3), \]
and so on, until
\[ A_{2n+1}=(1 + r^2 + r^4 + \dots + r^{2n},~r+r^3+r^5+\dots+r^{2n-1}). \]
Define a rectangle $ABCD$ by
\[ A=A_0, ~B=(1 + r^2 + \dots + r^{2n},~0), ~C=A_{2n+1}, ~~\mbox{and}~~
 D=(0,~r+r^3+~...~+r^{2n-1}).\]
The sides of the $(2n+2)$-gon $A_1A_2\dots A_{2n+1}B$ have lengths
\[ r,~r^2, ~r^3, ~\dots~,~r^{2n}, ~r+r^3+r^5+\dots+r^{2n-1}, ~r^2+r^4+r^6+\dots+r^{2n}, \]
and the sides of the $(2n+2)$-gon $A_0A_1A_2 \dots A_{2n}D$ have
lengths
\[ 1, ~r,~r^2, ~\dots~, ~r^{2n-1}, ~1+r^2+r^4+\dots+r^{2n-2}, ~r+r^3+r^5+ \dots +r^{2n-1}, \]
respectively. These two polygons dissect the rectangle $ABCD$ and,
apart from orientation, it is clear that they are similar but
noncongruent, with coefficient of similarity $r>1$. The rectangle
$ABCD$ and its dissection are thus constructed.

The rectangle $ABCD$ is similar to a rectangle of size $1 \times
f_n(r)$, where
\[ f_n(r) = \frac{1+r^2+...+r^{2n}}{r+r^3+...+r^{2n-1}}. \]
It remains to show that $f_n(r)$ can have any value $k>1$ for
appropriate choices of $n$ and $r$. Choose $n$ sufficiently large so
that $1+\frac{1}{n}<k$. Since
\[ f_n(1)=1+\frac{1}{n} < k < k\frac{1+k^2+...+k^{2n}}{k^2+k^4+...+k^{2n}} =  f_n(k)\]
and $f_n(r)$ is a continuous function for positive $r$, there exists
an $r$ such that $1< r < k$ and $f_n(r)=k$, so we are done.

Problem originally by Ricky Liu.

\vspace{5mm}

\item %WOO1
Alice and Bob play a game on a 6 by 6 grid.  On his or her turn, a
player chooses a rational number not yet appearing in the grid and
writes it in an empty square of the grid.  Alice goes first and then
the players alternate.  When all squares have numbers written in them,
in each row, the square with the greatest number in that row is
colored black.  Alice wins if she can then draw a line from the top of
the grid to the bottom of the grid that stays in black squares, and
Bob wins if she can't.  (If two squares share a vertex, Alice can draw
a line from one to the other that stays in those two squares.)  Find,
with proof, a winning strategy for one of the players.

\noindent\textbf{Solution:}
Bob can win as follows.

\begin{claim}
After each of his moves, Bob can insure that in that maximum number in
each row is a square in $A\cup B$, where
$$A=\{(1,1),(2,1),(3,1),(1,2),(2,2),(3,2),(1,3),(2,3)\}$$ and
$$B=\{(5,3),(4,4),(5,4),(6,4),(4,5),(5,5),(6,5),(4,6),(5,6),(6,6)\}.$$
\end{claim}

\begin{proof}
Bob pairs each square of $A\cup B$ with a square in the same row that
is not in $A\cup B$, so that each square of the grid is in exactly one
pair.  Whenever Alice plays in one square of a pair, Bob will play in
the other square of the pair on his next turn.  If Alice moves with
$x$ in $A\cup B$, Bob writes $y$ with $y<x$ in the paired square.  If
Alice moves with $x$ not in $A\cup B$, Bob writes $z$ with $z>x$ in
the paired square in $A\cup $B.  So after Bob's turn, the maximum of
each pair is in $A\cup B$, and thus the maximum of each row is in
$A\cup B$.
\end{proof}

So when all the numbers are written, the maximum square in row 6 is in
$B$ and the maximum square in row 1 is in $A$.  Since there is no path
from $B$ to $A$ that stays in $A \cup B$, Bob wins.

Problem originally by Melanie Wood.

\vspace{5mm}

\item %AND2
Let $a, b$ and $c$ be positive real numbers. Prove that
\[
(a^5-a^2+3)(b^5-b^2+3)(c^5-c^2+3) \ge (a+b+c)^3.
\]

\noindent\textbf{Solution:}
For any positive number $x$, the quantities 
$x^2-1$ and $x^3-1$ have the same sign. Thus,
we have $0 \le (x^3-1)(x^2-1) = x^5 - x^3 - x^2 + 1$, or
\[
x^5 - x^2 + 3 \ge x^3 + 2.
\]
It follows that
\[
(a^5-a^2+3)(b^5-b^2+3)(c^5-c^2+3) \ge (a^3+2)(b^3+2)(c^3+2).
\]
It suffices to show that
$$
(a^3+2)(b^3+2)(c^3+2) \ge (a+b+c)^3. \eqno{(*)}
$$
We finish with two approaches.

\begin{enumerate}
\item [$\bullet$]
{\em First approach}\quad
Expanding both sides of inequality $(*)$ and cancelling like
terms gives
$$
a^3b^3c^3 + 3(a^3+b^3+c^3) + 2(a^3b^3 + b^3c^3 + c^3a^3) + 8\ge
3(a^2b+b^2a + b^2c+c^2b + c^2a+ac^2) + 6abc. \eqno{(*')}
$$
By the AM-GM Inequality, we have $a^3 + a^3b^3 + 1 \ge 3a^2b$.
Combining similar results, inequality $(*)$ reduces to
\[
a^3b^3c^3 + a^3 + b^3 + c^3 + 1 + 1 \ge 6abc,
\]
which is evident by the AM-GM Inequality.

\item [$\bullet$]
We rewrite the left-hand-side of inequality $(*)$ as
\[
(a^3+1+1)(1+b^3+1)(1+1+c^3).
\]
By H\"{o}lder's Inequality, we have
\[
(a^3+1+1)^{\frac{1}{3}}(1+b^3+1)^{\frac{1}{3}}(1+1+c^3)^{\frac{1}{3}}
\ge (a+b+c),
\]
from which inequality $(*)$ follows.
\end{enumerate}

Problem originally by Titu Andreescu.

\vspace{5mm}

\item %FEN1
A circle $\omega$ is inscribed in a quadrilateral $ABCD$. Let $I$ be the
center of $\omega$. Suppose that
\[
(AI + DI)^2 + (BI + CI)^2 = (AB + CD)^2.
\]
Prove that $ABCD$ is an isosceles trapezoid.

\noindent\textbf{Solution:}
Our proof is based on the following key Lemma.

{\bf Lemma} \quad
{\it If a circle $\omega$, centered at $I$, is inscribed in a quadrilateral
$ABCD$, then}
$$
BI^2 + \frac{AI}{DI}\cdot BI \cdot CI = AB\cdot BC. \eqno{(*)}
$$

\begin{center}%[htbp]
%\leavevmode \epsfxsize=2.5in \epsfysize=2.5in
\includegraphics{6zfeng_pic.eps}
\end{center}

{\it Proof:}\quad Since circle $\omega$ is inscribed in $ABCD$, we get
$m\angle DAI = m\angle IAB = a$, $m\angle ABI = m\angle IBC = b$, $m\angle BCI =
m\angle ICD = c$, $m\angle CDI = m\angle IDA = d$, and $a + b + c + d =
180\dg$. Construct a point $P$ outside of the quadrilateral such that
$\triangle ABP$ is similar to $\triangle DCI$.  We obtain 
\begin{eqnarray*}
 m\angle PAI
+ m\angle PBI & = & m\angle PAB + m\angle BAI + m\angle PBA + m\angle ABI \\ & = &
m\angle IDC + a + m\angle ICD + b \\ & = & a + b + c + d = 180\dg, 
\end{eqnarray*}
implying that the quadrilateral $PAIB$ is cyclic. By Ptolemy's
Theorem, we have $AI\cdot BP + BI \cdot AP = AB\cdot IP$, or
$$
BP\cdot\frac{AI}{IP} + BI\cdot \frac{AP}{IP} = AB. \eqno{(\dag)}
$$
Because $PAIB$ is cyclic, it is not difficult to see that, as indicated
in the figure, $m\angle IPB = m\angle IAB = a$, $m\angle API = m\angle ABI = b$,
$m\angle AIP = m\angle ABP = c$, and $m\angle PIB = m\angle PAB = d$. Note that
$\triangle AIP$ and $\triangle ICB$ are similar, implying that
\[
\frac{AI}{IP} = \frac{IC}{CB}\quad \mbox{and}\quad \frac{AP}{IP} =
\frac{IB}{CB}.
\]
Substituting the above equalities into the identity $(\dag)$, we arrive at
\[
BP\cdot \frac{CI}{BC} + \frac{BI^2}{BC} = AB,
\]
or
$$
BP\cdot CI + BI^2 = AB\cdot BC. \eqno{(\dag')}
$$
Note also that $\triangle BIP$ and $\triangle IDA$ are similar, implying that
$\displaystyle{\frac{BP}{BI} = \frac{IA}{ID}}$, or
\[
BP = \frac{AI}{ID}\cdot IB.
\]
Substituting the above identity back into $(\dag')$ gives the desired
relation $(*)$, establishing the Lemma.

Now we prove our main result. By the Lemma and symmetry, we 
have
$$
CI^2 + \frac{DI}{AI}\cdot BI\cdot CI = CD\cdot BC. \eqno{(*')}
$$
Adding the two identities $(*)$ and $(*')$ gives
\[
BI^2 + CI^2 + \left(\frac{AI}{DI} + \frac{DI}{AI}\right) BI\cdot CI = BC(AB +
CD).
\]
By the AM-GM Inequality, we have $\displaystyle{\frac{AI}{DI} +
\frac{DI}{AI} \ge 2}$. Thus,
\[
BC(AB + CD) \ge IB^2 + IC^2 + 2IB\cdot IC = (BI + CI)^2,
\]
where the equality holds if and only if $AI = DI$. Likewise, we have
\[
AD(AB + CD) \ge (AI + DI)^2,
\]
where the equality holds if and only if $BI = CI$. Adding the last two
identities gives
\[
(AI + DI)^2 + (BI + CI)^2 \le (AD + BC)(AB + CD) = (AB + CD)^2,
\]
because $AD + BC = AB + CD$. (The latter equality is true because the
circle $\omega$ is inscribed in the quadrilateral $ABCD$.)

By the given condition in the problem, all the equalities in the above
discussion must hold, that is, $AI = DI $ and $BI = CI$. Consequently,
we have $a = d$, $b = c$, and so $\angle DAB + \angle ABC = 2a + 2b =
180\dg$, implying that $AD \parallel BC$. It is not difficult to see
that $\triangle AIB$ and $\triangle DIC$ are congruent, implying that
$AB = CD$. Thus, $ABCD$ is an isosceles trapezoid.

Problem originally by Zuming Feng.

\end{enumerate}

\vfill
{\small
\begin{center}
Copyright \copyright\ \ Committee on the American Mathematics
Competitions,\\
Mathematical Association of America
\end{center}
}

\end{document}