\documentclass[12pt]{article}
\usepackage{amssymb, latexsym, amsmath, amsthm, graphicx}
\usepackage{epic, eepic}
\usepackage[all]{xy}
\pagestyle{plain} \setlength{\oddsidemargin}{-.3in}
\setlength{\evensidemargin}{-.3in} \setlength{\textwidth}{6.75in}
\setlength{\textheight}{8.5in} \setlength{\topmargin}{.2in}
\setlength{\headheight}{0in} \setlength{\headsep}{0in}
\setlength{\parskip}{25pt} \setlength{\labelsep}{10pt}
\setlength{\parindent}{0pt} \setlength{\medskipamount}{.1in}
\setlength{\smallskipamount}{1ex}
\def\RR{{\mathbb R}}
\def\ZZ{{\mathbb Z}}
\newtheorem*{lemma}{Lemma}
\newtheorem{fact}{Proposition}
\def\arc{\widehat}
\newcommand\dg{\raisebox{.15pt}{$^{\circ}$}}
\def\th{^{\mbox{\scriptsize th}}}
\begin{document}
\setlength{\baselineskip}{.25in}
\begin{center}
${\bf 37th}$ \textbf{United States of America Mathematical
Olympiad}
\end{center}
\begin{enumerate}

\item
 Prove that for each positive integer $n$, there are pairwise
relatively prime integers $k_0,k_1,\ldots, k_n$, all strictly
greater than $1$, such that $k_0k_1\cdots k_n-1$ is the product of
two consecutive integers.

\medskip

{\bf First solution:}  We proceed by induction. The case $n=1$ is
clear, since we may pick $k_0=3$ and $k_1=7$.

Let us assume now that for a certain $n$ there are pairwise
relatively prime integers $1<k_0<k_1<\cdots <k_n$ such that
$k_0k_1\cdots k_n-1= a_n(a_n-1)$, for some positive integer $a_n$.
Then choosing $k_{n+1}=a_n^2+a_n+1$ yields
\begin{eqnarray*}
k_0k_1\cdots k_{n+1}=(a_n^2-a_n+1)(a_n^2+a_n+1)=a_n^4+a_n^2+1,
\end{eqnarray*}
so $k_0k_1\cdots k_{n+1} - 1$ is the product of the two
consecutive integers $a_n^2$ and $a_n^2+1$. Moreover,
\begin{eqnarray*}
\mbox{gcd}(k_0k_1\cdots k_n,k_{n+1})=
\mbox{gcd}(a_n^2-a_n+1,a_n^2+a_n+1)=1,
\end{eqnarray*}
hence $k_0,k_1,\ldots, k_{n+1}$ are pairwise relatively prime.
This completes the proof. \hspace*{\fill} $\qedsymbol$

\medskip

{\bf Second solution:} Write the relation to be proved as
\begin{eqnarray*}
4k_0k_1\cdots k_n=4a(a+1)+4=(2a+1)^2+3.
\end{eqnarray*}
There are infinitely many primes for which $-3$ is a quadratic
residue. Let $2<p_0<p_1<\ldots< p_n$ be such primes. Using the
Chinese Remainder Theorem to specify $a $ modulo $p_n$, we can
find an integer  $a$ such that $(2a+1)^2+3=4p_0p_1\cdots
p_nm$ for some positive integer $m$. Grouping the factors of $m$
appropriately with the $p_i$'s, we obtain
$(2a+1)^2+3=4k_0k_1\cdots k_n$ with $k_i$ pairwise relatively
prime. We then have $k_0k_1\cdots k_n-1=a(a+1)$, as desired.
\hspace*{\fill} $\qedsymbol$
\medskip

 {\bf Third solution:} We are supposed to show that for
every positive integer $n$, there is a positive integer $x$ such
that $x(x+1)+1=x^2+x+1$ has at least $n$ distinct prime divisors.
We can actually prove a more general statement.

\medskip

\noindent {\bf Claim.} {\em Let $P(x)=a_dx^d+\cdots +a_1x+1$ be a
polynomial of degree $d\geq 1$ with integer coefficients. Then for
every positive integer $n$, there is a positive integer $x$ such
that $P(x)$ has at least $n$ distinct prime divisors.}

\medskip

The proof follows from  the following two lemmas.

\medskip

