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

\begin{document}
\title{The 56th William Lowell Putnam Mathematical Competition \\
    Saturday, December 2, 1995\vspace{-2\baselineskip}}
\maketitle

\begin{itemize}
\item[A--1] Let $S$ be a set of real numbers which is closed under
multiplication (that is, if $a$ and $b$ are in $S$, then so is $ab$).
Let $T$ and $U$ be disjoint subsets of $S$ whose union is $S$. Given
that the product of any {\em three} (not necessarily distinct)
elements of $T$ is in $T$ and that the product of any three elements
of $U$ is in $U$, show that at least one of the two subsets $T,U$ is
closed under multiplication.

\item[A--2] For what pairs $(a,b)$ of positive real numbers does the
improper integral
\[
\int_{b}^{\infty} \left( \sqrt{\sqrt{x+a}-\sqrt{x}} -
\sqrt{\sqrt{x}-\sqrt{x-b}} \right)\,dx
\]
converge?

\item[A--3] The number $d_{1}d_{2}\dots d_{9}$ has nine (not
necessarily distinct) decimal digits. The number $e_{1}e_{2}\dots
e_{9}$ is such that each of the nine 9-digit numbers formed by
replacing just one of the digits $d_{i}$ is $d_{1}d_{2}\dots d_{9}$
by the corresponding digit $e_{i}$ ($1 \leq i \leq 9$) is divisible
by 7. The number $f_{1}f_{2}\dots f_{9}$ is related to
$e_{1}e_{2}\dots e_{9}$ is the same way: that is, each of the nine
numbers formed by replacing one of the $e_{i}$ by the corresponding
$f_{i}$ is divisible by 7. Show that, for each $i$, $d_{i}-f_{i}$ is
divisible by 7. [For example, if $d_{1}d_{2}\dots d_{9} = 199501996$,
then $e_{6}$ may be 2 or 9, since $199502996$ and $199509996$ are
multiples of 7.]

\item[A--4] Suppose we have a necklace of $n$ beads. Each bead is
labeled with an integer and the sum of all these labels is $n-1$.
Prove that we can cut the necklace to form a string whose
consecutive labels $x_{1},x_{2},\dots,x_{n}$ satisfy
\[
\sum_{i=1}^{k} x_{i} \leq k-1 \qquad \mbox{for} \quad k=1,2,\dots,n.
\]

\item[A--5] Let $x_{1},x_{2},\dots,x_{n}$ be differentiable
(real-valued) functions of a single variable $t$ which satisfy
\begin{align*}
\frac{dx_{1}}{dt} &= a_{11}x_{1} + a_{12}x_{2} + \cdots +
a_{1n}x_{n} \\
\frac{dx_{2}}{dt} &= a_{21}x_{1} + a_{22}x_{2} + \cdots +
a_{2n}x_{n} \\
\vdots && \vdots \\
\frac{dx_{n}}{dt} &= a_{n1}x_{1} + a_{n2}x_{2} + \cdots +
a_{nn}x_{n}
\end{align*}
for some constants $a_{ij}>0$. Suppose that for all $i$, $x_{i}(t)
\to 0$ as $t \to \infty$. Are the functions $x_{1},x_{2},\dots,x_{n}$
necessarily linearly dependent?

\item[A--6] Suppose that each of $n$ people writes down the numbers
1,2,3 in random order in one column of a $3 \times n$ matrix, with
all orders equally likely and with the orders for different columns
independent of each other. Let the row sums $a,b,c$ of the resulting
matrix be rearranged (if necessary) so that $a \leq b \leq c$. Show
that for some $n \geq 1995$, it is at least four times as likely that
both $b=a+1$ and $c=a+2$ as that $a=b=c$.

\item[B--1]  For a partition $\pi$ of $\{1, 2, 3, 4, 5, 6, 7, 8, 9\}$,
let $\pi(x)$ be the number of elements in the part containing $x$.
Prove that for any two partitions $\pi$ and $\pi'$, there are two
distinct numbers $x$ and $y$ in $\{1, 2, 3, 4, 5, 6, 7, 8, 9\}$
such that $\pi(x) = \pi(y)$ and $\pi'(x) = \pi'(y)$. [A {\em
partition} of a set $S$ is a collection of disjoint subsets (parts)
whose union is $S$.]

\item[B--2] An ellipse, whose semi-axes have lengths $a$ and $b$,
rolls without slipping on the curve $y = c \sin \left( \frac{x}{a}
\right)$. How are $a,b,c$ related, given that the ellipse completes
one revolution when it traverses one period of the curve?

\item[B--3] To each positive integer with $n^{2}$ decimal digits, we
associate the determinant of the matrix obtained by writing the
digits in order across the rows. For example, for $n=2$, to the
integer 8617 we associate $\det \left(
 \begin{array}{cc} 8 & 6 \\
1 & 7 \end{array} \right) = 50$. Find, as a function of $n$, the
sum of all the determinants associated with $n^{2}$-digit
integers. (Leading digits are assumed to be nonzero; for example,
for $n=2$, there are 9000 determinants.)

\item[B--4] Evaluate
\[
\sqrt[8]{2207 - \frac{1}{2207-\frac{1}{2207-\dots}}}.
\]
Express your answer in the form $\frac{a+b\sqrt{c}}{d}$, where
$a,b,c,d$ are integers.

\item[B--5] A game starts with four heaps of beans, containing 3,4,5
and 6 beans. The two players move alternately. A move consists of
taking \textbf{either}
\begin{itemize}
\item[a)] one bean from a heap, provided at least two beans are
left behind in that heap, \textbf{or}

\item[b)] a complete heap of two or three beans.
\end{itemize}
The player who takes the last heap wins. To win the game, do you
want to move first or second? Give a winning strategy.

\item[B--6] For a positive real number $\alpha$, define
\[
S(\alpha) = \{ \lfloor n\alpha \rfloor : n = 1,2,3,\dots \}.
\]
Prove that $\{1,2,3,\dots\}$ cannot be expressed as the disjoint
union of three sets $S(\alpha), S(\beta)$ and $S(\gamma)$. [As
usual, $\lfloor x \rfloor$ is the greatest integer $\leq x$.]

\end{itemize}
\end{document}
