\documentclass[12pt]{article}
\usepackage{amssymb, latexsym, amsmath, amsthm}
\usepackage{epic, eepic}
\usepackage{graphicx}
\usepackage{pifont}
\usepackage{enumerate}
\usepackage{fancyhdr, ifthen, lastpage}
\usepackage{epsf}

\pagestyle{empty} \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}{20pt} \setlength{\labelsep}{10pt}
\setlength{\parindent}{0pt} \setlength{\medskipamount}{3ex}
\setlength{\smallskipamount}{1ex}
\def\RR{{\Bbb R}}
\newtheorem{fact}{Proposition}
\newcommand\dg{\raisebox{.15pt}{$^{\circ}$}}
\def\th{^{\mbox{\scriptsize th}}}

\def\head#1{\noindent \textbf{#1.}}
\def\OR{\begin{center} \textbf{ OR } \\ \end{center}}
\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\be{\begin{enumerate}}
\def\ii{\item}
\def\ee{\end{enumerate}}
\def\bi{\begin{itemize}}
\def\ei{\end{itemize}}

\def\CC{\mathbb{C}}
\def\NN{\mathbb{N}}
\def\QQ{\mathbb{Q}}
\def\RR{\mathbb{R}}
\def\ZZ{\mathbb{Z}}

\def\calA{\mathcal{A}}
\def\calB{\mathcal{B}}
\def\calC{\mathcal{C}}
\def\calF{\mathcal{F}}
\def\calG{\mathcal{G}}
\def\calP{\mathcal{P}}
\def\calR{\mathcal{R}}
\def\calS{\mathcal{S}}
\def\calT{\mathcal{T}}

\def\lf{\lfloor}
\def\rf{\rfloor}
\def\floor#1{\lf {#1} \rf}
\def\Lf{\left\lfloor}%tjp
\def\Rf{\right\rfloor}%tjp
\def\lc{\lceil}
\def\rc{\rceil}
\def\Lp{\left(}
\def\Rp{\right)}
\def\Lc{\left\lc}
\def\Rc{\right\rc}
\def\Lb{\left[} %tjp
\def\Rb{\right]}%tjp
\def\Paren#1{\Lp {#1} \Rp}

\def\ang{\angle}
\def\sang{\sin \angle}
\def\oar{\overrightarrow}
\def\ray{\stackrel\rightharpoonup}
\def\odar{\stackrel\longleftrightarrow}
\def\ol{\overline}
\def\lra{\leftrightarrow}
\def\sfn{\widehat}

\def\beqa{\begin{eqnarray*}}
\def\eeqa{\end{eqnarray*}}
\def\dsp{\displaystyle}

\def\binom#1#2{{#1 \choose #2}}
\def\half{\frac{1}{2}}
\def\lcm{\textrm{lcm}}
\def\dnd{\mbox{\ $\!\not\;\mid $\ }}
\def\arc{\widehat}
\def\cis{\,\mbox{cis}\,}
\def\real{\,\mbox{Re}\,}
\def\ord{\,\mbox{ord}\,}
\def\legendre#1#2{\left( \frac{#1}{#2} \right)}
\def\dg{^{\circ}}
\def\mymod#1{\,(\mbox{mod}\,\, #1)}
\def\map#1#2#3{#1\!: #2\to #3}
\def\eop{\rule{5pt}{5pt}}

\begin{document}
\setlength{\baselineskip}{.25in}
\begin{center}
${\bf 34\th}$ \textbf{United States of America Mathematical
Olympiad}
\end{center}
\begin{enumerate}

\item %LIU1
Answer: $n=4$ or $n\geq 6$.
\\
\\
First we show that these are all possible. For $n=2k \geq 4$, let
$$(a_1,a_2,\dots,a_k)=\left(k,2,1,1,\dots\,1\right).$$ For
$n=2k+3\geq 9$, let
$$(a_1,a_2,\dots,a_k)=\left(\frac{2k+3}{2},\frac{1}{2},4,1,1,\dots,1\right).$$
Finally, for $n=7$, take
$$(a_1,a_2,a_3)=\left(\frac{4}{3},\frac{7}{6},\frac{9}{2}\right).$$
It is easy to verify that these constructions all satisfy the given
conditions.

