\documentclass[11pt]{article}
\usepackage{amsmath, amsthm, amsfonts, latexsym, epsf}

\setlength{\textheight}{9.25in}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{0.0in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\leftmargin}{0.0in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\parindent}{1pc}

\def\calA{\mathcal{A}}
\def\calB{\mathcal{B}}
\def\calF{\mathcal{F}}
\def\calG{\mathcal{G}}
\def\calL{\mathcal{L}}
\def\calO{\mathcal{O}}
\def\calP{\mathcal{P}}
\def\calS{\mathcal{S}}
\def\calT{\mathcal{T}}
\def\ida{\mathfrak{a}}
\def\idb{\mathfrak{b}}
\def\idm{\mathfrak{m}}
\def\idn{\mathfrak{n}}
\def\idp{\mathfrak{p}}
\def\CC{\mathbb{C}}
\def\FF{\mathbb{F}}
\def\N{\mathbb{N}}
\def\NN{\mathbb{N}}
\def\PP{\mathbb{P}}
\def\QQ{\mathbb{Q}}
\def\RR{\mathbb{R}}
\def\R{\mathbb{R}}
\def\Z{\mathbb{Z}}
\def\ZZ{\mathbb{Z}}
\def\bou{\mathbf{u}}
\def\bov{\mathbf{v}}
\def\bow{\mathbf{w}}

\def\dg{\raisebox{.15pt}{$^{\circ}$}}
\def\binom#1#2{{#1 \choose #2}}
\def\mymod#1{\,(\mbox{mod}\,\, #1)}
\def\pmatrix#1{\left( \begin{array}{ccc} #1 \end{array} \right)}
\def\head#1{{\bf \noindent \newline #1:  } \nopagebreak}
\def\map#1#2#3{#1\!: #2\to #3}
\def\benum{\begin{enumerate}}
\def\eenum{\end{enumerate}}
\def\soln{{\bf \noindent \newline Solution:  } \nopagebreak}
\def\first{{\bf \noindent \newline First Solution:  } \nopagebreak}
\def\second{{\bf \noindent \newline Second Solution:  } \nopagebreak}
\def\third{{\bf \noindent \newline Third Solution:  } \nopagebreak}
\def\fourth{{\bf \noindent \newline Fourth Solution:  } \nopagebreak}
\def\fifth{{\bf \noindent \newline Fifth Solution:  } \nopagebreak}
\def\sixth{{\bf \noindent \newline Sixth Solution:  } \nopagebreak}
\def\note{{\bf \noindent \newline Note:  } \nopagebreak}
\def\comment{{\bf \noindent \newline Comment:  } \nopagebreak}
\def\remark{{\bf \noindent \newline Remark:  } \nopagebreak}
\def\hint{{\bf \noindent \newline Hint:  } \nopagebreak}
\def\source{{\bf \noindent \newline Source:  } \nopagebreak}
\def\|{~|~}
\def\dnd{\!\not\;\mid }
\def\T{^{\rm T}}
\def\sfn{\widehat}
\def\cis{\,\mbox{cis}\,}
\def\vv{\vec{v}}
\def\wm{\hat{w}}
\def\legendre#1#2{\left( \frac{#1}{#2} \right)}
\def\script{\scriptsize}
\def\th{^{\script\mbox{th}}}
\def\st{^{\script\mbox{st}}}
\def\nd{^{\script\mbox{nd}}}
\def\eop{\rule{5pt}{5pt}}
\newtheorem{lemma}{Lemma}
\newcounter{newtheorem}

\def\be{\begin{enumerate}}
\def\ee{\end{enumerate}}
\def\beq{\begin{equation}}
\def\eeq{\end{equation}}
\def\beqa{\begin{eqnarray*}}
\def\eeqa{\end{eqnarray*}}
\def\bea{\begin{array}}
\def\eea{\end{array}}
\def\ii{\item}
\def\ds{\dsp}
\def\seqa{a_{1}, \dots, a_{n}}
\def\seqb{b_{1}, \dots, b_{n}}
\def\seqx{x_{1}, \dots, x_{n}}
\def\lf{\lfloor}
\def\rf{\rfloor}
\def\lc{\lceil}
\def\rc{\rceil}
\def\Lp{\left(}
\def\Rp{\right)}
\def\L[{\left[}
\def\R]{\right]}
\def\alf{\alpha}
\def\lcm{\mbox{lcm}}
\def\reseteq{\setcounter{equation}{0}}
\def\Avec{{(A_{1}, \ldots, A_{n})}}
\def\xvec{{(x_{1}, \ldots, x_{n})}}
\def\Acup{\bigcup_{i=1}^{n}A_{i}}
\def\crn{{\sqrt[3]{n}}}
\def\ang{\angle}
\def\ep{\epsilon}
\def\dsp{\displaystyle}
\def\oar{\overrightarrow}
\def\ol{\overline}
\def\|{~|~}
\def\dnd{\!\not\;\mid }
\def\T{^{\rm T}}
\def\sfn{\widehat}
\def\cis{\,\mbox{cis}\,}
\def\vv{\vec{v}}
\def\wm{\hat{w}}
\def\legendre#1#2{\left( \frac{#1}{#2} \right)}
\def\script{\scriptsize}
\def\th{^{\script\mbox{th}}}
\def\1st{^{\script\mbox{st}}}
\def\2nd{^{\script\mbox{nd}}}
\def\3rd{^{\script\mbox{rd}}}