\noindent {\bf Lemma 1.} {\em The set
\begin{eqnarray*}
Q=\{p\, |\, p \mbox{ a prime for which there is an integer }x
\mbox{ such that } p \mbox{ divides }P(x)\}
\end{eqnarray*}
is infinite. }

\begin{proof} The proof is analogous to Euclid's proof that
there are infinitely many primes. Namely, if we assume that there
are only finitely many primes $p_1,p_2,\ldots, p_k$ in $Q$,
then for each integer $m$, $P(m p_1 p_2 \cdots p_k)$ is an integer
with no prime factors, which must equal $1$ or $-1$.
However, since $P$ has degree $d \geq 1$, it takes each of the values
$1$ and $-1$ at most $d$ times, a contradiction.
\end{proof}

\medskip

\noindent {\bf Lemma 2.} {\em  Let $p_1,p_2,\ldots, p_n$, $n\geq
1$
 be  primes in $Q$.
 Then there is a positive
integer $x$ such that $P(x)$ is divisible by $p_1p_2\cdots p_n$.}

\begin{proof} For $i=1,2,\ldots, n$, since $p_i\in Q$ we can
find an integer  $c_i$ such that $P(x) $ is divisible by $p_i$
whenever $x\equiv c_i (\mbox{mod }p_i)$. By the Chinese Remainder
Theorem, the system of $n$ congruences $x\equiv c_i(\mbox{mod }
p_i)$, $i=1,2,\ldots, n$ has positive integer solutions. For every
positive integer $x$ that solves this system, $P(x)$ is divisible
by $p_1p_2\cdots p_n$. \end{proof}

 This problem was suggested by Titu Andreescu.


\item  Let $ABC$ be an  acute, scalene triangle, and let $M,\,N$,
and $P$ be the midpoints of $\overline{BC},\,\overline{CA}$, and
$\overline{AB}$, respectively. Let the perpendicular bisectors of
$\overline{AB}$ and $\overline{AC}$ intersect ray $AM$ in points
$D$ and $E$ respectively, and let lines $BD$ and $CE$ intersect in
point  $F$, inside of  triangle $ABC$.   Prove that points
$A,\,N,\,F$, and $P$ all lie on one circle.

\medskip

{\bf First solution:} Let $O$ be the circumcenter of triangle
$ABC$.  We prove that
$$\angle APO=\angle ANO=\angle AFO=90^{\circ}.\eqno{(1)}$$ It will
then follow that $A,\,P,\,O,\,F,\,N$ lie on the circle with
diameter $\overline{AO}$.  Indeed, the fact that the first two
angles in (1) are right is immediate because $\overline{OP}$ and
$\overline{ON}$ are the perpendicular bisectors of $\overline{AB}$
and $\overline{AC}$, respectively.  Thus we need only prove that
$\angle AFO=90^{\circ}$.


\begin{center}
\scalebox{2.5}{
%\fbox{
\includegraphics[clip,viewport=0 10 150
105]{Feng3.1.eps}}
% }
\end{center}

\begin{center}
\scalebox{2.5}{ %\fbox{
\includegraphics[clip,viewport=205 10 355
110]{Feng3.1.eps}}
% }
\end{center}

\noindent We may assume, without loss of generality, that $AB>AC$.
This leads to configurations similar to the ones shown above. The
proof can be adapted to other configurations.  Because $PO$ is the
perpendicular bisector of $AB$, it follows that triangle $ADB$ is
an isosceles triangle with $AD=BD$.  Likewise, triangle $AEC$ is
isosceles with $AE=CE$.  Let $x=\angle ABD=\angle BAD$ and
$y=\angle CAE=\angle ACE$, so $x+y=\angle BAC$.