We now show that it is impossible for $n=1$, $2$, $3$, or $5$.
Indeed, suppose we have a construction for some $k$. By AM-GM,
$$n^\frac{1}{k}=\sqrt[k]{a_1a_2\dots a_k}\leq
\frac{a_1+a_2+\dots+a_k}{k}=\frac{n}{k}.$$ This gives $$n\geq
k^{\frac{k}{k-1}},$$ but the right hand side is greater than 5 when
$k\geq 3$. Thus we must have $k=2$. But then $a_1+a_2=a_1a_2=n$
implies that $$a_2=\frac{a_1}{a_1-1} \mbox{, and }
n=\frac{a_1^2}{a_1-1}.$$ Thus $a_1$ satisfies the quadratic
$a_1^2-a_1n+n=0$, but since $a_1$ is rational, $n^2-4n$ must be a
square. Since this is not the case for any of these $n$, this
completes the proof.

[Note: A considerable portion of the difficulty of this problem lies
in dealing with the case $n=7$, much more than one might expect from
the short construction.]

\item %HEU1
No, a square in the plane cannot be covered by two smaller squares.
Let the square be $S=ABCD$ and its side length be 1. See figure
below. If some two smaller squares were to cover S, neither could
cover two opposite corners, so each would have to cover two adjacent
corners. Suppose, without loss of generality, that one of them, with
side $s<1$ covers $A$ and $B$, and thus side $AB$. The other must
cover side $CD$, and between them they must cover sides $AD$ and
$BC$. Let $\alpha$ be the angle indicated in the figure between a
side of the smaller square and side $AB$, and $x$ and $y$ be the
lengths of the parts of $AD$ and $BC$, respectively, covered by this
first smaller square. We assume that the sides of the smaller square
pass through $A$ and $B$, for if not, we could move the square and
cover more of square $ABCD$, still covering side $AB$. Then point
$A$ divides the side of the smaller square into lengths
$s-\cos{\alpha}$ and $\cos{\alpha}$, and
$x=(s-\cos{\alpha})/\sin{\alpha}$. Point $B$ divides the side of the
smaller square passing through it into lengths $\sin{\alpha}$ and $s
- \sin{\alpha}$, and $y=(s-\sin{\alpha})/\cos{\alpha}$. Thus

\begin{align*}
x+y &= \frac{s-\cos{\alpha}}{\sin{\alpha}} +
\frac{s-\sin{\alpha}}{\cos{\alpha}}\\
&< \frac{1-\cos{\alpha}}{\sin{\alpha}} +
\frac{1-\sin{\alpha}}{\cos{\alpha}}\\
&=\frac{\sin{\alpha}}{1 + \cos{\alpha}} + \frac{\cos{\alpha}}{1 +
\sin{\alpha}}\\
&=\frac{\sin{\alpha} + \cos{\alpha} + 1}{1+ \sin{\alpha} +
\cos{\alpha} + \sin{\alpha}\cos{\alpha}}\\
&<1,
\end{align*}

as is clear from the fact that $0 < \alpha < \pi/2$. Similarly the
parts of sides $AD$ and $BC$ covered by the second smaller square
have total length less than 1, and therefore between them they fail
to cover all of the vertical sides.

%\item %AND1


\item %GIBBS1
We will show that $N_t = 2k^3 + 5k^2 +3k-1$ and that $N_f= 2k^3 +
3k^2 +3k.$\\
    First we'll find $N_t$. Given $k$, $N$, and positive integers $a_1 <
a_2<a_3<\ldots<a_{2k+1}$, suppose that
    $$a_1 + a_2 + a_3 + \ldots + a_{2k+1} > N,$$
but that
    $$a_{k+2} + a_{k+3} + a_{k+4} + \ldots +a_{2k+1} \leq N/2.$$
(Note that $a_{k+2} + a_{k+3} + a_{k+4} + \ldots +a_{2k+1}$ is the
largest possible $k$ element subset sum.) Then we have\\
    $a_{k+2} + (a_{k+2}+1) + (a_{k+2}+2) + \ldots + (a_{k+2}+(k-1))$
    $= k(a_{k+2}) + (k-1)k/2$
    $\leq a_{k+2} + a_{k+3} + a_{k+4} + \ldots +a_{2k+1} \leq N/2$\\