\def\cycsum{\sum_{\mbox{\small cyc}}}
\def\ssum{\sum_{\mathrm{sym}}}
\newcommand{\hex}[6]{
\ensuremath{\displaystyle {#1}\,{{#2}\atop {#6}}\,{{#3}\atop
{#5}}\,{#4}}}

\def\bi{\begin{itemize}}
\def\ei{\end{itemize}}
\def\dd{\dots}
\def\half{\frac{1}{2}}
\def\sang{\sin \angle}

\hyphenation{Zvezde-lina}
\hyphenation{Olym-piad}

\def\head#1{\begin{center} {\bf #1} \end{center}}

\pagestyle{empty}
\begin{document}
%\input epsf

\begin{center}
${\bf 32\2nd}$ {\bf United States of America Mathematical Olympiad} \\[.1in]
%{\bf Lincoln, Nebraska} \\ [.05in]
{\bf Recommended Marking Scheme}\\[.05in]
{\bf May 1, 2003}
\end{center}
\vspace*{.3in}

\remark The general philosophy of this marking scheme follows that of
IMO 2002. This scheme encourages {\em complete solutions}. Partial
credits will be given under more strict circumstances. Each solution by
students shall be graded from one of the two approaches: (1) from 7
going down (a complete solution with possible minor errors); (2) from 0
going up (a solution missing at least one critical idea.) Most partial
credits are not additive. Because there are many results need to be
proved progressively in problem 3, most partial credits in this problem
are accumulative. Many problems have different approaches. Graders are
encouraged to choose the approach that most favorable to students. But
the partial credits from different approaches are not additive.

\be
\ii [1.] %EEE
%Titu
Prove that for every positive integer $n$ there exists an
$n$-digit number divisible by $5^n$ all of whose digits are odd.

\soln
We proceed by induction. The property is clearly true for $n=1$. Assume
that $N=a_1a_2\ldots a_n$ is divisible by $5^n$ and has only odd
digits. Consider the numbers
\beqa
& & N_1 = 1a_1a_2\ldots a_n=1\cdot 10^n+5^nM = 5^n(1\cdot 2^n+M),\\
& & N_2 = 3a_1a_2\ldots a_n=3\cdot 10^n+5^nM = 5^n(3\cdot 2^n+M), \\
& & N_3 = 5a_1a_2\ldots a_n=5\cdot 10^n+5^nM = 5^n(5\cdot 2^n+M),\\
& & N_4 = 7a_1a_2\ldots a_n=7\cdot 10^n+5^nM = 5^n(7\cdot 2^n+M),\\
& & N_5 = 9a_1a_2\ldots a_n=9\cdot 10^n+5^nM = 5^n(9\cdot 2^n+M).\\
\eeqa

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 2 points for setting up clear induction steps and making
attempts to discuss numbers $N_1, N_2, N_3, N_4, N_5$.} \\
\hline
\end{tabular}
\end{center}

The numbers $ 1\cdot 2^n+M,3\cdot 2^n+M,5\cdot 2^n+M,7\cdot
2^n+M,9\cdot 2^n+M$ give distinct remainders when divided by $5$.
Otherwise the difference of some two of them would be a multiple
of $5$, which is impossible, because $2^n$ is not a multiple of
$5$, nor is the difference of any two of the numbers $1,3,5,7,9$.
It follows that one of the numbers $N_1,N_2,N_3,N_4,N_5$ is
divisible by $5^n\cdot 5$, and the induction is complete.

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 5 points for completing the proof.} \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
\remark
No points should be given for just mentioning induction. If there
is any unclear arguments in the proof of the inducting step, 2
points should be deducted. The possible marks for this problem are
0, 2, 5, 7. \\
\hline
\end{tabular}
\end{center}

\newpage
\ii [2.]
% Gal2, MMH
A convex polygon $\calP$ in the plane is dissected into smaller
convex polygons by drawing all of its diagonals. The lengths of
all sides and all diagonals of the polygon $\calP$ are rational
numbers. Prove that the lengths of all sides of all polygons in
the dissection are also rational numbers.


\soln
Let $\calP = A_1A_2\dots A_n$, where $n$ is an integer with $n \ge
3$. The problem is trivial for $n = 3$ because there are no
diagonals and thus no dissections. We assume that $n\ge 4$. Our
proof is based on the following Lemma.

{\bf Lemma 1.} \quad
{\it Let $ABCD$ be a convex quadrilateral such that all its sides and
diagonals have rational lengths. If segments $AC$ and $BD$ meet at
$P$, then segments $AP$, $BP$, $CP$, $DP$ all have rational
lengths.}

\begin{figure}[htbp]
%\leavevmode \epsfxsize=2.5in \epsfysize=2.5in
\centering\epsfbox{usa0321.eps}
\end{figure}

It is clear by Lemma 1 that the desired result holds when $\calP$ is a
convex quadrilateral. Let $A_iA_j$ ($1\le i < j \le n$) be a diagonal
of $\calP$. Assume that $C_1$, $C_2$, $\dots$, $C_m$ are the
consecutive division points on diagonal $A_iA_j$ (where point $C_1$ is
the closest to vertex $A_i$ and $C_m$ is the closest to $A_j$). Then
the segments $C_{\ell}C_{\ell+1}$, $1\le \ell\le m-1$, are the sides of
all polygons in the dissection. Let $C_{\ell}$ be the point where
diagonal $A_iA_j$ meets diagonal $A_sA_t$. Then quadrilateral
$A_iA_sA_jA_t$ satisfies the conditions of Lemma 1. Consequently,
segments $A_iC_{\ell}$ and $C_{\ell}A_j$ have rational lengths.
Therefore, segments $A_iC_1, A_iC_2, \dots, A_jC_m$ all have rational
lengths. Thus, $C_{\ell}C_{\ell+1} = AC_{\ell+1}-AC_{\ell}$ is
rational. Because $i, j, \ell$ are arbitrarily chosen, we proved that
all sides of all polygons in the dissection are also rational numbers.

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 1 point for reducing this problem to a problem on convex
quadrilateral.} \\
\hline
\end{tabular}
\end{center}

Now we present four proofs of Lemma 1 to finish our proof.

\be

\ii [$\bullet$]
{\em First approach}\quad
We show only that segment $AP$ is rational, the others being similar.
Introduce Cartesian coordinates with $A = (0,0)$ and $C = (c,0)$. Put
$B = (a,b)$ and $D = (d,e)$. Then by hypothesis, the numbers
\beqa
& & AB = \sqrt{a^2+b^2}, \quad AC = c,\quad AD = \sqrt{d^2+e^2}, \\
& & BC = \sqrt{(a-c)^2+b^2}, \quad BD = \sqrt{(a-d)^2 + (b-e)^2},
\quad CD = \sqrt{(d-c)^2+e^2},
\eeqa
are rational. In particular,
\[
BC^2 - AB^2 - AC^2 = (a-c)^2 + b^2 - (a^2+b^2) - c^2 = 2ac
\]
is rational. Because $c \ne 0$, $a$ is rational. Likewise $d$ is
rational.

\begin{figure}[htbp]
%\leavevmode \epsfxsize=2.5in \epsfysize=2.5in
\centering\epsfbox{usa0322.eps}
\end{figure}

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 2 points for setting up coordinates and verifying the
rationality of at least one non-trivial component of a vertex.}
\\
\hline
\end{tabular}
\end{center}

Now we have that $b^2 = AB^2 - a^2$, $e^2 = AD^2 - d^2$, $(b-e)^2 =
BD^2 - (a-d)^2$ are rational, and so that $2be = b^2 + e^2 - (b-e)^2$
is rational. Because quadrilateral $ABCD$ is convex, $b$ and $e$ are
nonzero and have opposite sign. Hence $\frac{b}{e} = \frac{2be}{2b^2}$
is rational.

We now calculate
\[
P = \left( \frac{bd - ae}{b-e}, 0 \right),
\]
so
\[
AP = \frac{\frac{b}{e}\cdot d-a}{\frac{b}{e}-1}
\]
is rational. \hfill\eop
\ee

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 4 points for showing one of $AP, BP, CP, DP$ are rational.}
\\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline \remark As in the first approach, 1+2 = 2 rule applies here.
(With Lemma 1 and setting up coordinates and obtaining some nontrivial
result.) The possible marks following this approach are 0, 1, 2, 7.
\\
\hline
\end{tabular}
\end{center}

\ii [$\bullet$]
{\em Second approach}\quad

Note that, for an angle $\alpha$, if $\cos\alpha$ is rational, then
$\sin \alpha = r_{\alpha}\sqrt{m_{\alpha}}$ for some rational $r$ and
square-free positive integer $m$ (and this expression is unique when
$r$ is written in the lowest term). We say two angles $\alpha$ and
$\beta$ with rational cosine are {\em equivalent} if $m_{\alpha} =
m_{\beta}$, that is, if $\sin \alpha/\sin\beta$ is rational. We
establish the following lemma.

{\bf Lemma 2.} \quad
{\it Let $\alpha$ and $\beta$ be two angles.
\be
\ii [(a)]
If $\alpha$, $\beta$ and $\alpha + \beta$ all have rational cosines,
then all three are equivalent.
\ii [(b)]
If $\alpha$ and $\beta$ have rational cosine values and are equivalent,
then $\alpha + \beta$ has rational cosine value (and is equivalent to
the other two).
\ii [(c)]
If $\alpha$, $\beta$ and $\gamma$ are the angles of a triangle with
rational sides, then all three have rational cosine values and are
equivalent.
\ee}

