\documentclass[12pt]{article}
\usepackage{latexsym}

\setlength{\textheight}{8.75in}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{0.0in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\leftmargin}{0.0in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\parindent}{1pc}

\def\head#1{{\medskip \bf \noindent #1}}

\begin{document}

\begin{center}
The Fifty-Sixth Annual William Lowell Putnam Mathematical 
Competition \\
Saturday, December 2, 1995
\end{center}

\begin{itemize}
	\item[A1] 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[A2] 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[A3] 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[A4] 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[A5] 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[A6] 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$.
	
	\end{itemize}
	\begin{itemize}
		\item[B1]  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[B2] 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[B3] 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[B4] 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[B5] 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[B6] 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}