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

\begin{document}
\title{The 79th William Lowell Putnam Mathematical Competition \\
    Saturday, December 1, 2018}
\maketitle

\begin{itemize}

\item[A1]
Find all ordered pairs $(a,b)$ of positive integers for which
\[
\frac{1}{a} + \frac{1}{b} = \frac{3}{2018}.
\]

\item[A2]
Let $S_1, S_2, \dots, S_{2^n-1}$ be the nonempty subsets of $\{1,2,\dots,n\}$ in some order, and let
$M$ be the $(2^n-1) \times (2^n-1)$ matrix whose $(i,j)$ entry is
\[
m_{ij} = \begin{cases} 0 & \mbox{if }S_i \cap S_j = \emptyset; \\
1 & \mbox{otherwise.}
\end{cases}
\]
Calculate the determinant of $M$.

\item[A3]
Determine the greatest possible value of $\sum_{i=1}^{10} \cos(3x_i)$ for real numbers $x_1,x_2,\dots,x_{10}$
satisfying $\sum_{i=1}^{10} \cos(x_i) = 0$.
 
\item[A4]
Let $m$ and $n$ be positive integers with $\gcd(m,n) = 1$, and let
\[
a_k = \left\lfloor \frac{mk}{n} \right\rfloor - \left\lfloor \frac{m(k-1)}{n} \right\rfloor
\]
for $k=1,2,\dots,n$.
Suppose that $g$ and $h$ are elements in a group $G$ and that 
\[
gh^{a_1} gh^{a_2} \cdots gh^{a_n} = e,
\]
where $e$ is the identity element. Show that $gh= hg$. (As usual, $\lfloor x \rfloor$ denotes the greatest integer
less than or equal to $x$.)
 
\item[A5]
Let $f: \mathbb{R} \to \mathbb{R}$ be an infinitely differentiable function satisfying $f(0) = 0$, $f(1)= 1$,
and $f(x) \geq 0$ for all $x \in \mathbb{R}$. Show that there exist a positive integer $n$ and a real number $x$
such that $f^{(n)}(x) < 0$.

\item[A6] 
Suppose that $A,B,C,$ and $D$ are distinct points, no three of which lie on a line,
in the Euclidean plane. Show
that if the squares of the lengths of the line segments $AB$, $AC$, $AD$, $BC$, $BD$, and $CD$
are rational numbers, then
the quotient
\[
\frac{\mathrm{area}(\triangle ABC)}{\mathrm{area}(\triangle ABD)}
\]
is a rational number.

\item[B1]
Let $\mathcal{P}$ be the set of vectors defined by
\[
\mathcal{P} = \left\{ \left. \begin{pmatrix} a \\ b \end{pmatrix} \right| 0 \leq a \leq 2, 0 \leq b \leq 100, \mbox{ and } a,b \in \mathbb{Z} \right\}.
\]
Find all $\mathbf{v} \in \mathcal{P}$ such that the set $\mathcal{P} \setminus \{ \mathbf{v} \}$ obtained by omitting
vector $\mathbf{v}$ from $\mathcal{P}$ can be partitioned into two sets of equal size and equal sum. 

\item[B2]
Let $n$ be a positive integer, and let $f_n(z) = n + (n-1) z + (n-2)z^2 + \cdots + z^{n-1}$. Prove that
$f_n$ has no roots in the closed unit disk $\{z \in \mathbb{C}\colon |z| \leq 1 \}$.

\item[B3]
Find all positive integers $n < 10^{100}$ for which simultaneously $n$ divides $2^n$, $n-1$ divides $2^n-1$,
and $n-2$ divides $2^n - 2$.

\item[B4]
Given a real number $a$, we define a sequence by $x_0 = 1$, $x_1 = x_2 = a$, and $x_{n+1} = 2x_n x_{n-1} - x_{n-2}$ for $n \geq 2$. Prove that if $x_n = 0$ for some $n$, then the sequence is periodic.

\item[B5]
Let $f = (f_1, f_2)$ be a function from $\mathbb{R}^2$ to $\mathbb{R}^2$ with continuous partial derivatives
$\frac{\partial f_i}{\partial x_j}$ that are positive everywhere. Suppose that
\[
\frac{\partial f_1}{\partial x_1} \frac{\partial f_2}{\partial x_2} - \frac{1}{4} \left( \frac{\partial f_1}{\partial x_2}  + \frac{\partial f_2}{\partial x_1} \right)^2 > 0
\]
everywhere. Prove that $f$ is one-to-one.

\item[B6]
Let $S$ be the set of sequences of length $2018$ whose terms  are in the set $\{1,2,3,4,5,6,10\}$ and sum to $3860$.
Prove that the cardinality of $S$ is at most
\[
2^{3860} \cdot \left( \frac{2018}{2048} \right)^{2018}.
\]

\end{itemize}

\end{document}
