% Process using LaTeX2e
\documentclass[12pt]{amsart}
\usepackage{latexsym}

% \setlength{\textheight}{8.75in}
% \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\binom#1#2{{#1 \choose #2}}
% \def\mymod#1{\,\,({\rm mod}\, #1)}

\begin{document}
\begin{center}
{\bf Solutions to the Sixtieth William Lowell Putnam Mathematical
Competition} \\
\vskip 0.25cm
Saturday, December 4, 1999\\
\vskip 0.25cm
Prepared by Mark Hovey
\end{center}

\vskip .2cm
\begin{itemize}
\item[A--1]
The simplest way to solve this is to let $f(x)$, $g(x)$, and $h(x)$ be
linear polynomials and figure out what they have to be.  I get $f(x)=\pm
(\frac{3}{2}x+\frac{3}{2})$, $g(x)=\pm (\frac{5}{2}x)$, and
$h(x)=-x+\frac{1}{2}$.  This gives 4 solutions.  Presumably there are no
others, but I am not sure about that.  

\item[A--2]
The idea of this proof is to write $p(x)$ as a product of irreducible
factors.   The leading coefficient of $p(x)$ must be nonegative, so is a
square.  If $p(x)$ has any linear factors, these must occur to an even
power, so are themselves squares.  Any irreducible quadratic factor is
of the form $x^{2}+bx+c$, where $b^{2}<4c$ (it is monic because we
factored out the leading coefficient already).  Hence any such quadratic
factor is a sum of squares, namely $(x+b/2)^{2} + (c-(1/4)b^{2})$.  It
remains to prove that sums of squares are closed under products, which
is straightforward.  

\item[A--3]
Use partial fractions to write 
\[
\frac{1}{1-2x-x^{2}} = -\frac{1}{2\sqrt{2}}(\frac{1}{x+c}-\frac{1}{x+b})
\]
where $c=1-\sqrt{2}$ and $b=1+\sqrt{2}$.  The standard expansion of
$1/(1+y)$, plus some simplification, then leads to 
\[
a_{n}= \frac{1}{2\sqrt{2}}(b^{n+1}-c^{n+1}).
\]
It helped me to realize that $b-c=2\sqrt{2}$, so we have 
\[
a_{n} = \frac{b^{n+1}-c^{n+1}}{b-c}. 
\]
Then, using the fact that $bc=-1$, we find that 
\[
a_{n}^{2} + a_{n+1}^{2} = a_{2n+2}.  
\]

\item[A--4] (Due to Prof. Karen Collins of Wesleyan University) Let $S$
denote the sum we are trying to find.  The key idea is to reverse the
roles of $m$ and $n$.  We have 
\[
2S = \sum _{m=1}^{\infty } \sum _{n=1}^{\infty }
\frac{m^{2}n}{3^{m}(m3^{n}+n3^{m})} + \frac{n^{2}m}{3^{n}(n3^{m}+m3^{n})}
\]
which is in turn equal to 
\[
\sum_{m=1}^{\infty }\sum _{n=1}^{\infty } \frac{mn}{3^{m}3^{n}} = T^{2}
\]
where $T=\sum _{m=1}^{\infty }\frac{m}{3^{m}}$.  The sum $T$ can be
evaluated by differentiating the standard series for $1-x$.  We find
\[
\frac{x}{(1-x)^{2}} = \sum _{m=1}^{\infty } mx^{m-1}.  
\]
Multiplying by $x$ and plugging in $x=1/3$, we find that 
\[
T=\sum _{m=1}^{\infty } \frac{m}{3^{m}} = \frac{1}{4}.  
\]
Therefore, the sum $S$ is $\frac{1}{32}$.  

\item[A--5] 

I don't like this problem.  I got the following solution from sci.math,
but I am not sure who to credit it to.  The first thing to realize is
that we may as well assume our polynomial $p$ has $p(0)=1$, since we can
fix any other value by scaling, except for $p(0)=0$, when there is
nothing to prove anyway. We are therefore trying to find a lower
bound for $\int _{-1}^{1} |p(x)| \, dx$ given that $p$ is a polynomial
of degree $N=1999$ and $p(0)=1$.  Since $p(0)=1$, $p$ is a
product of terms of the form $1-sx$.  The plan is to find a lower
bound for each $|1-sx|$ on some interval of finite length.  

Now, if $s=a+ib$ is complex, then the term $1-(a-ib)x$ will
also appear, so the product will be $1-2ax+(a^{2}+b^{2})\geq 1-2ax$.  It
therefore suffices to get a lower bound for $1-sx$ when $s$ is real.  

