Putnam Problem Solutions

A story in the June issue of E&S about
the Putnam Mathematical Competition
and Caltech's star competitor Peter Shor
(BS '81) left some problems for readers to
tackle. Here are Shor's answers.

Problem B-3, 1980
For which real numbers a does the
sequence defined by the initial condition
u0 = a and the recursion un+1 = 2un
- n2  have un > 0 for all n ≥ 0?

Express the answer in the simplest
form.)

You can make the recursion easier by
defining vn's by

Un will be positive whenever vn is positive.

Then , and v0 = u0 = a.
The formula u n+1 = 2un - n2
becomes
or
This gives

vn will be positive for all n if

Now, if x = 1/2 this is
x2 + 22x3 + 32x4 + . . .

To sum this series , consider

and this series is what we want with x = 1/2.
So, the series converges to 3, and the
answer is a ≥ 3.

Problem B-4, 1980
Let A1, A2, ... , A1066 be subsets of a
finite set X such that |A1| > 1/2|X| for 1 ≤ i
≤1066. Prove there exist ten elements x1 ,
. . . , x10 of X such that every Ai contains
at least one of x 1, . . . , x10.

(Here |S| means the number of elements
in the set S.)

We can find an element x1 that is contained
in more than half the sets Ai. If
there were no such x1, then |A1| + |A2| +
... + |A1066| would be less than or equal
to because each x is in at
most half the Ai's. But for each Ai, |Ai| >
1/2|X|·

Consider only the sets Ai with x1 not
contained in Ai. There are at most 532 of
these, and each of them contains more
than half of the elements of X. Repeating
the argument above, there is an x2 contained
in more than half of these 532
remaining sets, leaving at most 265 sets
without x1 or x2. Repeating this ten times,
you get x1, x2, ... , x10, with each Ai
containing one of them.

Problem A-6, 1978
Let n distinct points in the plane be
given. Prove that fewer than pairs of
them are unit distance apart.

Draw a circle of radius 1 around each
of the points Pi. Define ei as the number
of points p on the circle around Pi.
is the number of pairs of points
at distance j, since each pair gives two
points on the circles. We can assume ei ≥ 1
for all i, since otherwise we have a point
unit distance from no points.

Each pair of circles has at most two
intersections, so there are at most n(n-1)
intersections. The point Pi occurs as an
intersection times, so we have

By the Cauchy-Schwarz inequality,

So, combining the above equations ,

And finally, there's Problem A-4 from
1980, the first part of which was solved in
the June
issue, leaving (b), the harder
part, for readers.

(a) Prove that there exist integers a, b, c,
not all zero and each of absolute value
less than one million, such that

(b) Let a, b, c be integers, not all zero and
each of absolute value less than one million.
Prove that

In (b) you can multiply by conjugates to
get rid of the square roots :

If a, b, and care all integers, then this
will be an integer, and if it's not equal to
0, it has to be of magnitude at least 1.

In the first part of the problem we
showed that a number of this form had to
be less than 107, so if the product of the
conjugates is not 0, then we have a +
times three factors that
are less than 107 yielding something bigger
than or equal to 1, and therefore

and we're done.

Now all we have to do is show that the
product of the conjugates cannot be equal
to 0, and we can do this by proving that
it's impossible for any of the four conjugate
factors to be 0. If
, say,

then

Now, squaring both sides, we get

If a and b are not 0, then this last equation
could be used to express as a quotient
of integers, which is impossible since
isn't a rational number . So it only remains
to consider the possibility that a = 0 or b
= 0. If b = 0, then

which would make   a ratIonal number
unless c = 0. But if c is 0, then obviously
a is 0, so a, b, and c are all 0, contrary to
assumption. So the only remaining possibilities
are in the case a = 0, b ≠ 0.
In this case

so we get

which is impossible because is not
rational, and this completes the argument.
39

Prev Next