\documentclass[11pt]{article}
\def\Z{\mathbb{Z}}
\def\Q{\mathbb{Q}}
\usepackage{latexsym,amsmath,amssymb,float,graphicx,subfig}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\textheight}{8.6in}
\setlength{\topmargin}{-0.6in}
\newtheorem{theorem}{Theorem}
\begin{document}
\centerline{76th Annual William Lowell Putnam Mathematical Competition}
\centerline{December 5, 2015}
\vskip 10pt
\noindent
\begin{itemize}
\item {\bf Problem A1.}  Let $A$ and $B$ be points on the same branch of the hyperbola
$xy = 1$.  Suppose that $P$ is a point lying between $A$ and $B$ on this hyperbola, such 
that the area of the triangle $APB$ is as large as possible.  Show that the region bounded
by the hyperbola and the chord $AP$ has the same area as the region bounded by the hyperbola
and the chord $PB$.
\item[]
\item {\bf Problem A2.}  Let $a_0 = 1$, $a_2 = 2$ and $a_n = 4a_{n-1} - a_{n-2}$ for $n \ge 2$.
Find an odd prime factor of $a_{2015}$.  
\item[]
\item {\bf Problem A3.}  Compute 
$$\log_2\left(\prod_{a=1}^{2015} \prod_{b=1}^{2015} \left(1 + e^{2\pi i a b/2015}\right)\right)$$
Here $i$ is the imaginary unit (that is, $i^2 = -1$). 
\item[]
\item {\bf Problem A4.}  For each real number $x$, let 
$$f(x) = \sum_{n \in S_x} \frac{1}{2^n},$$
where $S_x$ is the set of positive integers $n$ for which $\lfloor nx\rfloor$ is even.
What is the largest real number $L$ such that $f(x) \ge L$ for all $x \in [0,1)$?
(As usual $\lfloor z\rfloor$ denotes the greatest integer less than or equal to $z$.)
\item[]
\item {\bf Problem A5.} Let $q$ be an odd positive integer, and let $N_q$ denote the 
number of integers $a$ such that $0 < a < q/4$ and $\gcd(a,q) = 1$.  Show that $N_q$
is odd if and only if $q$ is of the form $p^k$ with $k$ a positive integer and $p$ a prime
congruent to $5$ or $7$ modulo 8.
\item[]
\item {\bf Problem A6.} Let $n$ be a positive integer.  Suppose that $A,B,M$ are $n\times n$
matrices with real entries such that $AM = MB$, and such that $A$ and $B$ have the same
characteristic polynomial.  Prove that $\det(A - MX) = \det(B - XM)$ for every $n\times n$
matrix $X$ with real entries.  
\item[]
\item {\bf Problem B1.} Let $f$ be three times differentiable function (defined on 
$\mathbb{R}$ and real-valued) such that $f$ has at least five distinct zeroes.
Show that $f + 6f' + 12f'' + 8f'''$ has at least two distinct real zeroes.  
\item[]
\item {\bf Problem B2.} Given a list of the positive integers $1,2,3,4,\ldots,$ take the first
three numbers $1,2,3$ and their sum $6$ and cross all four numbers off the list.  Repeat
with the three smallest remaining numbers $4,5,7$ and their sum $16$.  Continue in this
way, crossing off the three smallest remaining numbers and their sum, and continue the 
sequence of sums produced: $6,16,27,36,\ldots$.  Prove or disprove that there is 
some number in this sequence whose base 10 representation ends in $2015$.
\item[] 
\item {\bf Problem B3.} Let $S$ be the set of all $2 \times 2$ real matrices
$$M = \begin{pmatrix} a & b\\ c & d\end{pmatrix}$$
whose entries $a,b,c,d$ (in that order) form an arithmetic progression.  Find all 
matrices $M$ in $S$ for which there is some integer $k > 1$ such that $M^k$ is also in $S$.
\item[]
\item {\bf Problem B4.}  Let $T$ be the set of all triples $(a,b,c)$ of positive integers
for which there exist triangles with side lengths $a,b,c$.  Express 
$$\sum_{(a,b,c) \in T} \frac{2^a}{3^b 5^c}$$
as a rational number in lowest terms.
\item[] 
\item {\bf Problem B5.} Let $P_n$ be the number of permutations $\pi$ of $\{1,2,\ldots,n\}$
such that 
$$|i - j| = 1\ {\rm implies}\ |\pi(i) - \pi(j)| \le 2$$
for all $i,j$ in $\{1,2,\ldots,n\}$.  Show that for $n \ge 2$, the quantity 
$$P_{n+5} - P_{n+4} - P_{n+3} + P_n$$
does not depend on $n$ and find its value.
\item[]
\item {\bf Problem B6.}  For each positive integer $k$, let $A(k)$ be the number
of odd divisors of $k$ in the interval $[1,\sqrt{2k})$.  Evaluate
$$\sum_{k=1}^\infty (-1)^{k-1} \frac{A(k)}{k}.$$
\end{itemize}
\end{document} 
