\documentclass[amssymb,twocolumn,pra,10pt,aps]{revtex4-1}
\usepackage{mathptmx,amsmath, multirow}

\begin{document}
\title{The 76th William Lowell Putnam Mathematical Competition \\
    Saturday, December 5, 2015}
\maketitle

\begin{itemize}

\item[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[A2]
Let $a_0=1$, $a_1=2$, and $a_n=4a_{n-1}-a_{n-2}$ for $n\geq 2$. Find an odd prime factor of $a_{2015}$.

\item[A3]
Compute
\[
\log_2 \left( \prod_{a=1}^{2015} \prod_{b=1}^{2015} (1+e^{2\pi i a b/2015}) \right)
\]
Here $i$ is the imaginary unit (that is, $i^2=-1$). 

\item[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) \geq L$ for all $x \in [0,1)$? (As usual, $\lfloor z \rfloor$ denotes the greatest integer less than or equal to $z$.)

\item[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[A6]
Let $n$ be a positive integer. Suppose that $A$, $B$, and $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[B1]
Let $f$ be a three times differentiable function (defined on $\mathbb{R}$ and real-valued) such that $f$ has at least five distinct real zeros. Prove that $f + 6f' + 12f'' + 8f'''$ has at least two distinct real zeros.

\item[B2]
Given a list of the positive integers $1,2,3,4,\dots$, 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 consider the sequence of sums produced: $6, 16, 27, 36, \dots$. Prove or disprove that there is some number in the sequence whose base 10 representation ends with $2015$.

\,
\item[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[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[B5]
Let $P_n$ be the number of permutations $\pi$ of $\{1,2,\dots,n\}$ such that
\[
|i-j| = 1 \mbox{ implies } |\pi(i) -\pi(j)| \leq 2
\]
for all $i,j$ in $\{1,2,\dots,n\}$. Show that for $n \geq 2$, the quantity
\[
P_{n+5} - P_{n+4} - P_{n+3} + P_n
\]
does not depend on $n$, and find its value.

\item[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}