Applying the Law of Sines to triangles $ABM$ and $ACM$ gives
\[
\frac{BM}{\sin x}= \frac{AB}{\sin\angle BMA}
\qquad\hbox{and}\qquad \frac{CM}{\sin y}=\frac{AC}{\sin\angle
CMA}.
\]
Taking the quotient of the two equations and noting that
$\sin\angle BMA=\sin\angle CMA$ we find
\[
\frac{BM}{CM} \frac{\sin y}{\sin x}=\frac{AB}{AC} \frac{\sin\angle
CMA}{\sin\angle BMA}= \frac{AB}{AC}. \] Because $BM=MC$, we have
\[
\frac{\sin x}{\sin y}= \frac{AC}{AB}.\eqno{(2)} \]  Applying the
law of sines to triangles $ABF$ and $ACF$ we find \[
\frac{AF}{\sin x}= \frac{AB}{\sin\angle AFB}
\qquad\hbox{and}\qquad \frac{AF}{\sin y}=\frac{AC}{\sin\angle
AFC}. \] Taking the quotient of the two equations yields
\[
\frac{\sin x}{\sin y}=\frac{AC}{AB} \frac{\sin\angle
AFB}{\sin\angle AFC},\qquad\hbox{so by (2),} \qquad \sin\angle
AFB=\sin\angle AFC.\eqno{(3)} \] Because $\angle ADF$ is an
exterior angle to triangle $ADB$, we have $\angle EDF=2x$.
Similarly, $\angle DEF=2y$.  Hence
$$\angle EFD=180^{\circ}-2x-2y=180^{\circ}-2\angle BAC.$$ Thus
$\angle BFC=2\angle BAC=\angle BOC$, so $BOFC$ is cyclic.  In
addition,
$$\angle AFB+\angle AFC=360^{\circ}-2\angle BAC>180^{\circ},$$ and
hence, from (3), $\angle AFB=\angle AFC=180^{\circ}-\angle BAC$.
Because $BOFC$ is cyclic and $\triangle BOC$ is isosceles with
vertex angle $\angle BOC=2\angle BAC$, we have $\angle OFB=\angle
OCB=90^{\circ}-\angle BAC$.  Therefore,
$$\angle AFO=\angle AFB-\angle OFB=(180^{\circ}-\angle
BAC)-(90^{\circ }-\angle BAC)=90^{\circ}.$$ This completes the
proof. \hspace*{\fill} $\qedsymbol$

\medskip

{\bf Second solution:}  Invert the figure about a circle centered at
$A$, and let $X'$ denote the image of the point $X$ under this
inversion. Find point $F_1'$ so that $AB'F_1'C'$ is a parallelogram
and let $Z'$ denote the center of this parallelogram. Note that
$\triangle BAC\sim\triangle C'AB'$ and $\triangle BAD\sim\triangle
D'AB'$.  Because $M$ is the midpoint of $BC$ and $Z'$ is the
midpoint of $B'C'$, we also have $\triangle BAM\sim\triangle C'AZ'$.
Thus
$$\angle AF_1'B'=\angle F_1'AC'=\angle Z'AC'=\angle MAB=\angle
DAB=\angle DBA=\angle AD'B'.$$ Hence quadrilateral $AB'D'F_1'$ is
cyclic and, by a similar argument, quadrilateral $AC'E'F_1'$ is
also cyclic.  Because the images under the inversion  of lines
$BDF$ and $CFE$ are circles that intersect in $A$ and $F'$, it
follows that $F_1'=F'$.

Next note that $B',\,Z'$, and $C'$ are collinear and are the
images of $P',\,F'$, and $N'$, respectively, under a homothety
centered at $A$ and with ratio $1/2$. It follows that $P',\,F'$
and $N'$ are collinear, and then that the points $A,\,P,\,F$ and
$N$ lie on a circle. \hspace*{\fill} $\qedsymbol$

\begin{center}
\scalebox{2.5}{
\includegraphics{Feng3.1Alt.eps}}
\end{center}

This problem was suggested by Zuming Feng. The second solution was
contributed by Gabriel Carroll.

\item  Let $n$ be a positive integer. Denote by $S_n$ the set of
points $(x,y)$ with integer coordinates such that
\[ |x| + \left|y+\frac{1}{2}\right|  < n. \]
A \emph{path} is a sequence of distinct points $(x_1,y_1),(x_2,y_2),
\dots,(x_\ell,y_\ell)$ in $S_n$ such that, for $i=2,\dots,\ell$, the
distance between $(x_i,y_i)$ and $(x_{i-1},y_{i-1})$ is 1 (in other words,
the points $(x_i,y_i)$ and $(x_{i-1},y_{i-1})$ are neighbors in the lattice
of points with integer coordinates).

Prove that the points in $S_n$ cannot be partitioned into fewer
than $n$ paths (a partition of $S_n$ into $m$ paths is a set
$\mathcal P$ of $m$ nonempty paths such that each point in $S_n$
appears in exactly one of the $m$ paths in $\mathcal P$).

