Try our Free Online Math Solver!

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 B3, 1980
For which real numbers a does the
sequence defined by the initial condition
u_{0} = a and the recursion u_{n+1} = 2u_{n}
 n^{2} have u_{n} > 0 for all n ≥ 0?
Express the answer in the simplest
form.)
You can make the recursion easier by
defining v_{n}'s by
U_{n} will be positive whenever v_{n} is positive.
Then
, and v_{0} = u_{0} = a.
The formula
u _{n+1} = 2u_{n}
 n^{2}
becomes
or
This gives
v_{n} will be positive for all n if
Now, if x = 1/2 this is
x^{2} + 2^{2}x^{3} + 3^{2}x^{4} + . . .
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 B4, 1980
Let A_{1}, A_{2}, ... , A_{1066} be subsets of a
finite set X such that A_{1} > 1/2X for 1 ≤ i
≤1066. Prove there exist ten elements x_{1} ,
. . . , x_{10} of X such that every A_{i} contains
at least one of x _{1}, . . . , x_{10}.
(Here S means the number of elements
in the set S.)
We can find an element x_{1} that is contained
in more than half the sets A_{i}. If
there were no such x_{1}, then A_{1} + A_{2} +
... + A_{1066} would be less than or equal
to
because each x is in at
most half the A_{i}'s. But for each A_{i}, A_{i} >
1/2Xยท
Consider only the sets A_{i} with x_{1} not
contained in A_{i}. 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 x_{2} contained
in more than half of these 532
remaining sets, leaving at most 265 sets
without x_{1} or x_{2}. Repeating this ten times,
you get x_{1}, x_{2}, ... , x_{10}, with each A_{i}
containing one of them.
Problem A6, 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 P_{i}. Define e_{i} as the number
of points p on the circle around P_{i}.
is the number of pairs of points
at distance j, since each pair gives two
points on the circles. We can assume e_{i} ≥ 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(n1)
intersections. The point P_{i} occurs as an
intersection
times, so we have
By the Cauchy Schwarz inequality ,
So, combining the above equations ,
And finally, there's Problem A4 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 10^{7}, so if the product of the
conjugates is not 0, then we have a +
times three factors that
are less than 10^{7} 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 