{\bf Proof:}\quad
Assume that $\cos\alpha = s$ and $\cos\beta = t$.
\be
\ii [(a)]
Assume that $s$ and $t$ are rational. By the {\bf Addition formula}, we
have
$$
\cos(\alpha + \beta) = \cos\alpha\cos\beta - \sin\alpha\sin\beta,
\eqno{(*)}
$$
or, $\sin\alpha\sin\beta = st - \cos(\alpha+\beta)$, which is rational
by the given conditions. Hence $\alpha$ and $\beta$ are equivalent.
Thus $\sin\alpha = r_a\sqrt{m}$ and $\sin\beta = r_b\sqrt{m}$ for some
rational numbers $r_a$ and $r_b$ and some positive square free integer
$m$. By the Addition formula, we have
\[
\sin(\alpha + \beta) = \sin\alpha\cos\beta + \cos\alpha\sin\beta =
(tr_a + sr_b)\sqrt{m},
\]
implying that $\alpha+\beta$ is equivalent to both $\alpha$ and
$\beta$.
\ii [(b)]
By $(*)$, $\cos(\alpha + \beta)$ is rational if $s, t$ are rational and
$\alpha$ and $\beta$ are equivalent. Then by (a), $\alpha$, $\beta$,
$\alpha+\beta$ are equivalent.
\ii [(c)]
Applying the {\bf Law of Cosine} to triangle $ABC$ shows that
$\cos\alpha$, $\cos\beta$ and $\cos\gamma$ are all rational. Note that
$\cos\gamma = \cos(180\dg - \alpha - \beta) = -\cos(\alpha+\beta)$. The
desired conclusions follow from (a). \hfill\eop
\ee

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 4 points for proving this Lemma. 2 points can be given for failed
attempts with decent arguments on rationalities of cosine values with
correct cosine and sine addition formulas.} \\
\hline
\end{tabular}
\end{center}

\begin{figure}[htbp]
%\leavevmode \epsfxsize=2.5in \epsfysize=2.5in
\centering\epsfbox{usa0323.eps}
\end{figure}

We say a triangle {\em rational} if all its sides are rational. By
Lemma 2 (c), all the angles in a rational triangle have rational cosine
values and are equivalent to each other. To prove Lemma 1, we set $\ang
DAC = A_1$, $\ang CAB = A_2$, $\ang ABD = B_1$, $\ang DBC = B_2$, $\ang
BCA = C_1$, $\ang ACD = C_2$, $\ang CDB = D_1$, $\ang BDA = D_2$.
Because triangles $ABC$, $ABD$, $ADC$ are rational, angles $A_2,
A_1+A_2, A_1$ all have rational cosine values. By Lemma 2 (a), $A_1$
and $A_2$ are equivalent. Similarly, we can show that $B_1$ and $B_2$,
$C_1$ and $C_2$, $D_1$ and $D_2$ are equivalent. Because triangle $ABC$
is rational, angles $A_2$ and $C_1$ are equivalent. There all angles
$A_1, A_2, B_1, \dots , D_2$ have rational cosine values and are
equivalent.

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 1 point for proving this part.} \\
\hline
\end{tabular}
\end{center}

Because angles $A_2$ and $B_1$ are equivalent, angle $A_2 + B_1$ has
rational values and is equivalent to $A_2$ and $B_1$. Thus, $\ang APB =
180\dg - (A_2+B_1)$ has rational cosine value and is equivalent to
$A_2$ and $B_1$. Apply the {\bf Law of Sine} to triangle $ABP$ gives
\[
\frac{AB}{\sin\ang APB} = \frac{AP}{\sin\ang B_1} = \frac{BP}{\sin\ang
A_2},
\]
implying that both $AP$ and $BP$ have rational length. Similarly, we
can show that both $CP$ and $DP$ has rational length, proving Lemma 1.

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 1 point for this final finishing touch.} \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline \remark In grading this approach, we have some new rules in
addition: 1 + 1 = 1, 1 + 2 = 2, 1 + 1 + 2 = 2, 1 + 1 + 1 + 2 = 2, 1 + 4
= 4. Basically, without a complete proof of Lemma 2, there will be at
most 2 points given. After proving Lemma 2, we require students to have
at least 2 of remaining subtle parts to obtain more partial credits.
The possible marks following this approach are 0, 1, 2, 4, 6, 7 (even
though a score of 5 is very unlikely).
\\
\hline
\end{tabular}
\end{center}

\ii [$\bullet$]
{\em Third approach}\quad This approach applies the techniques used in
the first approach into the second approach. To prove Lemma 1, we set
$\ang DAP = A_1$ and $\ang BAP = A_2$. Applying the Law of Cosine to
triangle $ABC$, $ABC$, $ADC$ shows that angles $A_1, A_2, A_1+A_2$ all
has rational cosine values. By the Addition formula, we have
\[
\sin A_1\sin A_2 = \cos A_1\cos A_2 - \cos (A_1 + A_2),
\]
implying that $\sin A_1\sin A_2$ is rational.

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 1 point for proving this part.} \\
\hline
\end{tabular}
\end{center}

Thus,
\[
\frac{\sin A_2}{\sin A_1} = \frac{\sin A_2\sin A_1}{\sin^2 A_1} =
\frac{\sin A_2\sin A_1}{1-\cos^2 A_1}
\]
is rational.

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 1 point for proving this part.} \\
\hline
\end{tabular}
\end{center}

\begin{figure}[htbp]
%\leavevmode \epsfxsize=2.5in \epsfysize=2.5in
\centering\epsfbox{usa0324.eps}
\end{figure}

Note that the ratio between areas of triangle $ADP$ and $ABP$ is equal
to $\frac{PD}{BP}$. Therefore,
\[
\frac{BP}{PD} = \frac{[ABP]}{[ADP]} = \frac{\frac{1}{2}AB\cdot
AP\cdot\sin A_2}{\frac{1}{2}AD\cdot AP\cdot\sin A_1} =
\frac{AB}{AD}\cdot\frac{\sin A_2}{\sin A_1},
\]
implying that $\frac{PD}{BP}$ is rational. Because $BP + PD = BD$ is
rational, both $BP$ and $PD$ are rational. Similarly, $AP$ and $PC$ are
rational, proving Lemma 1.

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 4 point for proving this part.} \\
\hline
\end{tabular}
\end{center}


\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline \remark In grading this approach, we have some new rules in
addition: 1 + 1 = 1, 1 + 1 + 1 = 2, that is, we give 2 points for
proving $\frac{\sin\alpha}{\sin\beta}$ is rational. In this approach,
it seems impossible to prove $AP$ is rational without using the fact
$\frac{\sin\alpha}{\sin\beta}$ is rational. The possible marks
following this approach are 0, 1, 2, 6, 7.
\\
\hline
\end{tabular}
\end{center}


\ii [$\bullet$]
{\em Fourth approach}\quad This approach is based on the following
lemma.

{\bf Lemma 3.} \quad
{\it Let $ABC$ be a triangle, $D$ be a point on side $AC$, $\phi_1=\ang
DAB$, $\phi_2 = \ang DBA$, $\phi_3 = \ang DBC$, $\phi_4=\ang DCB$, $AB
= c$, $BC = a$, $AD = x$, and $DC = y$. If the numbers $a, c$, and
$\cos\phi_i$ ($1\le i \le 4$) are all rational, then numbers $x$ and
$y$ are also rational.}

\begin{figure}[htbp]
%\leavevmode \epsfxsize=2.5in \epsfysize=2.5in
\centering\epsfbox{usa0325.eps}
\end{figure}