\medskip

{\bf Solution:} Color the points in $S_n$ as follows (see
Figure~\ref{f:coloring}):
\begin{enumerate}
\item[-] if $y \geq 0$, color $(x,y)$ white if $x+y-n$ is even and black if $x+y-n$ is odd;
\item[-] if $y < 0$, color $(x,y)$ white if $x+y-n$ is odd and black if $x+y-n$ is even.
\end{enumerate}
\begin{figure}[!hb]
\[
\xymatrix{
 &&&&
 \bullet \ar@{-}[d] \ar@{}[drr]|<<<<{(0,2)} &&&&
 \\
 &&&
 \bullet \ar@{-}[r]\ar@{-}[d] \ar@{}[drr]|<<<<{(-1,1)}&
 \circ \ar@{-}[r]\ar@{-}[d] \ar@{}[drr]|<<<<{(0,1)}&
 \bullet \ar@{-}[d] \ar@{}[drr]|<<<<{(1,1)} &&&
 \\
 &&
 \bullet \ar@{-}[r]\ar@{-}[d] \ar@{}[drr]|<<<<{(-2,0)}&
 \circ \ar@{-}[r]\ar@{-}[d] \ar@{}[drr]|<<<<{(-1,0)}&
 \bullet \ar@{-}[r]\ar@{-}[d] \ar@{}[drr]|<<<{(0,0)}&
 \circ \ar@{-}[r]\ar@{-}[d] \ar@{}[drr]|<<<<{(1,0)}&
 \bullet \ar@{-}[d] \ar@{}[drr]|<<<<{(2,0)} &&
 \\
 &&
 \bullet \ar@{-}[r] \ar@{}[drr]|<<<<{(-2,-1)}&
 \circ \ar@{-}[r]\ar@{-}[d] \ar@{}[drr]|<<<<{(-1,-1)}&
 \bullet \ar@{-}[r]\ar@{-}[d] \ar@{}[drr]|<<<<{(0,-1)}&
 \circ \ar@{-}[r]\ar@{-}[d] \ar@{}[drr]|<<<<{(1,-1)}&
 \bullet \ar@{}[drr]|<<<<{(2,-1)} &&
 \\
 &&&
 \bullet \ar@{-}[r] \ar@{}[drr]|<<<<{(-1,-2)}&
 \circ \ar@{-}[r]\ar@{-}[d] \ar@{}[drr]|<<<<{(0,-2)}&
 \bullet \ar@{}[drr]|<<<<{(1,-2)} &&&
 \\
 &&&&
 \bullet \ar@{}[rr]|<<<<{(0,-3)} &&&&
}
\]
\caption{Coloring of $S_3$}
\label{f:coloring}
\end{figure}

Consider a path $(x_1,y_1),(x_2,y_2),\dots,(x_\ell,y_\ell)$ in $S_n$.
A pair of successive points $(x_{i-1},y_{i-1})$ and $(x_i,y_i)$ in the
path is called a pair of successive black points if both points in the
pair are colored black.

Suppose now that the points of $S_n$ are partitioned into $m$
paths and the total number of successive pairs of black points in
all paths is $k$. By breaking the paths at each pair of successive
black points, we obtain $k+m$ paths in each of which the number of
black points exceeds the number of white points by at most one.
Therefore, the total number of black points in $S_n$ cannot exceed
the number of white points by more than $k+m$. On the other hand,
the total number of black points in $S_n$ exceeds the total number
of white points by exactly $2n$ (there is exactly one more black
point in each row of $S_n$). Therefore,
\[ 2n \leq k+m. \]
 There are exactly $n$ adjacent black points in $S_n$ (call two
points in $S_n$ \emph{adjacent} if their distance is 1), namely
the pairs
\[ (x,0) \text{ and } (x,-1), \]
for $x=-n+1,-n+3,\dots,n-3,n-1$. Therefore $k \leq n$ (the
number of successive pairs of black points in the paths in
the partition of $S_n$ cannot exceed the total number of
adjacent pairs of black points in $S_n$) and we have
$2n \leq k + m \leq n+m$, yielding
\[ n \leq m. \qedhere \]
\hspace*{\fill} $\qedsymbol$

This problem was suggested by Gabriel Carroll.

 \item Let
