\documentclass[amssymb,twocolumn]{revtex4}
\usepackage{times,amsmath,latexsym,epsfig}

\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}

\begin{document}
\title{Solutions to the 60th William Lowell Putnam Mathematical Competition \\
    Saturday, December 4, 1999}
\author{Manjul Bhargava, Kiran Kedlaya, and Lenny Ng}
\maketitle

\begin{itemize}

\item[A--1]
Note that if $r(x)$ and $s(x)$ are any two functions, then
\[ \max(r,s) = (r+s + |r-s|)/2.\]
Therefore, if $F(x)$ is the given function, we have
\begin{align*}
F(x)\ &= \max\{-3x-3,0\}-\max\{5x,0\}+3x+2 \\
      &= (-3x-3+|3x-3|)/2 \\
      & \qquad - (5x + |5x|)/2 + 3x+2 \\
      &= |(3x-3)/2| - |5x/2| -x + \frac{1}{2},
\end{align*}
so we may set $f(x)=(3x-3)/2$, $g(x) = 5x/2$, and $h(x)=-x+\frac{1}{2}$.

\item[A--2]
First solution:
First factor $p(x) = q(x) r(x)$, where $q$ has all real roots and $r$ has
all complex roots. Notice that each root of $q$ has even
multiplicity, otherwise $p$ would have a sign change at that root.
Thus $q(x)$ has a square root $s(x)$.

Now write $r(x) = \prod_{j=1}^k (x - a_j)(x - \overline{a_j})$
(possible because $r$ has roots in complex conjugate pairs).
Write $\prod_{j=1}^k (x - a_j) = t(x) + i u(x)$ with $t,x$
having real coefficients. Then for $x$ real,
\begin{align*}
p(x) &= q(x) r(x) \\
&= s(x)^2 (t(x) + iu(x)) (\overline{t(x) + iu(x)}) \\
&= (s(x)t(x))^2 + (s(x)u(x))^2.
\end{align*}
(Alternatively, one can factor $r(x)$ as a product of quadratic
polynomials with real coefficients, write each as a sum of squares, then
multiply together to get a sum of many squares.)

Second solution:
We proceed by induction on the degree of $p$, with base case where $p$
has degree 0. As in the first solution, we may reduce to a smaller degree
in case $p$ has any real roots, so assume it has none. Then $p(x) > 0$
for all real $x$, and since $p(x) \to \infty$ for $x \to \pm \infty$, $p$
has a minimum value $c$. Now $p(x) - c$ has real roots, so as above, we
deduce that $p(x) - c$ is a sum of squares. Now add one more square,
namely $(\sqrt{c})^2$, to get $p(x)$ as a sum of squares.

\item[A--3]
First solution:
Computing the coefficient of $x^{n+1}$ in the identity
$(1-2x-x^2)\sum_{m=0}^\infty a_m x^m = 1$ yields the recurrence
$a_{n+1} = 2a_n + a_{n-1}$; the sequence $\{a_n\}$ is then characterized
by this recurrence and the initial conditions $a_0 = 1, a_1 = 2$.

Define the sequence $\{b_n\}$ by
$b_{2n} = a_{n-1}^2 + a_n^2,~b_{2n+1} = a_n(a_{n-1}+a_{n+1}).$
Then
\begin{align*}
2b_{2n+1}+b_{2n} &= 2a_na_{n+1}+2a_{n-1}a_n+a_{n-1}^2+a_n^2 \\
&= 2a_na_{n+1} + a_{n-1}a_{n+1} + a_n^2 \\
&= a_{n+1}^2 + a_n^2 = b_{2n+2},
\end{align*}
and similarly $2b_{2n}+b_{2n-1} = b_{2n+1}$, so that $\{b_n\}$ satisfies
the same recurrence as $\{a_n\}$.  Since further $b_0=1,b_1=2$ (where
we use the recurrence for $\{a_n\}$ to calculate $a_{-1}=0$),
we deduce that $b_n=a_n$ for all $n$.  In particular,
$a_n^2+a_{n+1}^2 = b_{2n+2} = a_{2n+2}$.