{\bf Proof:}\quad
Note that $x + y = AC = c\cos\phi_1 + a\cos\phi_4$ is rational. Hence
$x$ is rational if and only if $y$ is rational. Let $BD = z$.
Projecting point $D$ onto the lines $AB$ and $BC$ yields
\[
\left\{
\begin{array}{l}
x\cos\phi_1 + z\cos\phi_2= c,\\
y\cos\phi_4 + z\cos\phi_3= a,
\end{array}
\right.
\]
or, denoting $c_i=\cos\phi_i$ for $i=1, 2, 3, 4$,
\[
\left\{
\begin{array}{l}
c_1x + c_2z= c,\\
c_4y + c_3z= a.
\end{array}
\right.
\]
Eliminating $z$, we get $(c_1c_3)x-(c_2c_4)y=c_3c - c_2a$, which is
rational. Hence there exist rational numbers, $r_1$ and $r_2$, such
that
\[
\left\{
\begin{array}{l}
(c_1c_3)x-(c_2c_4)y = r_1,\\
x + y = r_2.
\end{array}
\right.
\]


\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 2 points for reducing to this linear system.} \\
\hline
\end{tabular}
\end{center}

We consider two cases.
\be
\ii [$\bullet$]
In this case, we assume that the determinant of the above system,
$c_1c_3+c_2c_4$, is not equal to $0$, then this system has a unique
solution $(x, y)$ in rational numbers.
\ii [$\bullet$]
In this case, we assume that the determinant $c_1c_3+c_2c_4 = 0$, or
\[
\cos\phi_1\cos\phi_3= - \cos\phi_2\cos\phi_4.
\]
Let's denote $\theta=\angle BDC$, then $\phi_2 = \theta -\phi_1$
and $\phi_3 = 180\dg - (\theta+\phi_4)$. Then the above equation
becomes
\[
\cos\phi_1\cos(\theta+\phi_4)= \cos\phi_4\cos(\theta -\phi_1).
\]
by the {\bf Product-to-sum formulas}, we have
\[
\cos(\theta+\phi_1+\phi_4) + \cos(\theta+\phi_4-\phi_1) =
\cos(\theta+\phi_4-\phi_1) + \cos(\theta-\phi_1-\phi_4),
\]
or
\[
\cos(\theta+\phi_1+\phi_4) = \cos(\theta-\phi_1-\phi_4).
\]
It is possible only if $[\theta+\phi_1+\phi_4] \pm
[\theta-\phi_1-\phi_4] = 360\dg$, that is, either $\theta = 180\dg$ or
$\phi_1+\phi_4 = 180\dg$, which is impossible because they are angles
of triangles.
\ee
Thus, the determinant $c_1c_3+c_2c_4$ is not equal to 0 and $x$
and $y$ are both rational numbers. \hfill\eop

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 3 points for solving this system. No points for discussing
non-degenerate case.} \\
\hline
\end{tabular}
\end{center}

Now we are ready to prove Lemma 1. Applying the Law of Cosine to
triangles $ABC, ACD, ABD$ shows that $\cos\ang BAC$, $\cos\ang CAD$,
$\cos\ang ABD$, $\cos\ang ADB$ are all rational. Applying Lemma 1 to
triangle $ABD$ shows that both of the segments $BP$ and $DP$ have
rational lengths. In exactly the same way, we can show that both of the
segments $AP$ and $CP$ have rational lengths.

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 1 point for this final finishing touch.} \\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline \remark In grading this approach, we have some new rules in
addition: 1 + 1 = 1, 1 + 2 = 2, 1 + 1 + 2 = 2. Basically, without a
complete proof of Lemma 2, there will be at most 2 points given.
Partial credits are additive with complete proof of Lemma 3. The
possible marks following this approach are 0, 1, 2, 5, 6, 7 (even
though a score of 5 is very unlikely).
\\
\hline
\end{tabular}
\end{center}

\note
It's interesting how easy it is to get a gap in the proof of the Lemma
1 by using the core idea of the proof of Lemma 3. Here is an example.

Let us project the intersection point of the diagonals, $O$, onto
the four lines of all sides of the quadrilateral. We get the
following $4\times 4$ system of linear equations:
\[
\left\{
\begin{array}{l}
\cos\phi_1~x+\cos\phi_2 y = a,\\
\cos\phi_3 y+\cos\phi_4 z = b,\\
\cos\phi_5 z+\cos\phi_6 t = c,\\
\cos\phi_7 t+\cos\phi_8 x = d.
\end{array}
\right.
\]
Using the {\bf Kramer's Rule}, we conclude that all $x, y, z,$ and
$t$ must be rational numbers, for all the corresponding
determinants are rational. However, this logic works only if the
determinant of the system is different from $0$.

Unfortunately, there are many geometric configurations for which the
determinant of the system vanishes (for example, this occurs for
rectangles), and you cannot make a conclusion of rationality of the
segments $x, y, z,$ and $t$. That's why Lemma 2 plays the central role
in the solution to this problem.

\newpage
\ii [3.]
%{\bf SUN2} %MMH
Let $n \neq 0$. For every sequence of integers
\[
A = a_0,a_1,a_2,\dots, a_n
\]
satisfying $0 \le a_i \le i$, for $i=0,\dots,n$, define another
sequence
\[
t(A)= t(a_0), t(a_1), t(a_2), \dots, t(a_n)
\]
by setting $t(a_i)$ to be the number of terms in the sequence $A$
that precede the term $a_i$ and are different from $a_i$. Show
that, starting from any sequence $A$ as above, fewer than $n$
applications of the transformation $t$ lead to a sequence $B$ such
that $t(B) = B$.

\soln
Note first that the transformed sequence $t(A)$ also satisfies the
inequalities $0 \le t(a_i) \le i$, for $i = 0, \dots, n$. Call any
integer sequence that satisfies these inequalities an {\em index
bounded sequence}.

We prove now that that $a_i \le t(a_i)$, for $i = 0, \dots, n$. Indeed,
this is clear if $a_i=0$. Otherwise, let $x=a_i>0$ and $y=t(a_i)$. None
of the first $x$ consecutive terms $a_0,a_1,\dots,a_{x-1}$ is greater
than $x-1$ so they are all different from $x$ and precede $x$ (see the
diagram below). Thus $y \ge x$, that is, $a_i \le t(a_i)$, for $i = 0,
\dots,n$.

\begin{center}
\begin{tabular}{c|cccccc}
index  &   0      &   1      & $\dots$ &    $x-1$      & $\dots$ & $i$ \\
\hline
$A$    & $a_0$    & $a_1$    & $\dots$ & $a_{x-1}$     & $\dots$ & $x$ \\
$t(A)$ & $t(a_0)$ & $t(a_1)$ & $\dots$ &  $t(a_{x-1})$ & $\dots$ &
$y$
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 1 point for stating and proving this fact.}
\\
\hline
\end{tabular}
\end{center}

This already shows that the sequences stabilize after finitely many
applications of the transformation $t$, because the value of the index
$i$ term in index bounded sequences cannot exceed $i$. Next we prove
that if $a_i=t(a_i)$, for some $i=0, \dots, n$, then no further
applications of $t$ will ever change the index $i$ term. We consider
two cases.

\be
\ii [$\bullet$] \quad
In this case, we assume that $a_i = t(a_i) = 0$. This means that
no term on the left of $a_i$ is different from 0, that is, they
are all 0. Therefore the first $i$ terms in $t(A)$ will also be 0
and this repeats (see the diagram below).

\begin{center}
\begin{tabular}{c|cccc}
index &   0 &   1 & $\dots$ & $i$ \\ \hline
$A$   &   0 &   0 & $\dots$ & 0 \\
$t(A)$&   0 &   0 & $\dots$ & 0
\end{tabular}
\end{center}

\ii [$\bullet$] \quad
In this case, we assume that $a_i = t(a_i) = x > 0$. The first $x$
terms are all different from $x$. Because $t(a_i) = x$, the terms
$a_x, a_{x+1}, \dots, a_{i-1}$ must then all be equal to $x$.
Consequently, $t(a_j) = x$ for $j = x,\dots, i-1$ and further
applications of $t$ cannot change the index $i$ term (see the
diagram below).

\begin{center}
\begin{tabular}{c|cccccccccc}
index & 0 & 1 & \dots & $x-1$ & $x$ & $x+1$ & $\dots$ & $i$ \\
\hline
$A$   & $a_0$   & $a_1$    & $\dots$ & $a_{x-1}$ & $x$ & $x$ & $\dots$ & $x$ \\
$t(A)$& $t(a_0)$ & $t(a_1)$ & $\dots$ &  $t(a_{x-1})$      & $x$ &
$x$ & $\dots$ & $x$
\end{tabular}
\end{center}

\ee

For $0 \le i \le n$, the index $i$ entry satisfies the following
properties: (i) it takes integer values; (ii) it is bounded above
by $i$; (iii) its value does not decrease under transformation
$t$; and (iv) once it stabilizes under transformation $t$, it
never changes again. This shows that no more than $n$ applications
of $t$ lead to a sequence that is stable under the transformation
$t$.

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 3 points for stating and proving this fact.}
\\
\hline
\end{tabular}
\end{center}