and so
    $$a_{k+2} \leq N/(2k)-(k-1)/2=(N-k^2+k)/(2k).$$
Define q and r by
    $$N-k^2+k = (2k)q+r\text{, where } 0\leq r \leq 2k-1.$$
Then $a_{k+2} \leq q,$ $a_{k+1} \leq q-1,$ and\\
    $a_1 + a_2 + a_3 + \ldots + a_{k+1} \leq (q-(k+1)) + (q-k) +
    (q-(k-1)) + \ldots + (q-1) = (k+1)q-(k+1)(k+2)/2.$\\
Therefore,
\begin{align}
\text{if $(k+1)q - (k+1)(k+2)/2 \leq N/2$, then (by way of
contradiction) $P(k,N)$ is true.}
\end{align}

Since
    $N=(2k)q+r+k^2 -k,$ where $0 \leq r \leq 2k-1,$
we see that (1) is equivalent to
    if $q-r/2 \leq k^2 + k +1,$ then $P(k,N)$ is true,
or more precisely,
\begin{align}
\text{if $\lfloor q- r/2 \rfloor \leq k^2 + k +1$, then $P(k,N)$ is
true}
\end{align}

It follows that $N_t$ occurs for $r = 2k-1$ and, consequently,
$q=(k+1)^2$ (why?).

Therefore, $N_t = 2k(k+1)^2 + (2k-1) + k^2 -k = 2k^3 + 5k^2 +3k-1.$

    We'll now find $N_f$. We know that if $(k+1)q-(k+1)(k+2)/2 \leq N/2$ then $P(k,N)$ is true. We'll show that if $(k+1)q-(k+1)(k+2)/2
    > N/2$ then $P(k,N)$ is false. To that end suppose that $(k+1)q-(k+1)(k+2)/2
    > N/2.$ Define
    $$a_i = q - (k+2-i) \text{ for } i= 1, 2, 3, \ldots, 2k\text{ and } a_{2k+1} = N/2 - (k-1)q -
    (k-2)(k-1)/2.$$
Then it is clear that $a_1<a_2<a_3< \ldots<a_{2k}.$ Furthermore,
$a_{2k} < a_{2k+1}$ if and only if
    $$q-(2-k) + (k-1)q + (k+1)(k+2)/2 < N/2$$
if and only if
    $$2kq + (k-2)(k+1) < N = 2kq + r +k^2 -k$$
Since $N \geq 2kq + k^2 -k > 2kq + (k-2)(k+1)$, we see that
$a_{2k}<a_{2k+1}.$ Furthermore, for this set $a_1, a_2, a_3, \ldots,
a{2k+1},$
    $$a_1+a_2+a_3+\ldots+a_{k+1} = (k+1)q-(k+1)(k+2)/2 > N/2,$$
and, because $a_{2k+1}+a_{2k+2}+a_{2k+3}+\ldots+a_{2k+1} =
(k-1)q+(k-2)(k-1)/2,$
$$a_{2k+1}+a_{2k+2}+a_{2k+3}+\ldots+a_{2k+1} = N/2.$$

Therefore, $a_1 + a_2+a_3+\ldots + a_{2k+1} >N$, but $a_{2k+1} +
a_{2k+2} + a_{2k+3} + \ldots +a_{2k+1} = N/2.$ So $P(k,N)$ is false
if $(k+1)q-(k+1)(k+2)/2 > N/2.$ Since $(k+1)q-(k+1)(k+2)/2 > N/2$ is
equivalent to $\lfloor q-r/2 \rfloor > k^2 +k+1$, we see that $N_f$
occurs for $r=0$, and consequently, $q=k^2+k+2$ (why?). Therefore,
$N_f = 2k(k^2+k+2) + 0 + k^2 - k = 2k^3 + 3k^2 + 3k$.