$\mathcal{P}$ be a convex polygon with $n$ sides, $n \ge 3$. Any
set of $n-3$ diagonals of $\mathcal{P}$ that do not intersect in
the interior of the polygon determine a {\em triangulation} of
$\mathcal{P}$ into $n-2$ triangles. If $\mathcal{P}$ is regular
and there is a triangulation of $\mathcal{P}$ consisting of only
isosceles triangles, find all the possible values of $n$.

\medskip

{\bf Solution:}
 The answer is $n = 2^{m+1} + 2^{k}$, where $m$ and $k$ are
nonnegative integers. In other words, $n$ is either a power of $2$
(when $m + 1= k$) or the sum of two nonequal powers of 2 (with $1
= 2^0$ being considered as a power of 2).

We start with the following observation.

\textbf{Lemma.} {\em Let $\mathcal{Q} = Q_0Q_1\dots
Q_t$ be a convex polygon with
$Q_0Q_1 = Q_1Q_2 = \cdots = Q_{t-1}Q_t$. Suppose that
$\mathcal{Q}$ is cyclic and its circumcenter does not lie in its
interior. If there is a triangulation of $\mathcal{Q}$ consisting only
of isosceles triangles, then $t = 2^a$, where $a$ is a positive
integer.}

\begin{proof} We call an arc {\em minor} if its arc
measure is less than or equal to $180\dg$. By the given conditions,
points $Q_1, \dots , Q_{t-1}$ lie on the minor arc $\arc{Q_0Q_t}$ of
the circumcircle, so none of the angles $Q_iQ_jQ_k$ ($0\le i < j <
k\le t$) is acute. (See the left-hand side diagram shown below.)
It is not difficult to see that $Q_0Q_t$ is longer than each other
side or diagonal of $\mathcal{Q}$. Thus $Q_0Q_t$ must be the base of
an isosceles triangle in the triangulation of $\mathcal{Q}$.
Therefore, $t$ must be even. We write $t = 2s$. Then $Q_0Q_sQ_t$
is an isosceles triangle in the triangulation. We can apply the
same process to polygon $Q_0Q_1\dots Q_s$ and show that $s$ is
even. Repeating this process leads to the conclusion that $t =
2^a$ for some positive integer $a$.

The results of the lemma can be generalized by allowing $a = 0$ if
we consider the degenerate case $\mathcal{Q} = Q_0Q_1$.
\end{proof}

\begin{center}\scalebox{1.25}{
\includegraphics{gal082.eps}}
\end{center}

We are ready to prove our main result. Let $\mathcal{P} =
P_1P_2\dots P_n$ denote the regular polygon. There is an isosceles
triangle in the triangulation such that the center of
$\mathcal{P}$ lies within the boundary of the triangle. Without
loss of generality, we may assume that $P_1P_iP_j$, with $P_1P_i =
P_1P_j$ (that is, $P_j = P_{n-i+2}$), is this triangle. Applying
the Lemma to the polygons $P_1\dots P_i$, $P_i\dots P_j$, and
$P_j\dots P_1$, we conclude that there are $2^m-1$, $2^k-1$,
$2^m-1$ (where $m$ and $k$ are nonnegative integers) vertices in
the interiors of the minor arcs $\arc{P_1P_i}$, $\arc{P_iP_j}$,
$\arc{P_jP_1}$, respectively. (In other words, $i = 2^m+1$, $j =
2^k+i$.) Hence
\[
n = 2^m-1 + 2^k-1 + 2^m -1 + 3 = 2^{m+1} + 2^{k},
\]
where $m$ and $k$ are nonnegative integers. The above discussion
can easily lead to a triangulation consisting of only isosceles
triangles for $n = 2^{m+1} + 2^k$. (The middle diagram shown above
illustrates the case $n = 18 = 2^{3+1} + 2^1$. The right-hand side
diagram shown above illustrates the case $n = 16 = 2^{2+1} +
2^3$.) \hspace*{\fill} $\qedsymbol$

This problem was suggested by Gregory Galperin.




\item Three nonnegative real numbers $r_1$, $r_2$, $r_3$ are
written on a blackboard. These numbers have the property that
there exist integers $a_1$, $a_2$, $a_3$, not all zero, satisfying
$a_1r_1+a_2r_2+a_3r_3=0$. We are permitted to perform the
following operation: find two numbers $x$, $y$ on the blackboard
with $x\le y$, then erase $y$ and write $y-x$ in its place. Prove
that after a finite number of such operations, we can end up with
at least one $0$ on the blackboard.