Second solution:  
Note that
\begin{multline*}
\frac{1}{1-2x-x^2} \\
\qquad = \frac{1}{2\sqrt{2}} \left(
\frac{\sqrt{2}+1}{1-(1+\sqrt{2})x} + \frac{\sqrt{2}-1}{1-(1-\sqrt{2})x}
\right)
\end{multline*}
and that
\begin{eqnarray*}
\frac{1}{1 + (1\pm\sqrt{2})x} = \sum_{n=0}^\infty (1\pm\sqrt{2})^n x^n, 
\end{eqnarray*}
so that
\[
a_n = \frac{1}{2\sqrt{2}} \left((\sqrt{2}+1)^{n+1} - (1-\sqrt{2})^{n+1}
\right).
\]
A simple computation (omitted here) now shows that
$a_n^2 + a_{n+1}^2 = a_{2n+2}$.

Third solution (by Richard Stanley):
Let $A$ be the matrix $\begin{pmatrix} 0 & 1 \\1 & 2 \end{pmatrix}$.
A simple induction argument shows that
\[
A^{n+2} = \begin{pmatrix} a_n & a_{n+1} \\ a_{n+1} & a_{n+2}
\end{pmatrix}.
\]
The desired result now follows from comparing the top left corner
entries of the equality $A^{n+2} A^{n+2} = A^{2n+4}$.

\item[A--4]
Denote the series by $S$, and let $a_n = 3^n/n$.  Note that
\begin{align*}
S &= \sum_{m=1}^\infty \sum_{n=1}^\infty \frac{1}
{a_m(a_m+a_n)} \\
&= \sum_{m=1}^\infty \sum_{n=1}^\infty \frac{1}{a_n(a_m+a_n)},
\end{align*}
where the second equality follows by interchanging $m$ and $n$.
Thus
\begin{align*}
2S &= \sum_m \sum_n \left( \frac{1}{a_m(a_m+a_n)} +
\frac{1}{a_n(a_m+a_n)}\right) \\
&= \sum_m \sum_n \frac{1}{a_m a_n} \\
&= \left( \sum_{n=1}^\infty \frac{n}{3^n} \right)^2.
\end{align*}
But
\[
\sum_{n=1}^\infty \frac{n}{3^n} = \frac34
\]
since, e.g., it's $f'(1)$,
where
\[
f(x) = \sum_{n=0}^\infty \frac{x^n}{3^n} = \frac{3}{3-x},
\]
and we conclude that $S = 9/32$.

\item[A--5]

First solution: (by Reid Barton)
Let $r_1, \dots, r_{1999}$ be the roots of $P$. Draw a disc of radius
$\epsilon$ around each $r_i$, where $\epsilon < 1/3998$; this 
disc covers a subinterval of $[-1/2,1/2]$
of length at most $2\epsilon$, and so of the 2000 (or fewer) uncovered
intervals in $[-1/2,1/2]$,
one, which we call $I$, has length at least $\delta = (1-3998\epsilon)/2000
> 0$.
We will exhibit an explicit lower bound for the integral of $|P(x)|/P(0)$ over this
interval, which will yield such a bound for the entire integral.

Note that
\[
\frac{|P(x)|}{|P(0)|} = \prod_{i=1}^{1999} \frac{|x-r_i|}{|r_i|}.
\]
Also note that by construction, $|x - r_i| \geq \epsilon$ for each $x \in I$.
If $|r_i| \leq 1$, then we have $\frac{|x-r_i|}{|r_i|} \geq \epsilon$. If $|r_i| > 1$, then
\[
\frac{|x-r_i|}{|r_i|} = |1 - x/r_i| \geq 1 - |x/r_i| \geq = 1/2
> \epsilon.
\]
We conclude that $\int_I |P(x)/P(0)|\,dx \geq \delta \epsilon$, 
independent of $P$.

