\documentclass[amssymb,twocolumn,pra,10pt,aps]{revtex4-1}
\usepackage{mathptmx,amsmath}
\begin{document}
\title{The 67th William Lowell Putnam Mathematical Competition \\
Saturday, December 2, 2006}
\maketitle
\begin{itemize}
\item[A1]
Find the volume of the region of points $(x,y,z)$ such that
\[
(x^2 + y^2 + z^2 + 8)^2 \leq 36(x^2 + y^2).
\]
\item[A2]
Alice and Bob play a game in which they take turns removing stones from
a heap that initially has $n$ stones. The number of stones removed at
each turn must be one less than a prime number. The winner is the player
who takes the last stone. Alice plays first. Prove that there are
infinitely many $n$ such that Bob has a winning strategy.
(For example, if $n=17$, then Alice might take 6 leaving 11; then
Bob might take 1 leaving 10; then Alice can take the remaining stones
to win.)
\item[A3]
Let $1, 2, 3, \dots, 2005, 2006, 2007, 2009, 2012, 2016, \dots$
be a sequence defined by $x_k = k$ for $k=1, 2, \dots, 2006$ and
$x_{k+1} = x_k + x_{k-2005}$ for $k \geq 2006$. Show that the sequence has
2005 consecutive terms each divisible by 2006.
\item[A4]
Let $S = \{1, 2, \dots, n\}$ for some integer $n > 1$. Say a permutation
$\pi$ of $S$ has a \emph{local maximum} at $k \in S$ if
\begin{enumerate} % The for parts are aligned in the AMM version
\item[(i)]
$\pi(k) > \pi(k+1)$ for $k=1$;
\item[(ii)]
$\pi(k-1) < \pi(k)$ and $\pi(k) > \pi(k+1)$ for $1 < k < n$;
\item[(iii)]
$\pi(k-1) < \pi(k)$ for $k=n$.
\end{enumerate}
(For example, if $n=5$ and $\pi$ takes values at $1, 2, 3, 4, 5$ of
$2, 1, 4, 5, 3$, then $\pi$ has a local maximum of 2 at $k=1$,
and a local maximum of 5 at $k=4$.)
What is the average number of local maxima of a permutation of $S$,
averaging over all permutations of $S$?
\item[A5]
Let $n$ be a positive odd integer and let $\theta$ be a real number such
that $\theta/\pi$ is irrational. Set $a_k = \tan (\theta + k \pi/n)$,
$k=1,2,\dots,n$. Prove that
\[
\frac{a_1 + a_2 + \cdots + a_n}{a_1 a_2 \cdots a_n}
\]
is an integer, and determine its value.
\item[A6]
Four points are chosen uniformly and independently at random in the interior
of a given circle. Find the probability that they are the vertices
of a convex quadrilateral.
\item[B1]
Show that the curve $x^3 + 3xy + y^3 = 1$ contains only one set of three
distinct points, $A$, $B$, and $C$, which are vertices of an equilateral
triangle, and find its area.
\item[B2]
Prove that, for every set $X = \{x_1, x_2, \dots, x_n\}$ of $n$
real numbers, there exists a non-empty subset $S$ of $X$ and an integer $m$
such that
\[
\left| m + \sum_{s \in S} s \right| \leq \frac{1}{n+1}.
\]
\item[B3]
Let $S$ be a finite set of points in the plane. A linear partition of $S$
is an unordered pair $\{A,B\}$ of subsets of $S$ such that $A \cup B = S$,
$A \cap B = \emptyset$, and $A$ and $B$ lie on opposite sides of some
straight line disjoint from $S$ ($A$ or $B$ may be empty). Let $L_S$ be the
number of linear partitions of $S$. For each positive integer $n$, find the
maximum of $L_S$ over all sets $S$ of $n$ points.
\item[B4]
Let $Z$ denote the set of points in $\mathbb{R}^n$ whose coordinates are 0
or 1. (Thus $Z$ has $2^n$ elements, which are the vertices of a unit
hypercube in $\mathbb{R}^n$.) Given a vector subspace $V$
of $\mathbb{R}^n$, let $Z(V)$
denote the number of members of $Z$ that lie in $V$. Let $k$ be given,
$0 \leq k \leq n$. Find the maximum, over all vector subspaces $V
\subseteq \mathbb{R}^n$ of dimension $k$, of the number of points in
$V \cap Z$. [Editorial note: the proposers probably intended to write
$Z(V)$ instead of
``the number of points in $V \cap Z$'', but this changes nothing.]
\item[B5]
For each continuous function $f: [0,1] \to \mathbb{R}$, let $I(f) =
\int_0^1 x^2 f(x)\,dx$ and $J(x) = \int_0^1 x \left(f(x)\right)^2\,dx$.
Find the maximum value of $I(f) - J(f)$ over all such functions $f$.
\item[B6]
Let $k$ be an integer greater than 1. Suppose $a_0 > 0$, and define
\[
a_{n+1} = a_n + \frac{1}{\sqrt[k]{a_n}}
\]
for $n > 0$. Evaluate
\[
\lim_{n \to \infty} \frac{a_n^{k+1}}{n^k}.
\]
\end{itemize}
\end{document}