\item %KED1
First suppose that $s$ is a divisor of $p-1$; write $d = (p-1)/s$.
As $x$ varies among $1,2,\dots,p-1$, $\{ sx/p\}$ takes the values
$1/p, 2/p, \dots, (p-1)/p$ once each in some order. The possible
values with $\{sx/p\} < s/p$ are precisely $1/p, \dots, d/p$. From
the fact that $\{sd/p\} = (p-1)/p$, we realize that the values
$\{sx/p\} = 1/p, 2/p, \dots, d/p$ occur for
\[
x = p-d, 2(p-d)-p, \dots, s(p-d)-(s-1),
\]
respectively. (The point is that the numbers we wrote down are all
between 0 and $p$. It may be a bit easier to see that the values
$\{sx/p\} = (p-d)/p, \dots, (p-1)/p$ occur for $x=d, 2d, \dots, sd$,
respectively.)
>From this it is clear that $m$ and $n$ cannot exist as requested.

Conversely, suppose that $s$ is not a divisor of $p-1$. Put $m =
\lceil p/s \rceil$; then $m$ is the smallest positive integer such
that $\{ ms/p \} < s/p$, and in fact $\{ms/p\} = (ms-p)/p$. However,
we cannot have $\{ms/p\} = (s-1)/p$ or else we would have $(m-1)s =
p-1$, contradicting our hypothesis that $s$ does not divide $p-1$.
Hence the unique $n \in \{1, \dots, p-1\}$ for which $\{nx/p\} =
(s-1)/p$ has the desired properties (since the fact that $\{nx/p\} <
s/p$ forces $n \geq m$, but $m \neq n$).

\medskip
\head{Note} This problem is taken from a short paper of G. Lettl
(Note on a theorem of A. Aiba, \textit{Journal of Number Theory}, to
appear in 2005 but now available online); we learned about it from a
lecture of Bart de Smit.

\item %SUN2
Denote by $x_{i,k}$ the minimal number of moves needed to reach the
number $n_{i,k}=2^ik$, for $i \geq 0$ and $k \geq 1$. We need to
show that
\begin{equation}\label{claim}
x_{i,k} > x_{i,1},
\end{equation}
for $i \geq 0$ and $k>1$.

We do this by induction on $i$. The inequality \eqref{claim} holds
for $i=0$, since it takes more moves (at least 1) to reach
$n_{0,k}=k>1$ than it does to reach $n_{0,1}=1$ (0 moves).

Assume that $i \geq 1$ and $x_{j,k} > x_{j,1}$ holds for all $k>1$
and all non-negative $j$ that are smaller than $i$. Choose the
smallest $k>1$ for which \eqref{claim} fails. We will prove our
inductive claim by showing that the existence of such a $k$ leads to
a contradiction.

Let $P_k$ be a shortest sequence of $x_{i,k}$ moves used to reach
$n_{i,k}=2^ik$. In each move we make either a step of size 1 or a
step of size a positive integer power of 2 (the exact size of such a
power is based on the divisibility condition). The sequence of moves
$P_k$ cannot go through the value $2^i$ (otherwise the choice of $k$
is contradicted). Thus the value $2^i$ is jumped over. Let
$2^{M+1}$, $M \geq 0$, be the size of the largest step used in
$P_k$. Such a step can only be performed starting from a number
divisible by $2^M$. Thus we must have $M<i$ (otherwise a number
divisible by $2^i$ is visited in $P_k$ before $2^ik$ is reached,
which is a contradiction).

Let $2^{m+1}$ be the size of the step used to jump over $2^i$. We
have $0 \leq m < i$. The numbers of the form $2^m(2t+1)$, where $t$
is a non-negative integer, are the only numbers from which it is
possible to make a step of size $2^{m+1}$. Since
\[ 2^m(2^{i-m} -1) =2^i - 2^m < 2^i < 2^i + 2^m = 2^m(2^{i-m} +1) \]
and $2^m(2^{i-m} -1) + 2^{m+1} = 2^m(2^{i-m} +1)$ the step of size
$2^{m+1}$ used to jump over $2^i$ in the sequence $P_k$ consists of
replacing $2^m(2^{i-m} -1)$ by $2^m(2^{i-m}+1)=2^i+2^m$.

