\documentclass[amssymb,twocolumn]{revtex4}
\usepackage{times,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 $f$ which satisfy
\begin{eqnarray*}
\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{eqnarray*}
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}