Second solution:
It will be a bit more convenient to assume $P(0) = 1$ (which we
may achieve by rescaling unless $P(0)=0$, in which case
there is nothing to prove) and to prove that there exists $D>0$
such that $\int_{-1}^1 |P(x)|\,dx \geq D$, or even
such that $\int_0^1 |P(x)|\,dx \geq D$.

We first reduce to the case where $P$ has all of its roots in
$[0,1]$. If this is not the case, we can
factor $P(x)$ as $Q(x) R(x)$, where $Q$ has all roots in
the interval and $R$ has none. Then $R$ is either always
positive or always negative on $[0,1]$; assume the former.
Let $k$ be the largest positive real number such that
$R(x) - kx \geq 0$ on $[0,1]$; then
\begin{align*}
\int_{-1}^1 |P(x)|\,dx &= \int_{-1}^1 |Q(x)R(x)|\,dx \\
&> \int_{-1}^1 |Q(x)(R(x)-kx)|\,dx,
\end{align*}
and $Q(x)(R(x)-kx)$ has more roots in $[0,1]$ than does $P$
(and has the same value at 0).
Repeating this argument shows that $\int_{0}^1 |P(x)|\,dx$
is greater than the corresponding integral for some polynomial
with all of its roots in $[0,1]$.

Under this assumption, we have
\[
P(x) = c \prod_{i=1}^{1999} (x-r_i)
\]
for some $r_i \in (0,1]$. Since
\[
P(0) = -c \prod r_i = 1,
\]
we have
\[
|c| \geq \prod |r_i^{-1}| \geq 1.
\]

Thus it suffices to prove that if $Q(x)$ is a \emph{monic} polynomial
of degree 1999 with all of its roots in $[0,1]$,
then $\int_0^1 |Q(x)|\,dx \geq D$ for some constant $D>0$. But the
integral of $\int_0^1 \prod_{i=1}^{1999} |x-r_i|\,dx$ is a continuous
function for $r_i \in [0,1]$. The product of all of these intervals is
compact, so the integral achieves a minimum value for some $r_i$. This
minimum is the desired $D$.

Third solution (by Abe Kunin):
It suffices to prove the stronger inequality
\[
\sup_{x \in [-1,1]} |P(x)| \leq C \int_{-1}^1 |P(x)|\,dx
\]
holds for some $C$.
But this follows immediately from the following standard fact: any two
norms on a finite-dimensional vector space (here the polynomials of
degree at most 1999) are equivalent. (The proof of this statement is also
a compactness argument: $C$ can be taken to be the maximum of the
L1-norm divided by the sup norm over the set of polynomials with
L1-norm 1.)

Note: combining the first two approaches gives a constructive solution with
a constant that is better than that given by the first solution,
but is still far from optimal. I don't know
offhand whether it is even known what the optimal constant and/or the
polynomials achieving that constant are.

\item[A--6]
Rearranging the given equation yields the much more tractable equation
\[
\frac{a_n}{a_{n-1}} = 6 \, \frac{a_{n-1}}{a_{n-2}} 
- 8 \, \frac{a_{n-2}}{a_{n-3}}.
\]
Let $b_n = a_n/a_{n-1}$; with the initial conditions $b_2 = 2, b_3 = 12$,
one easily obtains $b_n = 2^{n-1} (2^{n-2} - 1)$, and so
\[
a_n = 2^{n(n-1)/2} \prod_{i=1}^{n-1} (2^i - 1).
\]
 
To see that $n$ divides $a_n$, factor $n$ as $2^k m$, with $m$
odd. Then note that $k \leq n \leq n(n-1)/2$, and that there
exists $i \leq m-1$ such that $m$ divides $2^i-1$, namely $i =
\phi(m)$ (Euler's totient function: the number of integers in
$\{1, \dots, m\}$ relatively prime to $m$).