Cover the interval $[-1,1]$ by $2N$ intervals of length $1/N$, where
$N=1999$ but can be arbitrary.  Then there must be some interval which
contains no root of $p$.  Look at the middle third of this interval,
which therefore has length $1/3N$.  If $1-sx$ is one of the factors of
$p$, we have, for $x$ in this interval, $|x-(1/s)|> 1/3N$.  Hence
$|1-sx|>|s|/3N$.  If $|s|>1-\frac{1}{3N}$, we then have $|1-sx|>
(1-\frac{1}{3N})\frac{1}{3N}$ on this interval.  

If, on the other hand, $|s|<1-\frac{1}{3N}$, then $|1-sx|\geq 1 -
|s||x|\geq 1-|s|>1/3N$ on the whole interval $[-1,1]$.  So in either
case we have $|1-sx|>(1-\frac{1}{3N})\frac{1}{3N}$ on this interval, for
any factor $1-sx$ of $p$.  Hence 
\[
\int _{-1}^{1} |p(x)| \, dx \geq \frac{1}{3N}^{N+1} (1-\frac{1}{3N})^{N}
\]
as required.  

\item[A--6]
We claim that $a_{n}=\prod _{i=1}^{n-1}2^{i}(2^{i}-1)$.  One can easily
check that this series satisfies the recurrence.  The way I found this
was by guessing that $a_{n}$ is a multiple $\lambda _{n}$ of $a_{n-1}$,
deducing the recurrence relation for $\lambda _{n} $, and solving it.
Now, in order to show that $n$ divides $a_{n}$, we can assume that $n$
is odd, since there are so many powers of $2$ in $a_{n}$.  In this case,
Euler's theorem guarantees that $2^{\phi (n)}-1$ is divisible by $n$,
where $\phi (n)$ is the Euler $\phi $ function.  Since $\phi (n)<n$, the
result follows.  

\item[B--1]
This one boils down to the Law of Sines.  You can use the angles given
in the problem to compute every angle in the picture.  In particular, we
find that the triangle FBE is similar to the triangle ABC.  Therefore,
$|EF|=|BE|/|BC|.$  We have $|BC|=\tan \theta $.  To compute $|BE|$, we
use the law of sinces on the triangle DBE.  We find that 
\[
\frac{\sin \beta }{|BE|} = \frac{\sin 3\theta /2}{|BD|},
\]
where $\beta =\pi /2-\theta /2$.  Furthermore, $|BD|=\sec \theta -1$.
Either using L'Hopital's rule or the standard infinite series for the
trig functions, we find that the limit in question is $1/3$.  

\item[B--2] We can assume that $P(x)$ is monic.  Suppose $P(x)$ does not
have $n$ distinct roots.  Then $P(x)$ must have a double root, and
without loss of generality we can assume that double root is at $0$.
(This may necessitate introducing complex coefficients into $P(x)$, but
there may well have been complex coefficients already, so this is not a
problem).  Suppose $P(x)$ has a zero of order $k$ at $0$, so that
$P(x)=x^{k}R(x)$, where $R(0)\neq 0$.  Then the Leibnitz rule implies
that $P''(x)$ has a zero of order $k-2$ at $0$, since 
\[
P''(x) = k(k-1)x^{k-2}R(x) + 2kx^{k-1} R'(x) + x^{k}R''(x).
\]  
Since $P(x)=Q(x)P''(x)$, it follows that $Q(x)=(1/k(k-1))x^{2}$.
Applying the formula above, we find that $R'(x)=-\frac{x}{2k}R''(x)$.  A
comparison of the leading terms, which are both nonegative, shows the
only way this can happen is if $k=n$, that is, if $P$ has an $n$-fold
root.  Thus, if $P$ has two distinct roots, it must have $n$ distinct
roots.  

\item[B--3]
This one is merely a matter of rearranging the sum so most everything
cancels out.  The first step is to rewrite $S(x,y)$ by combining the
terms where $m>n$ with the terms where $m<n$, adding in the terms where
$m=n$ separately.  We get 
\[
S(x,y) = \sum _{n=1}^{\infty } x^{n}y^{n}(1+\sum _{m=1}^{n} x^{m}+y^{m}).
\]
We then find that 
\begin{align*}
x^{2}y S(x,y) & = \sum _{n=2}^{\infty } x^{n}y^{n}(\sum _{m=1}^{n}x^{m}) +
\sum _{n=3}^{\infty }x^{n}y^{n}(\sum _{m=0}^{n-3}y^{m}) \\
xy^{2} S(x,y) & = \sum _{n=2}^{\infty } x^{n}y^{n}(\sum _{m=1}^{n}y^{m}) +
\sum _{n=3}^{\infty }x^{n}y^{n}(\sum _{m=0}^{n-3}x^{m}) \\
x^{3}y^{3}S(x,y) & = \sum _{n=4}^{\infty } x^{n}y^{n}(1+\sum
_{m=1}^{n-3}x^{m}+y^{m}).  
\end{align*}
Using these, and much simplification, we get 
\[
(1-xy^{2})(1-x^{2}y)S(x,y) = xy(1+x+y)+x^{2}y^{2}-x^{3}y^{3}.
\]
Taking the limit as $x$ and $y$ go to $1$, we get $3$. 

