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

\begin{document}
\title{The 75th William Lowell Putnam Mathematical Competition \\
    Saturday, December 6, 2014}
\maketitle

\begin{itemize}

\item[A1] 
Prove that every nonzero coefficient of the Taylor series of
\[
(1 - x + x^2)e^x
\]
about $x=0$ is a rational number whose numerator (in lowest terms) is either $1$ or a prime number.

\item[A2]
Let $A$ be the $n \times n$ matrix whose entry in the $i$-th row and $j$-th column is
\[
\frac{1}{\min(i,j)}
\]
for $1 \leq i,j \leq n$. Compute $\det(A)$.

\item[A3]
Let $a_0 = 5/2$ and $a_k = a_{k-1}^2 - 2$ for $k \geq 1$. Compute
\[
\prod_{k=0}^\infty \left(1 - \frac{1}{a_k} \right)
\]
in closed form.

\item[A4]
Suppose $X$ is a random variable that takes on only nonnegative integer values,
with $E\left[ X \right] = 1$, $E\left[ X^2 \right] = 2$, and $E \left[ X^3 \right] = 5$.
(Here $E\left[ y \right]$ denotes the expectation of the random variable $Y$.)
Determine the smallest possible value of the probability of the event $X=0$.

\item[A5]
Let
\[
P_n(x) = 1 + 2 x  + 3 x^2 + \cdots + n x^{n-1}.
\]
Prove that the polynomials $P_j(x)$
and $P_k(x)$ are relatively prime
for all positive integers $j$ and $k$ with $j \neq k$.

\item[A6]
Let $n$ be a positive integer. What is the largest $k$ for which there exist $n \times n$ matrices $M_1, \dots, M_k$ and $N_1, \dots, N_k$ with real entries such that for all $i$ and $j$, the matrix product $M_i N_j$ has a zero entry somewhere on its diagonal if and only if $i \neq j$?

\item[B1]
A \emph{base $10$ over-expansion} of a positive integer $N$ is an expression of the form
\[
N = d_k 10^k + d_{k-1} 10^{k-1} + \cdots + d_0 10^0
\]
with $d_k \neq 0$ and $d_i \in \{0,1,2,\dots,10\}$ for all $i$.
For instance, the integer $N = 10$ has two base 10 over-expansions: $10 = 10 \cdot 10^0$
and the usual base 10 expansion $10 = 1 \cdot 10^1 + 0 \cdot 10^0$.
Which positive integers have a unique base 10 over-expansion?

\item[B2]
Suppose that $f$ is a function on the interval $[1,3]$ such that $-1 \leq f(x) \leq 1$ for all $x$ and $\int_1^3 f(x)\,dx = 0$. How large can $\int_1^3 \frac{f(x)}{x}\,dx$ be?

\,

\item[B3]
Let $A$ be an $m \times n$ matrix with rational entries.
Suppose that there are at least $m+n$ distinct prime numbers among the absolute values of the entries of $A$. Show that the rank of $A$ is at least 2.

\item[B4]
Show that for each positive integer $n$, all the roots of the polynomial
\[
\sum_{k=0}^n 2^{k(n-k)} x^k
\]
are real numbers.

\item[B5]
In the 75th annual Putnam Games, participants compete at mathematical games.
Patniss and Keeta play a game in which they take turns choosing an element 
from the group of invertible $n \times n$ matrices with entries in the field
$\mathbb{Z}/p \mathbb{Z}$ of integers modulo $p$, where $n$ is a fixed positive integer and $p$ is a fixed prime number. The rules of the game are:
\begin{enumerate}
\item[(1)]
A player cannot choose an element that has been chosen by either player on any previous turn.
\item[(2)]
A player can only choose an element that commutes with all previously chosen elements.
\item[(3)]
A player who cannot choose an element on his/her turn loses the game.
\end{enumerate}
Patniss takes the first turn. Which player has a winning strategy?
(Your answer may depend on $n$ and $p$.)

\item[B6]
Let $f: [0,1] \to \mathbb{R}$ be a function for which there exists a constant $K>0$
such that $\left| f(x) - f(y) \right| \leq K \left| x - y \right|$ for all $x,y \in [0,1]$.
Suppose also that for each rational number $r \in [0,1]$, there exist integers $a$ and $b$
such that $f(r) = a + br$. Prove that there exist finitely many intervals $I_1, \dots, I_n$
such that $f$ is a linear function on each $I_i$ and $[0,1] = \bigcup_{i=1}^n I_i$. 

\end{itemize}

\end{document}
