%% 1993 Putnam exam questions
%% Entered by Kiran Kedlaya

\documentstyle[12pt]{article}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\textheight}{8.5in}
\setlength{\topmargin}{0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\parskip}{0pt}
\setlength{\parindent}{20pt}

\def\binom#1#2{{#1\choose#2}}
\def\head#1{{\large \bf #1}}
\def\bR{{\mathbf{R}}}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{prop}{Proposition}

\begin{document}

\begin{center}
\bf
The Fifty-Fourth William Lowell Putnam Mathematical Competition \\
December 4, 1993
\end{center}

\head{A-1} The horizontal line $y=c$ intersects the curve $y = 2x - 3x^3$ 
in the first quadrant as in the figure. Find $c$ so that the areas of the 
two shaded regions are equal. [Figure not included. The first region is 
bounded by the $y$-axis, the line $y=c$ and the curve; the other lies 
under the curve and above the line $y=c$ between their two points of 
intersection.]

\head{A-2} Let $(x_n)_{n \geq 0}$ be a sequence of nonzero real numbers 
such that $x_n^2 - x_{n-1}x_{n+1} = 1$ for $n=1,2,3,\dots$. Prove there 
exists a real number $a$ such that $x_{n+1} = ax_n - x_{n-1}$ for all $n 
\geq 1$.

\head{A-3} Let ${\cal P}_n$ be the set of subsets of $\{1, 2, \dots, 
n\}$. Let $c(n, m)$ be the number of functions $f: {\cal P}_n \to \{1, 2, 
\dots, m\}$ such that $f(A \cap B) = \min\{f(A), f(B)\}$. Prove that
\[
c(n, m) = \sum_{j=1}^m j^n.
\]

\head{A-4} Let $x_1, x_2, \dots, x_{19}$ be positive integers each of 
which is less than or equal to 93. Let $y_1, y_2, \dots, y_{93}$ be 
positive integers each of which is less than or equal to 19. Prove that 
there exists a (nonempty) sum of some $x_i$'s equal to a sum of some $y_j$'s.

\head{A-5} Show that
\[
\int_{-100}^{-10} \left( \frac{x^2 - x}{x^3 - 3x + 1} \right)^2\,dx +
\int_{\frac{1}{101}}^{\frac{1}{11}} \left( \frac{x^2 - x}{x^3 - 3x + 1} \right)^2\,dx +
\int_{\frac{101}{100}}^{\frac{11}{10}} \left( \frac{x^2 - x}{x^3 - 3x + 1} \right)^2\,dx
\]
is a rational number.

\head{A-6}
The infinite sequence of 2's and 3's
\[
2,3,3,2,3,3,3,2,3,3,3,2,3,3,2,3,3,3,2,3,3,3,2,3,3,3,2,3,3,2,3,3,3,2,\dots
\]
has the property that, if one forms a second sequence that records the 
number of 3's between successive 2's, the result is identical to the 
given sequence. Show that there exists a real number $r$ such that, for 
any $n$, the $n$th term of the sequence is 2 if and only if $n = 1 + 
\lfloor rm \rfloor$ for some nonnegative integer $m$. (Note: $\lfloor x 
\rfloor$ denotes the largest integer less than or equal to $x$.)
\pagebreak
\head{B-1}
Find the smallest positive integer $n$ such that for every integer $m$ 
with $0 < m < 1993$, there exists an integer $k$ for which
\[
\frac{m}{1993} < \frac{k}{n} < \frac{m+1}{1994}.
\]

\head{B-2}
Consider the following game played with a deck of $2n$ cards numbered 
from 1 to $2n$. The deck is randomly shuffled and $n$ cards are dealt to 
each of two players. Beginning with $A$, the players take turns 
discarding one of their remaining cards and announcing its number. The 
game ends as soon as the sum of the numbers on the discarded cards is 
divisible by $2n+1$. The last person to discard wins the game. Assuming 
optimal strategy by both $A$ and $B$, what is the probability that $A$ wins?

\head{B-3}
Two real numbers $x$ and $y$ are chosen at random in the interval (0,1) 
with respect to the uniform distribution. What is the probability that 
the closest integer to $x/y$ is even? Express the answer in the form 
$r+s\pi$, where $r$ and $s$ are rational numbers.

\head{B-4}
The function $K(x,y)$ is positive and continuous for $0 \leq x \leq 1, 0 
\leq y \leq 1$, and the functions $f(x)$ and $g(x)$ are positive and 
continuous for $0 \leq x \leq 1$. Suppose that for all $x$, $0 \leq x \leq 1$,
\[
\int_0^1 f(y)K(x,y)\,dy = g(x) \mbox{\qquad and \qquad}
\int_0^1 g(y)K(x,y)\,dy = f(x).
\]
Show that $f(x) = g(x)$ for $0 \leq x \leq 1$.

\head{B-5}
Show there do not exist four points in the Euclidean plane such that the 
pairwise distances between the points are all odd integers.

\head{B-6}
Let $S$ be a set of three, not necessarily distinct, positive integers.
Show that one can transform $S$ into a set containing 0 by a finite 
number of applications of the following rule: Select two of the three 
integers, say $x$ and $y$, where $x < y$ and replace them with $2x$ and $y-x$.

\end{document}