\mag1200
\vsize 7.5in
\hsize 5.3in
\parskip 6pt
\parindent 0pt
\nopagenumbers
\def\problem #1.
#2

{\expandafter\def\csname #1\endcsname{#2}{\bf Problem #1}\par #2\par}
\def\solution #1.
{{\bf Problem #1}\par\csname #1\endcsname\par\indent\hbox{\bf Solution: }}
\def\comments{\vfill\eject\noindent\hbox{\bigbold Comments}\par\bigskip}
\def\startprobs{\bigskip\noindent\hbox{\bigbold Problems}\par\bigskip}
\def\startsolns{\bigskip\noindent\hbox{\bigbold Unofficial solutions}\par\bigskip}
\def\setof#1{\left\{#1\right\}}
\def\floor#1{\left\lfloor#1\right\rfloor}
\def\tr{\mathop{\rm tr}}
\def\F{F}

\font\bigbold=cmbx12
{\bigbold 1994 Putnam problems and unofficial solutions, revised}\bigskip

As usual,
first come the problems,
then the problems with solutions.
Comments and criticism at the end.

Send any followup remarks to the {\tt USENET} newsgroup {\tt sci.math}.

\startprobs

\problem A1.
Suppose that a sequence $a_1,a_2,a_3,\ldots$
satisfies $0<a_n\le a_{2n}+a_{2n+1}$
for all $n\ge 1$.
Prove that the series $\sum_{n=1}^{\infty} a_n$ diverges.

\problem A2.
Let $A$ be the area of the region in the first quadrant
bounded by the line $y={1\over 2}x$, the $x$-axis,
and the ellipse ${1\over 9}x^2 + y^2 = 1$.
Find the positive number $m$
such that $A$ is equal to
the area of the region in the first quadrant
bounded by the line $y=mx$, the $y$-axis,
and the ellipse ${1\over 9}x^2 + y^2 = 1$.

\problem A3.
Show that if the points of an isosceles right triangle
of side length $1$
are each colored with one of four colors,
then there must be two points of the same color
which are at least a distance $2-\sqrt2$ apart.

\problem A4.
Let $A$ and $B$ be $2\times 2$ matrices with integer entries
such that $A$, $A+B$, $A+2B$, $A+3B$, and $A+4B$
are all invertible matrices
whose inverses have integer entries.
Show that $A+5B$ is invertible
and that its inverse has integer entries.

\problem A5.
Let $(r_n)_{n\ge 0}$
be a sequence of positive real numbers
such that $\lim_{n\to\infty} r_n=0$.
Let $S$ be the set of numbers representable as a sum
$$r_{i_1}+r_{i_2}+\cdots+r_{i_{1994}},\qquad
\hbox{with $i_1<i_2<\cdots<i_{1994}$}.$$
Show that every nonempty interval $(a,b)$
contains a nonempty subinterval $(c,d)$
that does not intersect $S$.

\problem A6.
Let $f_1,f_2,\ldots,f_{10}$
be bijections of the set of integers
such that for each integer $n$,
there is some composition $f_{i_1}\circ f_{i_2}\circ\cdots\circ f_{i_n}$
of these functions (allowing repetitions)
which maps $0$ to $n$.
Consider the set of $1024$ functions
$$\F=\setof{f_1^{e_1}\circ f_2^{e_2}\circ\cdots\circ f_{10}^{e_{10}}
\mathbin{\vert} e_i = \hbox{$0$ or $1$ for $1\le i\le 10$}}$$
($f_i^0$ is the identity function and $f_i^1=f_i$).
Show that if $A$ is any nonempty finite set of integers,
then at most $512$ of the functions in $F$
map $A$ to itself.

\problem B1.
Find all positive integers that are
within $250$ of exactly $15$ perfect squares.
(Note: A {\bf perfect square} is the square of an integer;
that is, a member of the set $\setof{0,1,4,9,16,\ldots}$.
$a$ is {\bf within} $n$ of $b$ if $b-n\le a\le b+n$.)

\problem B2.
For which real numbers $c$ is there a straight line
that intersects the curve
$$y=x^4+9x^3+cx^2+9x+4$$
in four distinct points?

\problem B3.
Find the set of all real numbers $k$ with the following property:
For any positive, differentiable function $f$
that satisfies $f'(x)>f(x)$ for all $x$,
there is some number $N$ such that
$f(x)>e^{kx}$ for all $x>N$.

\problem B4.
For $n\ge 1$,
let $d_n$ be the greatest common divisor of
the entries of $A^n-I$,
where $A=\pmatrix{3&2\cr 4&3\cr}$
and $I=\pmatrix{1&0\cr 0&1\cr}$.
Show that $\lim_{n\to\infty} d_n=\infty$.

\problem B5.
For any real number $\alpha$,
define the function $f_{\alpha}$ by $f_{\alpha}(x)=\floor{\alpha x}$.
Let $n$ be a positive integer.
Show that there exists an $\alpha$ such that
for $1\le k\le n$,
$$f_{\alpha}^k(n^2)=n^2-k=f_{\alpha^k}(n^2).$$
($\floor{x}$ denotes the greatest integer $\le x$,
and $f_{\alpha}^k=f_{\alpha}\circ\cdots\circ f_{\alpha}$
is the $k$-fold composition of $f_{\alpha}$.)

\problem B6.
For any integer $a$, set $n_a=101a-100\cdot 2^a$.
Show that for $0\le a,b,c,d\le 99$,
$$n_a+n_b\equiv n_c+n_d\pmod{10100}
\qquad\hbox{implies}\qquad
\setof{a,b}=\setof{c,d}.
$$


\startsolns
% ^L

\solution A1.
If $\sum_{n\ge 1}a_n$ converges then
$$\sum_{n\ge 1}a_n
=a_1+\sum_{n\ge 1}(a_{2n}+a_{2n+1})
\ge a_1+\sum_{n\ge 1}a_n
> \sum_{n\ge 1}a_n,$$
which is absurd.

\solution A2.
Map the plane to itself by $f(x,y)=(3y,x/3)$.
This map takes the $y$-axis to the $x$-axis,
the ellipse ${1\over 9}x^2+y^2=1$ to itself,
and the line $y={1\over 2}x$ to the line $y={2\over 9}x$.
Hence it takes
the region bounded by
$y={1\over 2}x$, the $x$-axis, and the ellipse to
the region bounded by
$y={2\over 9}x$, the $y$-axis, and the ellipse.
Finally,
the Jacobian $Df$ equals $\pmatrix{0&3\cr 1/3&0\cr}$,
which has determinant $-1$,
so $f$ preserves areas.
Hence $m=2/9$.

\solution A3.
Put the triangle into the real plane with vertices
$A=(0,1),B=(1,0),C=(0,0)$.
Also write
$D,E,F,G$
for 
$$
(\sqrt2-1,2-\sqrt2),
(\sqrt2-1,0),
(0,\sqrt2-1),
(2-\sqrt2,\sqrt2-1)
$$
respectively.
Finally write $a,b,c,d,e,f,g$ for the colors of
$A,B,C,D,E,F,G$ respectively.

If $a=b$ then we are done:
the distance $|A-B|$ is more than $2-\sqrt2$.
So assume $a\ne b$.

The points $C,D,E,F,G$ are all at distance at least $2-\sqrt2$
from $A$ and from $B$.
Hence we are done if any of $c,d,e,f,g$ equals $a$ or $b$.
So assume that none of $c,d,e,f,g$ equals $a$ or $b$.

Now there are only two colors among $c,d,e,f,g$.
So three of $c,d,e,f,g$ are the same.
Hence $c=d$ or $d=e$ or $e=f$ or $f=g$ or $g=c$.
But the distances $|C-D|,|D-E|,|E-F|,|F-G|,|G-C|$
are all at least $2-\sqrt2$.
So we are done.

\solution A4.
If $XY=I$ with $X,Y$ integer matrices then
$\det X\det Y=1$ so $\det X=\pm 1$.
Hence $\det(A+kB)=\pm 1$ for $k=0,1,2,3,4$.
So $\det(A+kB)$ repeats one value at least three times.
But
$$\det(A+kB)=\det A+k\tr(A^{-1}B)\det A+k^2\det B.$$
This is a quadratic in $k$ which takes the same value three times,
so it is constant.
Hence $\det(A+kB)=\det A=\pm 1$ for every $k$.

\solution A5.
Write $R$ for the set $\setof{r_n}$.
Since $\lim_{n\to\infty} r_n=0$
there are, for any $h>0$,
only finitely many elements of $R$ which are bigger than $h$.

Write $R_k=\sum_{1\le i\le k} R$ for the set of
sums of $k$ elements, not necessarily distinct, of $R$.
Then $S\subseteq R_{1994}$.

We prove by induction on $k\ge 0$ that any nonempty interval
$(a,b)$ contains a nonempty subinterval $(c,d)$ which does not intersect $R_k$.

For $k=0$ we have $R_k=\setof{0}$, so we can take $(c,d)=(a,b)$
if $0\notin (a,b)$ and $(c,d)=(0,b)$ if $0\in (a,b)$.

Assuming that we have
a nonempty interval $(c,d)$ which does not intersect $R_k$,
we now construct
a nonempty subinterval $(c',d')$ which does not intersect $R_{k+1}$.

Put $c'=(c+d)/2$, so that $c<c'<d$.
Consider any $x\in R_{k+1}$ such that $c'<x<d$.
Write $x=s_0+s_1+s_2+\cdots+s_k$ with each $s_i\in R$.
For any $i$ we have $x-s_i\in R_k$, and $x-s_i<x<d$,
so by the assumption $x-s_i\le c$.
Hence $$s_i\ge x-c>c'-c.$$
There are only finitely many elements of $R$ bigger than $c'-c$.
So there are only finitely many choices of each $s_i$.
Hence there are only finitely many possibilities for $x$.
Let $d'$ be the minimum such $x$, or $d$ if no such $x$ exists.
Then, by construction,
$x\ge d'$ for any $x\in R_{k+1}$ with $c'<x$.
And that's what we wanted to prove.

\solution A6.
We prove the contrapositive.
Let $f_1,f_2,\ldots,f_{10}$ be bijections of the integers.
Let $A$ be a nonempty finite set of integers.
Let $G$ be the set of $(e_1,\ldots,e_{10})$
such that $f_1^{e_1}\circ\cdots\circ f_{10}^{e_{10}}$
maps $A$ to $A$.
Say $G$ has size at least $513$.

We show first that $f_1$ maps $A$ to $A$.
There are $512$ choices of $(e_2,e_3,\ldots,e_{10})$,
and $513$ elements of $G$,
so at least two elements of $G$ have the same $(e_2,e_3,\ldots,e_{10})$.
There are only two possibilities for $e_1$,
so both possibilities must appear.
In other words both
$$f_2^{e_2}\circ\cdots\circ f_{10}^{e_{10}}$$
and
$$f_1\circ f_2^{e_2}\circ\cdots\circ f_{10}^{e_{10}}$$
map $A$ to $A$.
Write $h=f_2^{e_2}\circ\cdots\circ f_{10}^{e_{10}}$.
Now $h(A)=A$, and $f_1(h(A))=A$, so $f_1(A)=A$ as desired.

By the same method we show for each $i$ in turn that $f_i$ maps $A$ to $A$.
There are $512$ choices of
$(e_1,\ldots,e_{i-1},e_{i+1},\ldots,e_{10})$,
so at least two elements of $G$ have the same 
$(e_1,\ldots,e_{i-1},e_{i+1},\ldots,e_{10})$.
There are only two possibilities for $e_i$,
so both possibilities must appear.
In other words both
$$f_1^{e_1}\circ\cdots\circ f_{i-1}^{e_{i-1}}
\circ f_{i+1}^{e_{i+1}}\circ\cdots\circ f_{10}^{e_{10}}$$
and
$$f_1^{e_1}\circ\cdots\circ f_{i-1}^{e_{i-1}} \circ f_i
\circ f_{i+1}^{e_{i+1}}\circ\cdots\circ f_{10}^{e_{10}}$$
map $A$ to $A$.
Write $g=f_1^{e_1}\circ\cdots\circ f_{i-1}^{e_{i-1}}$
and $h=f_{i+1}^{e_{i+1}}\circ\cdots\circ f_{10}^{e_{10}}$.
Then $g\circ h$ and $g\circ f_i\circ h$ both map $A$ to $A$.
By the inductive hypothesis, $g$ maps $A$ to $A$.
Thus $f_i$ maps $h(A)=g^{-1}(A)=A$ to $A$ as desired.

So every $f_i$ maps $A$ to $A$.
If $0\in A$, select $n\notin A$;
it is impossible for a composition of $f_i$'s to take $0$ to $n$.
If $0\notin A$, select $n\in A$;
it is again impossible for a composition of $f_i$'s to take $0$ to $n$.

\solution B1.
Let $S(n)$ be the set of perfect squares $s$ such that
$n$ is within $250$ of $s$.
For example 
$$S(1)=\setof{0,1,4,9,16,25,36,49,64,81,100,121,144,169,196,225}.$$
Let $f(n)$ be the size of $S(n)$.
For example $f(1)=16$.

The difference between $S(n-1)$ and $S(n)$ is that we
lose $n-251$ if $n-251$ is a square, i.e., at
$$n\in\setof{251,252,255,260,267,276,287,300,315,332,351,\ldots},$$
and we gain
$n+250$ if $n+250$ is a square., i.e., at
$$n\in\setof{6,39,74,111,150,191,234,279,326,375,\ldots}.$$
If neither $n-251$ nor $n+250$ is a square
then $S(n)=S(n-1)$ and $f(n)=f(n-1)$.

We thus calculate successively
$f(6)=17$,
$f(39)=18$,
$f(74)=19$,
$f(111)=20$,
$f(150)=21$,
$f(191)=22$,
$f(234)=23$,
$f(251)=22$,
$f(252)=21$,
$f(255)=20$,
$f(260)=19$,
$f(267)=18$,
$f(276)=17$,
$f(279)=18$,
$f(287)=17$,
$f(300)=16$,
$f(315)=15$,
$f(326)=16$,
$f(332)=15$,
and
$f(351)=14$.
Hence the integers from $315$ through $325$
and the integers from $332$ through $350$
are the only integers up through $351$ which
are within $250$ of exactly $15$ perfect squares.

There are no such integers past $350$.
Indeed,
if $n$ is within $250$ of
$m^2,(m+1)^2,\ldots,(m+14)^2$
then $(m+14)^2-m^2\le 500$ so
$28m+196\le 500$ so
$m\le304/28<11$
so $m\le 10$.
Hence $n\le m^2+250\le 100+250=350$.

\solution B2.
A straight line $ax+b$ intersects $x^4+9x^3+cx^2+9x+4$
in four distinct points if and only if
$x^4+9x^3+cx^2+(9-a)x+(4-b)$
has four distinct roots.
Write $g(x)=x^4+9x^3+cx^2+(9-a)x+(4-b)$.

If $g$ has four distinct roots then
$g'=4x^3+27x^2+2cx+(9-a)$ has three distinct roots so
$g''=12x^2+54x+2c$ has two distinct roots.
Hence the discriminant
$(54)^2-4\cdot 12\cdot 2c$
is positive.
In other words
$c<(54)^2/96=243/8$.

Conversely, if $c<243/8$ then $g''$ has two distinct roots,
so $g'$ has two distinct extreme points.
We can choose $a$ so that
$g'$ has a root between these two extreme points.
Then $g'$ has three distinct roots.
Similarly we can choose $b$ so that
$g$ has four distinct roots.

\solution B3.
For $k\ge 1$ the stated property does not hold.
Consider the function $f(x)=\exp(x-10+\tan^{-1}x)$,
where $\tan^{-1}$ means the angle between $-\pi/2$ and $\pi/2$.
The derivative of $f$ is
$$f'(x)=
\exp(x-10+\tan^{-1}(x))\left(1+{1\over 1+x^2}\right)
>\exp(x-10+\tan^{-1}(x))
=f(x).$$
But $f(x)<\exp(x-10+\pi/2)<e^x\le e^{kx}$.

For $k<1$ the stated property does hold.
Say $f'(x)>f(x)$.
Write $g(x)=f(x)e^{-x}$.
Then $g'(x)=-f(x)e^{-x}+f'(x)e^{-x}>0$.
So $g(x)>g(0)$ for $x>0$.
In other words $f(x)>f(0)e^x$ for $x>0$.
If also $x>-(\log f(0))/(1-k)$ then
$$f(x)>f(0)e^x=f(0)e^{kx}e^{(1-k)x}>f(0)e^{kx}e^{-\log f(0)}=e^{kx}.$$
So let $N$ be $0$ or $-(\log f(0))/(1-k)$,
whichever is larger.

\solution B4.
The following solution is stolen from Robin J. Chapman.

Observe that
matrices of the form $\pmatrix{a&b\cr 2b&a}$
are closed under multiplication by $\pmatrix{1&1\cr 2&1\cr}$.
In particular $\pmatrix{1&1\cr 2&1\cr}^n$
must be of the form $\pmatrix{a&b\cr 2b&a}$.
Its determinant is $(-1)^n$,
so $a^2-2b^2=(-1)^n$.
But $\pmatrix{3&2\cr 4&3}=\pmatrix{1&1\cr 2&1}^2$,
so
$$\pmatrix{3&2\cr 4&3}^n-\pmatrix{1&0\cr 0&1\cr}
=\pmatrix{a&b\cr 2b&a}^2-\pmatrix{1&0\cr 0&1\cr}
=\pmatrix{a^2+2b^2-1&2ab\cr 4ab&a^2+2b^2-1\cr}.$$
If $n$ is odd then $a^2-2b^2=-1$
so $a^2+2b^2-1=2a^2$
so all entries are divisible by $a$.
If $n$ is even then $a^2-2b^2=1$
so $a^2+2b^2-1=4b^2$
so all entries are divisible by $b$.
Both $a$ and $b$ increase as $n\to\infty$.

\solution B5.
We will show that $\alpha=1-1/n^2$ works.

Consider the function $g(z)=e^z(1-z)$ for $z\ge 0$.
We have $g(0)=1$ and $g'(z)=-ze^z\le 0$,
so $g(z)\le 1$.
Hence $1-z\le e^{-z}$.
In particular $1-1/n^2\le e^{-1/n^2}$.

Now consider the function $h(z)=e^{-z}(1+z)$ for $z\ge0$.
We have $h'(z)=-ze^{-z}<0$ for $z>0$ so $h(z)<h(0)=1$.
Hence $e^{-z}< 1/(1+z)$.
In particular
$e^{-1/n}<1/(1+1/n)=n/(n+1)=1-1/(n+1)$.
Hence
$$\left(1-{1\over n^2}\right)^n \le e^{-1/n}<1-{1\over n+1}.$$
So $\alpha^n(n^2-1)<n^2-n$.

Suppose that
$\alpha^k (n^2-1)\ge n^2-k$ for some $k\le n$.
Then $\alpha^{k+1} n^2\ge\alpha(n^2-k)\ge n^2-k-1$.
So, iterating, we find that
$\alpha^n(n^2-1)\ge n^2-n$;
contradiction.
Hence $\alpha^k (n^2-1)< n^2-k$ for each $k$.
In other words $\alpha^{k+1}(n^2)< n^2-k$.
Hence $f_{\alpha^{k+1}}(n^2)\le n^2-k-1$.

We now prove, by induction on $k$,
that $f_{\alpha}^k(n^2)=n^2-k=f_{\alpha^k}(n^2)$ for $0\le k\le n+1$.

For $k=0$ we have $f_{\alpha}^0(n^2)=n^2-0=f_{\alpha^0}(n^2)$.

Assume that $f_{\alpha}^k(n^2)=n^2-k=f_{\alpha^k}(n^2)$.
We will show that
$f_{\alpha}^{k+1}(n^2)=n^2-k-1=f_{\alpha^{k+1}}(n^2)$,
provided that $k\le n$.

First,
$\alpha=1-1/n^2\ge 1-1/(n^2-k)$,
so $\alpha(n^2-k)\ge n^2-k-1$,
so
$$f_{\alpha}^{k+1}(n^2)=f_{\alpha}(f_{\alpha}^k(n^2))
=f_{\alpha}(n^2-k)\ge n^2-k-1.$$
Second,
$f_{\alpha}^k(n^2)\le \alpha^kn^2$,
so
$\alpha f_{\alpha}^k(n^2)\le \alpha^{k+1}n^2$,
so
$$f_{\alpha}^{k+1}(n^2)\le f_{\alpha^{k+1}}(n^2).$$
Finally,
we proved before that
$$f_{{\alpha}^{k+1}}(n^2)\le n^2-k-1.$$
Hence both $f_{\alpha}^{k+1}(n^2)$ and $f_{{\alpha}^{k+1}}(n^2)$
are squeezed into $n^2-k-1$.

\solution B6.
Note that $101$ is prime.
We check that $2$ is a generator of the units modulo $101$.
We have $2^{10}=1024\equiv 14\pmod{101}$,
so $2^{20}\equiv 196\equiv -6$,
so $2^{40}\equiv 36$,
so $2^{50}\equiv 36\cdot 14=504\equiv -1$.
The order of $2$ is a divisor of $100$, but not a divisor of $20$ or 
$50$, so it must be $100$.

We have $n_a+n_b\equiv n_c+n_d\pmod{100}$
so $a+b\equiv c+d\pmod{100}$.
We also have $n_a+n_b\equiv n_c+n_d\pmod{101}$
so $2^a+2^b\equiv 2^c+2^d\pmod{101}$.
This is a quadratic equation in disguise.
Multiply by $2^a$ and substitute $2^{a+b}\equiv 2^{c+d}\pmod{101}$:
$$\eqalign{
2^{2a}+2^{c+d}-2^{a+c}-2^{a+d}& \equiv0\pmod{101} \cr
(2^a-2^c)(2^a-2^d) &\equiv0\pmod{101}. \cr
}$$
Hence $2^a\equiv 2^c$ or $2^a\equiv 2^d$.
If $2^a\equiv 2^c\pmod{101}$ then $a\equiv c\pmod{100}$,
since $2$ is a generator.
So $b\equiv d\pmod{100}$ and thus $a=c,b=d$.
Similarly if $2^a\equiv 2^d\pmod{101}$
then $a=d,b=c$.

\comments

This is a revision of my 3 December 1994 solution set.
The main improvement in this revision is
Robin J. Chapman's vastly simpler solution to B4.
I also fixed typos in A3, A4 (thanks to Par Kurlberg), and A5.

Note that there's quite a bit of slack in Problem B5.
Chapman observes that $k$ can be pushed up to $n\sqrt 2$.

In past years each Putnam question envelope contained
a summary sheet listing all the problems.
Contestants would take the morning sheet, and their notes, to lunch,
and discuss the morning questions.
This year (and, Gerald Edgar points out, last year),
the summary sheet was not handed out until the end of the exam.
Contestants were not allowed to take any written material
out of the exam room during lunch.
What is the point of this absurd restriction?

As usual, several exam questions were poorly worded.
The ``set of 1024 functions'' in A6 is a sequence, not a set.
The triangle in A3 has ``side length $1$'';
does this mean the (equal) legs, or does it mean the hypoteneuse?
``Side lengths $1,1,\sqrt2$''
would have resolved the ambiguity.
``At least a distance'' in A3 should have been
``a distance at least.''
Dave Savitt points out another question about A3:
Does ``triangle'' mean the boundary or the interior?

Other complaints:
In A6 ``for each integer $n$'' is missing a comma.
Similarly for ``if $A$ is any nonempty finite set of integers''
and, in B5, ``for $1\le k\le n$.''
These punctuation errors are distracting
and potentially confusing.
In B1 and B5 there are sentences starting with formulas.
This is unconventional and, again, potentially confusing.
Finally, in B5, how come the floor function ``denotes''
while the composition operator ``is''?
Should the reader's attention be focused
on the notation in one case
but the semantics in the other?
I don't think Putnam contestants need this sort of distraction.

A3 is just like a problem on the 19th Putnam,
and can be systematically solved in the same way.
A5 seems a bit too standard for a Putnam problem.
Overall, though, the exam wasn't too bad.
A2 is a wonderful example of a problem that's much more difficult
for people who know calculus than for people who don't.
Similar praise goes to B4.
(In my original solution set,
I smashed through B4
using recurrence identities which took two hours to derive.)
B6 is perhaps too easy, but beautiful nevertheless.

\bigskip
---Daniel J. Bernstein, {\tt djb@silverton.berkeley.edu}, 7 December 1994

\bye