\item[B--4]
(Got this one from Dave Rusin).  The first thing to note is that it
suffices to prove $f'(0)<2f(0)$, since $f(x-a)$ satisfies the hypotheses
of the problem whenever $f$ does.  By multiplying by a constant we can
assume $f(0)=1$.  Let $a=f'(0)$ and $b=f''(0)$, so we want to show
$a<2$.  

The point here is that if $g'(x)\leq h'(x)$ for all $x\leq 0$, and
$g(0)=h(0)$, then $g(x)\geq h(x)$ for all $x\leq 0$.  To apply this,
note that, since $f''(x)$ is increasing, we have $f''(x)\leq b$ for all
$x\leq 0$.  Hence $f'(x)\geq bx+a$ for all $x\leq 0$.  Hence $f(x)\leq
(1/2)bx^{2}+ax+1$ for all $x\leq 0$.  Since this quadratic has positive
coefficients, if it has any roots it will have to have negative roots.
Since $f(x)$ is positive, it can't have any negative roots.  Thus the
discriminant $a^{2}-2b$ must be negative, so $a^{2}<2b$.  
 
Similarly, $f(x)\leq 1$ for all $x\leq 0$, since $f$ is increasing.
Hence $f'''(x)\leq 1$ for all $x\leq 0$, using the assumption that
$f'''(x)\leq f(x)$.  Thus $f''(x)\geq x+b$ for all $x\leq 0$.  
Hence $f'(x)\leq (1/2)x^{2}+bx+a$ for all $x<0$.  This means, as above,
that this quadratic has no roots.  This its discriminant $b^{2}-2a$ must
be negative, so $b^{2}<2a$.  

Combining these two inequalities, we find that $a^{3}<8$, so $a<2$.  

\item[B--5] (This one I got from Robin Chapman).  The crucial
observation here is that $a_{j,k}=(1/2)(\zeta ^{j+k}+\zeta ^{-j-k})$,
where $\zeta =e^{2\pi i/n}$.  We construct a lot of eigenvectors for
$A$, as follows.  Given an integer $m$, define a vector $v(m)$ by
$v(m)_{k}=\zeta ^{mk}$.  The set of $v_{m}$ for $0\leq
m\leq n-1$ is a basis for $n$-dimensional complex vector space, using
the fact that $\zeta $ is a primitive $n$th root of unity.  

We have 
\begin{align*}
Av_{m}& = (1/2)\sum _{j=1}^{n}(\zeta ^{j+k+mj}+\zeta ^{-j-k+mj}) \\
& = (1/2)(\zeta ^{k}\sum _{j=1}^{n} (\zeta ^{m+1})^{j} + \zeta ^{-k}\sum
_{j=1}^{n} (\zeta ^{m-1})^{j}).
\end{align*}
Each of these sums is a well-known geometric series, whose sum is $0$ if
the root of unity is not $1$ and $n$ if the root of unity is $1$.  Hence
$Av_{m}=0$ if $2\leq m\leq n-2$ or if $m=0$, and $Av_{1}=(n/2)v_{n-1}$,
and $Av_{n-1}=(n/2)v_{1}$.  Thus, $A$ is similar to the block matrix 
\[
\begin{array}{cc}
0 & 0 \\
0 & B 
\end{array}
\]
where $B$ is the matrix 
\[
\begin{array}{cc}
0 & n/2 \\
n/2 & 0
\end{array}
\]
The determinant of $I+A$ is then easily seen to be $1-n^{2}/4$.  

\item[B--6] 

(Solution due to Prof. Karen Collins at Wesleyan)  Let $S$ be a finite
set of integers as in the problem.  Define the support of $S$ to be the
collection of all primes that divide some element of $S$.  Now let $r$
be the smallest integer such that there is some list of primes
$p_{1},\dots ,p_{r}$ in the support of $S$ such that $\gcd
(p_{1}p_{2}\dots p_{r},s)>1$ for all $s\in S$.  This means there must be
some element $s_{0}$ of $S$ such that $\gcd(p_{1}p_{2}\dots
p_{r},s_{0})=s_{0}$, so that $s_{0}$ is a product of some of the
$p_{i}$.  Suppose without loss of generality that $p_{r}$ divides $s$.
By the way we chose $r$ , there is some element $t$ of $S$ such that
$\gcd(p_{1}p_{2}\dots p_{r-1},t)=1$.  But $\gcd(p_{1}p_{2}\dots
p_{r},t)>1$, so $p_{r}$ divides $t$.  Hence the gcd of $s_{0}$ and $t$
is $p_{r}$.  
\end{itemize}

\end{document}