Finally, we need to show that no more than $n-1$ applications of
$t$ is needed to obtain a fixed sequence from an initial
$n+1$-term index bounded sequence $A = (a_0, a_1, \dots , a_n)$.
We induct on $n$.

For $n=1$, the two possible index bounded sequences $(a_0, a_1) =
(0, 0)$ and $(a_0, a_1) = (0, 1)$ are already fixed by $t$ so we
need zero applications of $t$.

Assume that any index bounded sequences $(a_0, a_1, \dots, a_n)$
reach a fixed sequence after no more than $n-1$ applications of
$t$. Consider an index bounded sequence $A = (a_0, a_1, \dots,
a_{n+1})$. It suffices to show that $A$ will be stabilized in no
more than $n$ applications of $t$. We approach indirectly by
assume on the contrary that $n+1$ applications of transformations
are needed. This can happen only if $a_{n+1}= 0$ and each
application of $t$ increased the index $n+1$ term by exactly 1.
Under transformation $t$, the resulting value of index term $i$
will not the effected by index term $j$ for $i < j$. Hence by the
induction hypothesis, the subsequence $A' = (a_0, a_1, \dots,
a_n)$ will be stabilized in no more than $n-1$ applications of
$t$. Because index $n$ term is stabilized at value $x \le n$ after
no more than $\min\{ x, n-1\}$ applications of $t$ and index $n+1$
term obtains value $x$ after $x$ exactly applications of $t$ under
our current assumptions. We conclude that the index $n+1$ term
would become equal to the index $n$ term after no more than $n-1$
applications of $t$. However, once two consecutive terms in a
sequence are equal they stay equal and stabilize together. Because
the index $n$ term needs no more than $n-1$ transformations to be
stabilized, $A$ can be stabilized in no more than $n-1$
applications of $t$, which contradicts our assumption of $n+1$
applications needed. Thus our assumption was wrong and we need at
most $n$ applications of transformation $t$ to stabilize an
$(n+1)$-term index bounded sequence. This completes our inductive
proof.

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 3 points for stating and proving this fact.}
\\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline \remark It seems that it is difficult to reaching later stages
of the proof without previous results. Possible marks for this problem
are 0, 1, 4, 7.
\\
\hline
\end{tabular}
\end{center}
\ee

%\vfill

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

%\begin{center}
%${\bf 32\2nd}$ {\bf United States of America Mathematical Olympiad} \\[.1in]
%{\bf Lincoln, Nebraska} \\ [.05in]
%{\bf Day II \hspace{.25in} 12:30 PM - 5:00 PM}\\[.05in]
%{\bf April 30, 2003}
%\end{center}

%\vspace*{.3in}

\be
\ii [4.]
%T2 and ZF, EMM
Let $ABC$ be a triangle. A circle passing through $A$ and $B$
intersects segments $AC$ and $BC$ at $D$ and $E$, respectively. Rays
$BA$ and $ED$ intersect at $F$ while lines $BD$ and $CF$ intersect at
$M$. Prove that $MF = MC$ if and only if $MB\cdot MD = MC^2$.

\first
Extend segment $DM$ through $M$ to $G$ such that $FG \parallel CD$.

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 1 point for constructing $G$.}
\\
\hline
\end{tabular}
\end{center}

\begin{figure}[htbp]
%\leavevmode \epsfxsize=2.5in \epsfysize=2.5in
\centering\epsfbox{usa03paf11.eps}
\end{figure}

Then $MF = MC$ if and only if quadrilateral $CDFG$ is a parallelogram,
or, $FD \parallel CG$. Hence $MC = MF$ if and only if $\ang GCD = \ang
FDA$, that is, $\ang FDA + \ang CGF = 180\dg$.

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 1 point for reducing side information to angle information.}
\\
\hline
\end{tabular}
\end{center}

Because quadrilateral $ABED$ is cyclic, $\ang FDA = \ang ABE$. It
follows that $MC = MF$ if and only if
\[
180\dg = \ang FDA + \ang CGF = \ang ABE + \ang CGF,
\]
that is, quadrilateral $CBFG$ is cyclic, which is equivalent to
\[
\ang CBM = \ang CBG = \ang CFG = \ang DCF = \ang DCM.
\]
Because $\ang DMC = \ang CMB$, $\ang CBM = \ang DCM$ if and only if
triangles $BCM$ and $CDM$ are similar, that is
\[
\frac{CM}{BM} = \frac{DM}{CM},
\]
or $MB\cdot MD = MC^2$.

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 5 points for completing the proof.}
\\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
\remark
The possible marks for this problem are 0, 1, 2, 7. This is not a
very hard geometry problem. If a student knows many facts but
cannot make final connections between the facts, he can only get
at most 2 points.
\\
\hline
\end{tabular}
\end{center}

\second

\begin{figure}[htbp]
%\leavevmode \epsfxsize=2.5in \epsfysize=2.5in
\centering\epsfbox{usa03paf12.eps}
\end{figure}

We first assume that $MB\cdot MD = MC^2$. Because $\frac{MC}{MD} =
\frac{MB}{MC}$ and $\ang CMD = \ang BMC$, triangles $CMD$ and $BMC$ are
similar. Consequently, $\ang MCD = \ang MBC$.

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 1 point for proving this fact.}
\\
\hline
\end{tabular}
\end{center}

Because quadrilateral $ABED$ is cyclic, $\ang DAE = \ang DBE$.
Hence
\[
\ang FCA = \ang MCD = \ang MBC = \ang DBE = \ang DAE = \ang CAE,
\]
implying that $AE\parallel CF$, so $\ang AEF = \ang CFE$. Because
quadrilateral $ABED$ is cyclic, $\ang ABD = \ang AED$. Hence
\[
\ang FBM = \ang ABD = \ang AED = \ang AEF = \ang CFE = \ang MFD.
\]
Because $\ang FBM = \ang DFM$ and $\ang FMB =
\ang DMF$, triangles $BFM$ and $FDM$ are similar. Consequently,
$\frac{FM}{DM} = \frac{BM}{FM}$, or $FM^2 = BM\cdot DM = CM^2$.
Therefore $MC^2 = MB\cdot MD$ implies $MC = MF$.

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 2 points for proving this part.}
\\
\hline
\end{tabular}
\end{center}