\item[B--1]

The answer is 1/3.
Let $G$ be the point obtained by reflecting $C$ about the line $AB$.
Since $\angle ADC = \frac{\pi-\theta}{2}$, we find that
$\angle BDE = \pi - \theta - \angle ADC = \frac{\pi-\theta}{2}
= \angle ADC = \pi - \angle BDC = \pi - \angle BDG$, so that $E,D,G$
are collinear.  Hence
\[
|EF| = \frac{|BE|}{|BC|} = \frac{|BE|}{|BG|} = \frac{\sin
(\theta/2)}{\sin (3\theta/2)},
\]
where we have used the law of sines in $\triangle BDG$.  But by
l'H\^opital's Rule,
\[
\lim_{\theta \rightarrow 0} 
\frac{\sin(\theta/2)}{\sin(3\theta/2)} = 
\lim_{\theta \rightarrow 0}
\frac{\cos(\theta/2)}{3\cos(3\theta/2)} = 1/3.
\]

\item[B--2]
First solution:
Suppose that $P$ does not have $n$ distinct roots; then it has
a root of multiplicity at least $2$, which we may assume is $x=0$
without loss of generality.  Let $x^k$ be the greatest power of $x$
dividing $P(x)$, so that $P(x) = x^k R(x)$ with $R(0) \neq 0$;
a simple computation yields
\[
P''(x) = (k^2-k)x^{k-2} R(x) + 2kx^{k-1} R'(x) + x^k R''(x).
\]
Since $R(0) \neq 0$ and $k\geq 2$, we conclude that the greatest power of $x$ 
dividing $P''(x)$ is $x^{k-2}$.  But $P(x) = Q(x) P''(x)$, and so
$x^2$ divides $Q(x)$.
We deduce (since $Q$ is quadratic)
that $Q(x)$ is a constant $C$ times $x^2$; in fact, $C=1/(n(n-1))$ by
inspection of the leading-degree terms of $P(x)$ and $P''(x)$.

Now if $P(x) = \sum_{j=0}^n a_j x^j$, then the relation
$P(x) = Cx^2 P''(x)$ implies that $a_j = Cj(j-1)a_j$ for all $j$;
hence $a_j = 0$ for $j \leq n-1$, and we conclude that $P(x) = a_n x^n$,
which has all identical roots.

Second solution (by Greg Kuperberg): Let $f(x) = P''(x)/P(x) = 1/Q(x)$. By
hypothesis, $f$ has at most two poles (counting multiplicity).