\medskip

{\bf Solution:} If two of the $a_i$ vanish, say $a_2$ and $a_3$,
then $r_1$ must be zero and we are done. Assume at most one $a_i$
vanishes. If any one $a_i$ vanishes, say $a_3$, then
$r_2/r_1=-a_1/a_2$ is a nonnegative rational number. Write this
number in lowest terms as $p/q$, and put $r=r_2/p=r_1/q$. We can
then write $r_1=qr$ and $r_2=pr$. Performing the Euclidean
algorithm on $r_1$ and $r_2$ will ultimately leave $r$ and $0$ on
the blackboard. Thus we are done again.

Thus it suffices to consider the case where none of the $a_i$
vanishes. We may also assume none of the $r_i$ vanishes, as
otherwise there is nothing to check. In this case we will show
that we can perform an operation to obtain $r_1^{\prime}$,
$r_2^{\prime}$, $r_3^{\prime}$ for which either one of
$r_1^{\prime}$, $r_2^{\prime}$, $r_3^{\prime}$ vanishes, or there
exist integers $a_1^{\prime}$, $a_2^{\prime}$, $a_3^{\prime}$, not
all zero, with
$a_1^{\prime}r_1^{\prime}+a_2^{\prime}r_2^{\prime}+a_3^{\prime}r_3^{\prime}=0$
and
$$\vert a_1^{\prime}\vert + \vert a_2^{\prime}\vert +\vert a_3^{\prime}\vert <
\vert a_1\vert +\vert a_2\vert +\vert a_3\vert.$$ After finitely
many steps we must arrive at a case where one of the $a_i$
vanishes, in which case we finish as above.

If two of the $r_i$ are equal, then we are immediately done by
choosing them as $x$ and $y$. Hence we may suppose
$0<r_1,r_2<r_3$. Since we are free to negate all the $a_i$, we may
assume $a_3>0$. Then either $a_1<-\frac{1}{2}a_3$ or
$a_2<-\frac{1}{2}a_3$ (otherwise $a_1r_1+a_2r_2+a_3r_3>
(a_1 + \frac{1}{2}a_3)r_1 + (a_2 + \frac{1}{2}a_3)r_2 > 0$).
Without loss of generality, we may assume
$a_1<-\frac{1}{2}a_3$. Then choosing $x=r_1$ and
$y=r_3$ gives the triple
$(r_1^{\prime},r_2^{\prime},r_3^{\prime})=(r_1,r_2,r_3-r_1)$ and
$(a_1^{\prime},a_2^{\prime},a_3^{\prime})=(a_1+a_3,a_2,a_3)$.
Since $a_1<a_1+a_3<\frac{1}{2}a_3<-a_1$, we have $\vert
a_1^{\prime}\vert =\vert a_1+a_3\vert<\vert a_1\vert$ and hence
this operation has the desired effect. \hspace*{\fill} $\qedsymbol$

This problem was suggested by Kiran Kedlaya.

\item  At a certain mathematical conference, every pair of
mathematicians are either friends or strangers. At mealtime, every
participant eats in one of two large dining rooms. Each
mathematician insists upon eating in a room which contains an even
number of his or her friends. Prove that the number of ways that
the mathematicians may be split between the two rooms is a power
of two (i.e., is of the form $2^k$ for some positive integer $k$).

\medskip

{\bf Solution:} Let $n$ be the number of participants at the
conference. We proceed by induction on $n$.


If $n=1$, then we have one participant who can eat in either room;
that gives us total of $2=2^1$ options.

Let $n\geq 2$. The case in which some participant, $P$, has no
friends is trivial. In this case, $P$ can eat in either of the two
rooms, so the total number of ways to split $n$ participants is
twice as many as the number of ways to split $(n-1)$ participants
besides the participant $P$. By induction, the latter number is a
power of two, $2^k$, hence the number of ways to split $n$
participants is $2\times 2^k=2^{k+1}$, also a power of two. So we
assume from here on that every participant has at least one
friend.

We consider two different cases separately: the case when some
participant has an odd number of friends, and the case when each
participant has an even number of friends.

