The 1994 William Lowell Putnam Mathematical Competition
December 3, 1994
transcribed by Kiran Kedlaya (kedlaya@math.harvard.edu)
...but nonetheless (C) 1994 of the Mathematical Association of America

This file should be suitable for processing by any flavor of TeX.

A1:
Let $(a_n)$ be a sequence of positive reals such that, for all $n$,
$a_n \leq a_{2n} + a_{2n+1}$. Prove that $\sum_{n=1}^{\infty} a_n$
diverges.

A2:
Find the positive value of $m$ such that the area in the first
quadrant enclosed by the ellipse $\frac{x^2}{9} + y^2 = 1$, the
$x$-axis, and the line $y = 2x/3$ is equal to the area in the first
quadrant enclosed by the ellipse $\frac{x^2}{9} + y^2 = 1$, the
$y$-axis, and the line $y = mx$.

A3:
Prove that the points of an isosceles triangle of side length 1
annot be colored in four colors such that no two points at distance at
least $2 - \sqrt{2}$ from each other receive the same color.

A4:
Let $A$ and $B$ be $2 \times 2$ matrices with integer entries such
that each of $A, A+B, A+2B, A+3B, A+4B$ has an inverse with integer
entries. Prove that the same must be true of $A+5B$.

A5:
Let $(r_n)$ be a sequence of positive reals with limit 0. Let $S$ be the
set of all numbers expressible in the form $r_{i_1} + \dots +
r_{i_{1994}}$ for positive integers $i_1 < i_2 < \dots <
i_{1994}$. Prove that every interval $(a,b)$ contains a subinterval
$(c,d)$ whose intersection with $S$ is empty.

A6:
Let $f_1, \dots, f_{10}$ be bijections of the integers such that for
every integer $n$, there exists a sequence $i_1, \dots, i_k$ for some
$k$ such that $f_{i_1} \circ \dots \circ f_{i_k}(0) = n$. Prove that
if $A$ is any nonempty finite set, there exist at most 512 sequences
$(e_1, \dots, e_{10})$ of zeroes and ones such that $f_1^{e_1} \circ
\dots \circ f_{10}^{e_{10}}$ maps $A$ to $A$. (Here $f^1 = f$ and
$f^0$ means the identity function.)

B1:
Find all positive integers $n$ such that $|n - m^2| \leq 250$ for
exactly 15 nonnegative integers $m$.

% Note: a and b were specific numbers in the problem, but I've
% forgotten what they were, and the values are irrelevant.
B2:
Find all $c$ such that the graph of the function $x^4 + 9x^3 + cx^2 +
ax + b$ meets some line in four distinct points.

B3:
Let $f(x)$ be a positive-valued function over the reals such that
$f'(x) > f(x)$ for all $x$. For what $k$ must there exist $N$ such
that $f(x) > e^{kx}$ for $x > N$?

% Drawing out the matrix would have been dependent on a flavor of TeX.
B4:
Let $A$ be the matrix $((3 2) (4 2))$ and for positive integers $n$,
define $d_n$ as the greatest common divisor of the entries of $A^n -
I$, where $I = ((1 0) (0 1))$. Prove that $d_n \to \infty$ as $n \to
\infty$.

B5:
Fix $n$ a positive integer. For $\alpha$ real, define $f_{\alpha}(i)$ as the
greatest integer less than or equal to $\alpha i$, and write $f^k$ for
the $k$-th iterate of $f$ (i.e.\ $f^1 = f$ and $f^{k+1} = f \circ
f^k$). Prove there exists $\alpha$ such that $f_{\alpha^k}(n^2) =
f_{\alpha}^k(n^2) = n^2 - k$ for $k = 1, \dots, n$.

B6:
Suppose $a, b, c, d$ are integers with $0 \leq a \leq b leq 99$, $0
\leq c \leq d \leq 99$. For any integer $i$, let $n_i = 101 i + 100
2^i$. Show that if $n_a + n_b$ is congruent to $n_c + n_d$ mod 10100,
then $a = c$ and $b = d$.