Recall that for any complex polynomial $P$, the roots of $P'$ lie within the convex
hull of $P$. To show this, it suffices to show that if the roots of $P$ lie on one
side of a line, say on the positive side of the imaginary axis, then $P'$ has no
roots on the other side. That follows because if $r_1, \dots, r_n$ are the roots of $P$,
\[
\frac{P'(z)}{P(z)} = \sum_{i=1}^n \frac{1}{z-r_i}
\]
and if $z$ has negative real part, so does $1/(z-r_i)$ for $i=1, \dots, n$,
so the sum is nonzero.

The above argument also carries through if $z$ lies on the
imaginary axis, provided that $z$ is not equal to a root of $P$. Thus we also have that
no roots of $P'$ lie on the sides of the convex hull of $P$, unless they are also
roots of $P$.

From this we conclude that if $r$ is a root of $P$ which is a vertex of the convex hull
of the roots, and
which is not also a root of $P'$,
then $f$ has a single pole at $r$ (as $r$ cannot be a root of $P''$).
On the other hand, if $r$ is a root of $P$ which is also a root of $P'$, it
is a multiple root, and then $f$ has a double pole at $r$.

If $P$ has roots not all equal, the convex hull of its roots has at least two
vertices. 

\item[B--3]
We first note that
\[
\sum_{m,n > 0} x^m y^n = \frac{xy}{(1-x)(1-y)}.
\]
Subtracting $S$ from this gives two sums, one of which is
\[
\sum_{m \geq 2n+1} x^m y^n = \sum_n y^n \frac{x^{2n+1}}{1-x}
= \frac{x^3y}{(1-x)(1-x^2y)}
\]
and the other of which sums to $xy^3/[(1-y)(1-xy^2)]$. Therefore
\begin{eqnarray*}
S(x,y) &=& \frac{xy}{(1-x)(1-y)} - \frac{x^3y}{(1-x)(1-x^2y)} -
\frac{xy^3}{(1-y)(1-xy^2)} \\
&=& \frac{xy(1+x+y+xy-x^2y^2)}{(1-x^2y)(1-xy^2)}
\end{eqnarray*}
and the desired limit is $\lim_{(x,y) \to (1,1)} xy(1+x+y+xy-x^2y^2) = 3$.

\item[B--4]
\setcounter{equation}{0}
(based on work by Daniel Stronger)
We make repeated use of the following fact: if $f$ is a differentiable function on all of
$\RR$, $\lim_{x \to -\infty} f(x) \geq 0$, and $f'(x) > 0$ for all $x \in \RR$, then
$f(x) > 0$ for all $x \in \RR$. (Proof: if $f(y) < 0$ for some $x$, then $f(x)< f(y)$ for all
$x<y$ since $f'>0$, but then $\lim_{x \to -\infty} f(x) \leq f(y) < 0$.)

From the inequality $f'''(x) \leq f(x)$ we obtain
\[
f'' f'''(x) \leq f''(x) f(x) < f''(x) f(x) + f'(x)^2
\]
since $f'(x)$ is positive. Applying the fact to the difference between the right and left sides,
we get
\begin{equation}
\frac{1}{2} (f''(x))^2 < f(x) f'(x).
\end{equation}

On the other hand, since $f(x)$ and $f'''(x)$ are both positive for all $x$,
we have
\[
2f'(x) f''(x) < 2f'(x)f''(x) + 2f(x) f'''(x).
\]
Applying the fact to the difference between the sides yields
\begin{equation}
f'(x)^2 \leq 2f(x) f''(x).
\end{equation}
Combining (1) and (2), we obtain
\begin{align*}
\frac{1}{2} \left( \frac{f'(x)^2}{2f(x)} \right)^2
&< \frac{1}{2} (f''(x))^2 \\
&< f(x) f'(x),
\end{align*}
or $(f'(x))^3 < f(x)^3$. We conclude $f'(x) < 2f(x)$, as desired.

Note: one can actually prove the result with a smaller constant in place of
2, as follows. Adding $\frac{1}{2} f'(x) f'''(x)$ to both sides
of (1) and again invoking the original bound
$f'''(x) \leq f(x)$, we get
\begin{align*}
\frac{1}{2} [f'(x) f'''(x) + (f''(x))^2] &< f(x) f'(x) + \frac{1}{2} f'(x) f'''(x) \\
&\leq \frac{3}{2} f(x) f'(x).
\end{align*}
Applying the fact again, we get
\[
\frac{1}{2} f'(x) f''(x) < \frac{3}{4} f(x)^2.
\]
Multiplying both sides by $f'(x)$ and applying the fact once more, we get
\[
\frac{1}{6} (f'(x))^3 < \frac{1}{4} f(x)^3.
\]
From this we deduce $f'(x) < (3/2)^{1/3} f(x) < 2f(x)$, as desired.

I don't know what the best constant is, except that it is not less than 1
(because $f(x) = e^x$ satisfies the given conditions).

\item[B--5]

We claim that the eigenvalues of $A$ are $0$ with multiplicity $n-2$,
and $n/2$ and $-n/2$, each with multiplicity $1$.  To prove this claim,
define vectors $v^{(m)}$, $0\leq m\leq n-1$, componentwise by
$(v^{(m)})_k = e^{ikm\theta}$, and note that the $v^{(m)}$ form a basis
for $\CC^n$.  (If we arrange the $v^{(m)}$ into an $n\times n$ matrix,
then the determinant of this matrix is a Vandermonde product which is
nonzero.)  Now note that
\begin{align*}
(Av^{(m)})_j &= \sum_{k=1}^n \cos(j\theta+k\theta) e^{ikm\theta} \\
&= \frac{e^{ij\theta}}{2} \sum_{k=1}^n e^{ik(m+1)\theta}
+ \frac{e^{-ij\theta}}{2} \sum_{k=1}^n e^{ik(m-1)\theta}.
\end{align*}
Since $\sum_{k=1}^n e^{ik\ell\theta} = 0$ for integer $\ell$ unless
$n\,|\,\ell$, we conclude that $Av^{(m)}=0$ for $m=0$ or for
$2 \leq m \leq n-1$.  In addition, we find that $(Av^{(1)})_j = 
\frac{n}{2} e^{-ij\theta} = \frac{n}{2}(v^{(n-1)})_j$ and $(Av^{(n-1)})_j = 
\frac{n}{2} e^{ij\theta} = \frac{n}{2}(v^{(1)})_j$, so that 
$A(v^{(1)} \pm v^{(n-1)}) = \pm \frac{n}{2} (v^{(1)} \pm v^{(n-1)})$.
Thus $\{v^{(0)},v^{(2)},v^{(3)},\ldots,v^{(n-2)},
v^{(1)}+v^{(n-1)},v^{(1)}-v^{(n-1)}\}$ is a basis for $\CC^n$ of
eigenvectors of $A$ with the claimed eigenvalues.

Finally, the determinant of $I+A$ is the product of $(1+\lambda)$
over all eigenvalues $\lambda$ of $A$; in this case,
$\det (I+A) = (1+n/2)(1-n/2) = 1-n^2/4$.


\item[B--6]
First solution:
Choose a sequence $p_1, p_2, \dots$ of primes as follows. Let $p_1$ be any prime
dividing an element of $S$. To define $p_{j+1}$ given $p_1, \dots, p_j$,
choose an integer $N_j \in S$ relatively prime to $p_1 \cdots p_j$ and let
$p_{j+1}$ be a prime divisor of $N_j$, or stop if no such $N_j$ exists.

Since $S$ is finite, the above algorithm eventually terminates in a finite
sequence $p_1, \dots, p_k$. 
Let $m$ be the smallest integer such that $p_1 \cdots p_m$ has a divisor in $S$.
(By the assumption on $S$ with $n=p_1\cdots p_k$, 
$m=k$ has this property, so $m$ is well-defined.)
If $m=1$, then $p_1\in S$, and we are done, so assume $m\geq 2$.
Any divisor $d$ of $p_1\cdots p_m$ in $S$ must be a multiple of $p_m$, or else
it would also be a divisor of $p_1 \cdots p_{m-1}$, contradicting the choice
of $m$. But now $\gcd(d, N_{m-1}) = p_m$, as desired.

Second solution (from \texttt{sci.math}):
Let $n$ be the smallest integer such that $\gcd(s,n) > 1$ for all $s$ in
$n$; note that $n$ obviously has no repeated prime factors.
By the condition on $S$, there exists $s \in S$ which divides $n$.

On the other hand, if $p$ is a prime divisor of $s$, then by the choice
of $n$, $n/p$ is relatively prime to some element $t$ of $S$. Since $n$ cannot
be relatively prime to $t$, $t$ is divisible by $p$, but not by any other
prime divisor of $n$ (as those primes divide $n/p$). Thus $\gcd(s,t) = p$,
as desired.

\end{itemize}

\end{document}