{\bf Case 1:} {\it Some participant, $Z$, has an \underline{odd}
number of friends.}

Remove $Z$ from consideration and for each pair $(X,~Y)$ of $Z$'s
friends, reverse the relationship between $X$ and $Y$ (from friends
to strangers or vice versa).

{\bf Claim.} {\it The number of possible seatings is unchanged
after removing $Z$ and reversing the relationship between $X$ and
$Y$ in each pair $(X,~Y)$ of $Z$'s friends.}


{\it Proof of the claim.} Suppose we have an arrangement prior to
$Z$'s departure. By assumption, $Z$ has an \underline{even} number
of friends in the room with him.


If this number is $0$, the room composition is clearly still valid
after $Z$ leaves  the room.

If this number is positive, let $X$ be one of $Z$'s friends in the
room with him. By
assumption, person $X$ also has an even number of friends in the
same room. Remove $Z$ from the room; then $X$ will have an odd
number of friends left in the room, and there will be an odd
number of $Z$'s friends in this room besides $X$. Reversing the
relationship between $X$ and each of $Z$'s friends in this room
will therefore restore the parity to even.

The same reasoning applies to any of $Z$'s friends in the other
dining room. Indeed, there will be an odd number of them in that
room, hence each of them will reverse relationships with an even
number of individuals in that room, preserving the parity of the number of
friends present.

Moreover, a legitimate seating without $Z$ arises from
\underline{exactly one} arrangement including $Z$, because in the
case under consideration, only one room contains an even number of
$Z$'s friends. \hspace*{\fill} $\qedsymbol$

Thus, we have to double the number of seatings for $(n-1)$
participants which is, by the induction hypothesis, a power of 2.
Consequently, for $n$ participants we will get again a power of 2
for the number of different arrangements.

{\bf Case 2:} {\it Each participant has an \underline{even} number
of friends.}

In this case, each valid split of participants in two rooms gives
us an even number of friends in either room.

Let $(A,~B)$ be any pair of friends. Remove this pair from
consideration and for each pair $(C,~D)$, where $C$ is a friend of
$A$ and $D$ is a friend of $B$, change the relationship between
$C$ and $D$ to the opposite; do the same if $C$ is a friend of $B$
and $D$ is a friend of $A$.
Note that if $C$ and $D$ are friends of both $A$ and $B$, their
relationship will be reversed twice, leaving it unchanged.

Consider now an arbitrary participant $X$ different from $A$ and
$B$ and choose one of the two dining rooms.  [Note that in the
case under consideration, the total number of participants is at
least 3, so such a triplet $(A,~B;~X)$ can be chosen.] Let $A$
have $m$ friends in this room and let $B$ have $n$ friends in this room; both $m$
and $n$ are even. When the pair $(A,~B)$ is removed,
$X$'s relationship will be reversed with either $n$, or $m$,
or $m+n-2k$ (for $k$ the number of mutual friends of $A$ and $B$
in the chosen room), or $0$ people within the chosen room (depending on
whether he/she is a friend of only $A$, only $B$, both, or neither). Since
$m$ and $n$ are both even, the parity of the number of $X$'s
friends in that room will be therefore unchanged in any case.


Again, a legitimate seating without $A$ and $B$ will arise
from \underline{exactly one} arrangement that includes the pair
$(A,~B)$: just add each of $A$ and $B$ to the room with an
odd number of the other's friends, and then reverse all of the
relationships between a friend of $A$ and a friend of $B$. In this way we
create a one-to-one correspondence between all possible seatings
before and after the $(A,~B)$ removal.

Since the number of arrangements for $n$ participants is twice as
many as that for $(n-2)$ participants, and that number for $(n-2)$
participants is, by the induction hypothesis, a power of 2, we get
in turn a power of 2 for the number of arrangements for $n$ participants.
The problem is completely solved. \hspace*{\fill}
$\qedsymbol$

This problem was suggested by Sam Vandervelde.





\end{enumerate}

 \vfill {\small
\begin{center}
Copyright \copyright\ \ Committee on the American Mathematics
Competitions,\\
Mathematical Association of America
\end{center}
}
\end{document}
\begin{center}
\epsfbox{kiran072.eps} % \\
%{\footnotesize Figure 1.57.}
\end{center}
\end{document}