# 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

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 B-4, 1980

Let A_{1}, A_{2}, ... , A_{1066} be subsets of a

finite set X such that |A_{1}| > 1/2|X| 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/2|X|·

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 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 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(n-1)

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 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 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 |