Now we assume that $MC = MF$. Applying {\bf Ceva's Theorem} to
triangle $BCF$ and {\bf cevians} $BM$, $CA$, $FE$ gives
\[
\frac{BA}{AF}\cdot\frac{FM}{MC}\cdot \frac{CE}{EB} = 1,
\]
implying that $\frac{BA}{AF} = \frac{BE}{EC}$, so $AE \parallel
CF$.

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 2 points for proving this fact.}
\\
\hline
\end{tabular}
\end{center}


Consequently, $\ang DCM = \ang DAE$. Because quadrilateral $ABED$
is cyclic, $\ang DAE = \ang DBE$. Hence
\[
\ang DCM = \ang DAE = \ang DBE = \ang CBM.
\]
Because $\ang CBM = \ang DCM$ and $\ang CMB = \ang DMC$, triangles
$BCM$ and $CDM$ are similar. Consequently, $\frac{CM}{DM} =
\frac{BM}{CM}$, or $CM^2 = BM\cdot DM$.

Combining the above, we conclude that $MF = MC$ if and only if $MB\cdot
MD = MC^2$.

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 2 points for proving this part.}
\\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
\remark
3 points for proving $MB\cdot MD = MC^2$ implying $MF = MC$; 4
points for $MF = MC$ implying $MB\cdot MD = MC^2$. Two partial
credits from different parts are not additive. A partial credits
in one part and a full mark in the other are not additive.
Possible marks are 0, 1, 2, 3 (only for completing the first
part), 4 (only for completing the second part), 7.
\\
\hline
\end{tabular}
\end{center}


\newpage
\ii [5.]
%T2 and ZF, MMH
Let $a, b, c$ be positive real numbers. Prove that
\[
\frac{(2a+b+c)^2}{2a^2+(b+c)^2} + \frac{(2b+c+a)^2}{2b^2+(c+a)^2} +
\frac{(2c+a+b)^2}{2c^2+(a+b)^2} \le 8.
\]

\first
%(Matthew Tang)
By multiplying $a, b$, and $c$ by a suitable factor, we
reduce the problem to the case when $a + b + c = 3$. The desired
inequality reads
\[
\frac{(a+3)^2}{2a^2+(3-a)^2} + \frac{(b+3)^2}{2b^2+(3-b)^2} +
\frac{(c+3)^2}{2c^2+(3-c)^2} \le 8.
\]

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 1 point for homogeneous approach and expressing $b+c$ in terms of
$a$.}
\\
\hline
\end{tabular}
\end{center}

Set
\[
f(x) = \frac{(x+3)^2}{2x^2+(3-x)^2}
\]
It suffices to prove that $f(a) + f(b) + f(c) \le 8$. Note that
\beqa
f(x) & = & \frac{x^2 + 6x + 9}{3(x^2 - 2x + 3)}
 = \frac{1}{3}\cdot \frac{x^2 + 6x + 9}{x^2 - 2x + 3} \\
& = & \frac{1}{3} \Lp 1 + \frac{8x + 6}{x^2 - 2x + 3} \Rp
 = \frac{1}{3} \Lp 1 + \frac{8x + 6}{(x-1)^2 + 2} \Rp \\
& \le & \frac{1}{3} \Lp 1 + \frac{8x + 6}{2} \Rp
 = \frac{1}{3} (4x + 4).
\eeqa
Hence,
\[
f(a) + f(b) + f(c) \le \frac{1}{3} (4a + 4 + 4b + 4 + 4c + 4) = 8,
\]
as desired.

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 6 points for completing the proof. No partial credits given in this
part.}
\\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline \remark The possible marks for this approach is 0, 1, 7.
\\
\hline
\end{tabular}
\end{center}

\second
%(Richard Stong)
Note that
\beqa
(2x+y)^2 + 2(x-y)^2 & = & 4x^2 + 4xy + y^2 + 2x^2 - 4xy +2y^2 \\
& = & 3(2x^2 + y^2).
\eeqa
Setting $x = a$ and $y = b+c$ yields
\[
(2a+b+c)^2 + 2(a-b-c)^2 = 3(2a^2+(b+c)^2).
\]
Thus, we have
\[
\frac{(2a+b+c)^2}{2a^2+(b+c)^2} = \frac{3(2a^2+(b+c)^2) -
2(a-b-c)^2}{2a^2+(b+c)^2} = 3 - \frac{2(a-b-c)^2}{2a^2+(b+c)^2}.
\]
and its analogous forms. Thus, the desired inequality is equivalent to
\[
\frac{(a-b-c)^2}{2a^2+(b+c)^2} + \frac{(b-a-c)^2}{2b^2+(c+a)^2} +
\frac{(c-a-b)^2}{2c^2+(a+b)^2} \ge \frac{1}{2}.
\]

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 3 points for transforming into this formation. Serious but
unsuccessful attempt to use $a$ and $b+c$ as two variables will be
awarded 1 point.}
\\
\hline
\end{tabular}
\end{center}

Because $(b+c)^2 \le 2(b^2+c^2)$, we have $2a^2+(b+c)^2\le
2(a^2+b^2+c^2)$ and its analogous forms. It suffices to show that
\[
\frac{(a-b-c)^2}{2(a^2+b^2+c^2)} + \frac{(b-a-c)^2}{2(a^2+b^2+c^2)} +
\frac{(c-a-b)^2}{2(a^2+b^2+c^2)} \ge \frac{1}{2},
\]
or,
$$
(a-b-c)^2 + (b-a-c)^2 + (c-a-b)^2 \ge a^2 + b^2 + c^2. \eqno{(1)}
$$

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 3 points for reducing to this inequality.}
\\
\hline
\end{tabular}
\end{center}

Multiplying this out the left-hand side of the last inequality
gives $3(a^2 + b^2 + c^2) - 2(ab+bc+ca)$. Therefore the inequality
(1) is equivalent to $2[a^2 + b^2 + c^2 - (ab+bc+ca)] \ge 0$,
which is evident because
\[
2[a^2 + b^2 + c^2 - (ab+bc+ca)] = (a-b)^2 + (b-c)^2 + (c-a)^2.
\]
Equalities hold if $(b+c)^2 = 2(b^2+c^2)$ and $(c+a)^2 = 2(c^2+a^2)$,
that is, $a = b = c$.

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 1 point for completing the proof.}
\\
\hline
\end{tabular}
\end{center}


\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline \remark Because the last step is only meaningful with previous
steps, the final 1 point will not be awarded to students if no evidence
why it is useful was provided. One the other hand, any serious attempt
to use $a$ and $b+c$ as two variables will be awarded 1 point. The
possible marks for this approach is 0, 1, 3, 6, 7.
\\
\hline
\end{tabular}
\end{center}

\third
Given a function $f$ of three variables, define the cyclic sum
\[
\cycsum f(p,q,r) = f(p,q,r) + f(q,r,p) + f(r,p,q).
\]
We first convert the inequality into
\[
\frac{2a(a+2b+2c)}{2a^2+(b+c)^2} + \frac{2b(b+2c+2a)}{2b^2+(c+a)^2} +
\frac{2c(c+2a+2b)}{2c^2+(a+b)^2} \le 5.
\]
Splitting the 5 among the three terms yields the equivalent form
$$
\cycsum \frac{4a^2 - 12a(b+c) + 5(b+c)^2}{3[2a^2 + (b+c)^2]} \ge 0.
\eqno{(2)}
$$

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 1 points for transforming into this formation.}
\\
\hline
\end{tabular}
\end{center}