Let the number of moves in $P_k$ used to reach $2^i+2^m$ from $1$ be
$N_1$ and the number of moves used to reach $2^ik$ from $2^i+2^m$ be
$N_2$. By inductive assumption $2^m$ can be reached from $1$ in less
than $N_1$ moves. On the other hand, since $M<i$ the number
$2^i(k-1)$ can be reached from $2^m$ in exactly $N_2$ moves by using
steps of the same size as the steps in the last $N_2$ moves in the
sequence $P_k$ in which $2^ik = 2^i(k-1)+2^i$ is reached from
$2^m+2^i$. The crucial observation is that the shift by $2^i$ does
not affect the divisibility conditions needed to perform the steps
of the required size. More precisely, the numbers obtained by using
the sequence of moves $P_k$ that are smaller than $2^ik$ all have
the form $2^p(2t+1)$ where $p<i$ (again by minimality of $k$). Since
$2^p(2t+1) - 2^i = 2^p(2t-2^{i-p}+1)$ and the number
$(2t-2^{i-p}+1)$ is odd, a step of size $2^{p+1}$ can be applied to
$2^p(2t+1)-2^i$ just as it could be applied to $2^p(2t+1)$.

Thus we can reach $2^i(k-1)$ from $1$ in less than $N_1+N_2=
x_{i,k}$ moves, which contradicts the assumed properties of $k$.

\vspace{1cm}

\textbf{Note} The problem is based on a graph theoretic idea
presented in

I.~Benjamini, C.~Hoffman, $\omega$-Periodic Graphs, The Electronic
Journal of Combinatorics \textbf{12} (2005) no.1, R46.

\item %FENG3
Let $P$ be the second intersection of the circumcircles of triangles
$TCF$ and $TDE$. Because $PEDT$ is cyclic, $\ang PET = \ang PDT$, or
\[
\ang PEF = \ang PDC. \eqno(*)
\]
Because $PFCT$ is cyclic,
\[
\ang PFE = \ang PFT = \ang PCT = \ang PCD. \eqno{(**)}
\]
By equations $(*)$ and $(**)$, it follows that triangle $PEF$ is
similar to triangle $PDC$. Hence $\ang FPE = \ang CPD$ and $PF/PE =
PC/PD$. Note also that $\ang FPC = \ang FPE + \ang EPC = \ang CPD +
\ang EPC = \ang EPD$. Thus, triangle $EPD$ is similar to triangle
$FPC$. (Indeed, because there is a {\bf spiral similarity}, centered
at $P$, that sends triangle $PFE$ to triangle $PCD$, it follows that
there is also a spiral similarity, centered at $P$, that sends
triangle $PFC$ to triangle $PED$, and vice versa.)

\begin{center}
\epsfbox{zfeng062.eps} %\\
%{\footnotesize Figure 1.57.}
\end{center}

Because $AE/ED = BF/FC$, points $A$ and $B$ are obtained by
extending corresponding segments of two similar triangles $PED$ and
$PFC$, namely, $DE$ and $CF$, by the identical proportion. We
conclude that triangle $PDA$ is similar to triangle $PCB$, implying
that triangle $PAE$ is similar to triangle $PBF$. Therefore, as
shown before, we can establish the similarity between triangles
$PBA$ and $PFE$, implying that
\[
\ang PBS = \ang PBA = \ang PFE = \ang PFS \quad \mbox{and}\quad \ang
PAB = \ang PEF.
\]
The first equation above shows that $PBFS$ is cyclic. The second
equation shows that $\ang PAS = 180\dg - \ang PAB = 180\dg - \ang
PEF = \ang PES$; that is, $PAES$ is cyclic. We conclude that the
circumcircles of triangles $SAE$, $SBF$, $TCF$, and $TDE$ pass
through point $P$.

\note There are two spiral similarities that sends segment $EF$ to
segment $CD$, and vice versa. One of them sends $E$ and $F$ to $D$
and $C$, respectively. Point $P$ is the center of this spiral
similarity. The other sends $E$ and $F$ to $C$ and $D$,
respectively. The center of this spiral similarity is the second
intersection (other than $T$) of the circumcircles of triangles
$TFD$ and $TEC$.


\end{enumerate}
\end{document}