The numerator of the term shown factors as $(2a-x)(2a-5x)$, where
$x = b+c$. We will show that
$$
\frac{(2a-x)(2a-5x)}{3(2a^2+x^2)} \ge -\frac{4(2a-x)}{3(a+x)}.
\eqno{(3)}
$$
Indeed, (3) is equivalent to
\[
(2a-x)[(2a-5x)(a+x) + 4(2a^2+x^2)] \ge 0,
\]
which reduces to
\[
(2a-x)(10a^2-3ax-x^2) = (2a-x)^2(5a+x) \ge 0,
\]
evident. We proved that
\[
\frac{4a^2 - 12a(b+c) + 5(b+c)^2}{3[2a^2 + (b+c)^2]} \ge
-\frac{4(2a-b-c)}{3(a+b+c)},
\]
hence (2) follows. Equality holds if and only if $2a=b+c$, $2b = c+a$,
$2c = a+b$, i.e., when $a = b = c$.


\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 6 points for transform into this formation.}
\\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline \remark The possible marks of this approach are 0, 1 and 7.
\\
\hline
\end{tabular}
\end{center}



\fourth
Given a function $f$ of three variables, we define the symmetric sum
\[
\ssum f(x_{1}, \dots, x_{n}) = \sum_{\sigma} f(x_{\sigma(1)}, \dots,
x_{\sigma(n)})
\]
where $\sigma$ runs over all permutations of $1, \dots, n$ (for a total
of $n!$ terms). For example, if $n = 3,$ and we write $x,y,z$ for
$x_{1}, x_{2}, x_{3},$
\begin{align*}
\ssum x^{3} &= 2x^{3} + 2y^{3} + 2z^{3} \\
\ssum x^{2}y &= x^{2}y + y^{2}z + z^{2}x + x^{2}z + y^{2}x + z^{2}y \\
\ssum xyz &= 6xyz.
\end{align*}
We combine the terms in the desired inequality over a common
denominator and use symmetric sum notation to simplify the algebra. The
numerator of the difference between the two sides is
\[
\ssum 8a^6 + 8 a^5 b + 2 a^4 b^2 + 10 a^4 b c + 10 a^3 b^3 - 52 a^3 b^2
c + 14 a^2 b^2 c^2.
\]

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 1 point for multiplying out correctly.}
\\
\hline
\end{tabular}
\end{center}

Recalling {\bf Schur's Inequality}, we have
\beqa
& & a^3 + b^3 + c^3 + 3abc - (a^2b+b^2c+c^a+ab^2+bc^2+ca^2) \\
& = & a(a-b)(a-c) + b(b-a)(b-c) + c(c-a)(c-b) \ge 0,
\eeqa
or
\[
\ssum a^3 - 2a^2b + abc \ge 0.
\]
Hence,
\[
0 \le 14abc \ssum a^3 - 2a^2b + abc = 14 \ssum a^4 bc - 28 a^3 b^2
c + 14 a^2 b^2 c^2
\]

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 3 points for proving this inequality.}
\\
\hline
\end{tabular}
\end{center}

and by repeated {\bf AM-GM Inequality},
\[
0 \le \ssum 4a^6 - 4 a^4 bc
\]
(because $a^46 + a^6 + a^6 + a^6 + b^6 + c^6 \ge 6a^4bc$ and its
analogous forms)
\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 1 point for proving this inequality.}
\\
\hline
\end{tabular}
\end{center}

and
\[
0 \leq \ssum 4a^6 + 8a^5b + 2a^4 b^2 + 10 a^3b^3 - 24 a^3 b^2 c.
\]

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 2 points for proving this inequality.}
\\
\hline
\end{tabular}
\end{center}

Adding these three inequalities yields the desired result.

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
\remark
In this approach, we have $1+1 = 2$ and the other partial credits
are not additive. (Indeed, because the last two inequalities are
in very artificial forms, it is almost impossible to state and
prove them with the third to last inequality.) The possible marks
for this approaches are 0, 1, 2, 3, 7.
\\
\hline
\end{tabular}
\end{center}

\newpage
\ii [6.]
% BAR3, MHH
At the vertices of a regular hexagon are written six nonnegative
integers whose sum is 2003. Bert is allowed to make moves of the
following form: he may pick a vertex and replace the number written
there by the absolute value of the difference between the numbers
written at the two neighboring vertices. Prove that Bert can make a
sequence of moves, after which the number 0 appears at all six
vertices.

\note
Let
\[
\hex ABCDEF
\]
denote a position, where $A, B, C, D, E, F$ denote the numbers written
on the vertices of the hexagon. We write
\[
\hex ABCDEF \pmod{2}
\]
if we consider the numbers written modulo 2.

\soln
Define the \textit{sum} and \textit{maximum} of a position to be the
sum and maximum of the six numbers at the vertices.  We will show that
from any position in which the sum is odd, it is possible to reach the
all-zero position.

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 1 point for making this claim.}
\\
\hline
\end{tabular}
\end{center}

Our strategy alternates between two steps:
\be
\ii[(a)]
from a position with odd sum, move to a position with exactly one odd
number;
\ii[(b)]
from a position with exactly one odd number, move to a position with
odd sum and strictly smaller maximum, or to the all-zero position.
\ee
Note that no move will ever increase the maximum, so this strategy is
guaranteed to terminate, because each step of type (b) decreases the
maximum by at least one, and it can only terminate at the all-zero
position. It suffices to show how each step can be carried out.

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 2 points for making this claim.}
\\
\hline
\end{tabular}
\end{center}

First, consider a position
\[
\hex ABCDEF
\]
with odd sum.  Then either $A + C + E$ or $B + D + F$ is odd; assume
without loss of generality that $A + C + E$ is odd. If exactly one of
$A$, $C$ and $E$ is odd, say $A$ is odd, we can make the sequence of
moves
\[
\hex 1B0D0F \to \hex 1{\bf 1}0{\bf 0}0{\bf 1} \to \hex {\bf 0}10001 \to
\hex 01000{\bf 0} \pmod{2},
\]
where a letter or number in boldface represents a move at that vertex,
and moves that do not affect each other have been written as a single
move for brevity.  Hence we can reach a position with exactly one odd
number. Similarly, if $A$, $C$, $E$ are all odd, then the sequence of
moves
\[
\hex 1B1D1F \to \hex 1{\bf 0}1{\bf 0}1{\bf 0} \to \hex 10{\bf 0}0{\bf
0}0 \pmod{2},
\]
brings us to a position with exactly one odd number.  Thus we have
shown how to carry out step (a).

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 2 points for proving this part.}
\\
\hline
\end{tabular}
\end{center}

Now assume that we have a position
\[
\hex ABCDEF
\]
with $A$ odd and all other numbers even. We want to reach a position
with smaller maximum. Let $M$ be the maximum.  There are two cases,
depending on the parity of $M$.
\be
\ii[$\bullet$]
In this case, $M$ is even, so one of $B$, $C$, $D$, $E$, $F$ is the
maximum.  In particular, $A < M$.

We claim after making moves at $B$, $C$, $D$, $E$, and $F$ in that
order, the sum is odd and the maximum is less than $M$. Indeed, the
following sequence
\[
\hex 100000 \to \hex 1{\bf 1}0000 \to \hex 11{\bf 1}000 \to \hex
111{\bf 1}00 \to \hex 1111{\bf 1}0 \to \hex 11111{\bf 0} \pmod{2}.
\]
shows how the numbers change in parity with each move. Call this new
position \hex {A'}{B'}{C'}{D'}{E'}{F'}.  The sum is odd, since there
are five odd numbers.  The numbers $A'$, $B'$, $C'$, $D'$, $E'$ are all
less than $M$, since they are odd and $M$ is even, and the maximum can
never increase.  Also, $F' = |A' - E'| \le \max \{A', E'\} < M$.  So
the maximum has been decreased.

\ii[$\bullet$]
In this case, $M$ is odd, so $M = A$ and the other numbers are all less
than $M$.

If $C > 0$, then we make moves at $B$, $F$, $A$, and $F$, in that
order. The sequence of positions is
\[
\hex 100000 \to \hex 1{\bf 1}0000 \to \hex 11000{\bf 1} \to \hex {\bf
0}10001 \to \hex 01000{\bf 0} \pmod{2}.
\]
Call this new position $\hex {A'}{B'}{C'}{D'}{E'}{F'}$.  The sum is
odd, since there is exactly one odd number.  As before, the only way
the maximum could not decrease is if $B' = A$; but this is impossible,
since $B' = |A - C| < A$ because $0 < C < M = A$.  Hence we have
reached a position with odd sum and lower maximum.

If $E > 0$, then we apply a similar argument, interchanging $B$ with
$F$ and $C$ with $E$.

If $C = E = 0$, then we can reach the all-zero position by the
following sequence of moves:
\[
\hex AB0D0F \to \hex A{\textbf{\textit{A}}}0{\bf
0}0{\textbf{\textit{A}}} \to \hex {\bf 0}A000A \to \hex 0{\bf 0}000{\bf
0}.
\]
(Here 0 represents zero, not any even number.)
\ee
Hence we have shown how to carry out a step of type (b), proving the
desired result.  The problem statement follows since $2003$ is odd.

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 2 points for proving this part.}
\\
\hline
\end{tabular}
\end{center}

\note
Observe that from positions of the form
\[
\hex 011011\quad\pmod{2}\qquad\hbox{or rotations}
\]
it is impossible to reach the all-zero position, because a move at any
vertex leaves the same value modulo 2.  Dividing out the greatest
common divisor of the six original numbers does not affect whether we
can reach the all-zero position, so we may assume that the numbers in
the original position are not all even.  Then by a more complete
analysis in step (a), one can show from any position not of the above
form, it is possible to reach a position with exactly one odd number,
and thus the all-zero position.  This gives a complete characterization
of positions from which it is possible to reach the all-zero position.

There are many ways to carry out the case analysis in this problem; the
one used here is fairly economical.  The important idea is the
formulation of a strategy that decreases the maximum value while
avoiding the ``bad'' positions described above.

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
\remark
Partial credits are not additive. 1 point will be rewarded for
somewhat applying a maximum value argument. 3 points will be
awarded for stating the strategies clearly and carrying out some
significant progress in proving the strategies can indeed be
realized, in other words, $2 + 2 = 3$. Possible marks for this
approach are 0, 1, 2, 3, 6/7. (Because this problem requires
strong combinatorial argument skill, 6 points can be rewarded to
solutions with minimum errors. On the other hand, a score of 5
points shall be very extremely special, if not possible.)
\\
\hline
\end{tabular}
\end{center}


\second
%Richard Stong
We will show that if there is a pair of opposite vertices with odd
sum (which of course is true if the sum of all the vertices is
odd), then we can reduce to a position of all zeros.

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 1 point for making this claim.}
\\
\hline
\end{tabular}
\end{center}

Focus on such a pair $(a,d)$ with smallest possible $\max(a,d)$.
We will show we can always reduce this smallest maximum of a pair
of opposite vertices with odd sum or reduce to the all-zero
position. Because the smallest maximum takes nonnegative integer
values, we must be able to achieve the all-zero position.

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 1 point for making this claim.}
\\
\hline
\end{tabular}
\end{center}

To see this assume without loss of generality that $a \ge d$ and
consider an arc $(a,x,y,d)$ of the position
\[
\hex axyd**
\]
Consider updating $x$ and $y$ alternately, starting with $x$. If
$\max(x,y)>a$, then in at most two updates we reduce $\max(x,y)$. Thus,
we can repeat this {\em alternate updating} process and we must
eventually reach a point when $\max(x,y)\le a$, and hence this will be
true from then on.

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 1 point for applying this process.}
\\
\hline
\end{tabular}
\end{center}

Under this alternate updating process, the arc of the hexagon will
eventually enter an unique cycle of length four modulo 2 in at
most one update. Indeed, we have
\[
\hex 1000** \to \hex 1{\bf 1}00** \to \hex 11{\bf 1}0**\to \hex 1{\bf
0}10** \to \hex 10{\bf 0}0** \pmod{2}
\]
and
\[
\begin{array}{ll}
\hex 1000** \to \hex 10{\bf 0}0** \pmod{2}; & \hex 1100** \to \hex
1{\bf 1}00** \pmod{2} \\
\\
\hex 1110** \to \hex 11{\bf 1}0** \pmod{2};
& \hex 1010** \to \hex 1{\bf 0}10** \pmod{2},
\end{array}
\]
or
\[
\hex 0011** \to \hex 0{\bf 1}11** \to \hex 01{\bf 0}1**\to \hex 0{\bf
0}01** \to \hex 00{\bf 1}1** \pmod{2}
\]
and
\[
\begin{array}{ll}
\hex 0001** \to \hex 0{\bf 0}01** \pmod{2}; & \hex 0011** \to \hex
00{\bf 1}1** \pmod{2} \\
\\
\hex 0111** \to \hex 0{\bf 1}01** \pmod{2};
& \hex 0101** \to \hex 01{\bf 0}1** \pmod{2}.
\end{array}
\]
Further note that each possible parity for $x$ and $y$ will occur
equally often.

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 2 points for proving this part.}
\\
\hline
\end{tabular}
\end{center}

Applying this alternate updating process to both arcs $(a, b, c,
d)$ and $(a, e, f, d)$ of
\[
\hex abcdef,
\]
we can make the other four entries be at most $a$ and control their
parity. Thus we can create a position
\[
\hex a{x_1}{x_2}d{x_4}{x_5}
\]
with $x_i+x_{i+3}$ ($i = 1, 2$) odd and $M_i = \max(x_i,x_{i+3})
\le a$. In fact, we can have $m = \min(M_1, M_2) < a$, as claimed,
unless both arcs enter a cycle modulo 2 where the values congruent
to $a$ modulo 2 are always exactly $a$. More precisely, because
the sum of $x_i$ and $x_{i+3}$ is odd, one of them is not
congruent to $a$ and so has its value strictly less than $a$. Thus
both arcs must pass through the state $(a,a,a,d)$ (modulo 2, this
is either $(0, 0, 0, 1)$ or $(1, 1, 1, 0)$) in a cycle of length
four. It is easy to check that for this to happen, $d = 0$.
Therefore, we can achieve the position
\[
\hex aaa0aa.
\]
From this position, the sequence of moves
\[
\hex aaa0aa \to \hex a{\bf 0}a0a{\bf 0} \to \hex {\bf 0}0{\bf 0}0{\bf
0}0
\]
completes the task.

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
{\bf 2 points for proving this part.}
\\
\hline
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{|p{5.0in}|}
\hline
\remark
For this approach, we have the following addition rule: $1+1 = 2$
(as both of the first two claims are quiet insightful), $1 + 1 + 1
= 2$, $1 + 2 = 2$ (which seems hard to be realized), $1 + 1 + 2 =
1 + 1 + 1 + 2 = 3$. The possible marks for this approach are 0, 1,
2, 3, 6/7. (Because this problem requires strong combinatorial
argument skill, 6 points can be rewarded to solutions with minimum
errors. On the other hand, a score of 5 points shall be very
extremely special, if not possible.)
\\
\hline
\end{tabular}
\end{center}

\ee


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