From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: sci.math
Subject: 1990 Putnam problems, with some unofficial solutions
Message-ID: <5246:Dec201:45:4390@kramden.acf.nyu.edu>
Date: 2 Dec 90 01:45:43 GMT
Sender: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Organization: IR
Lines: 269
Posted: Sun Dec  2 02:45:43 1990


Problem A-1
Let T_0 = 2, T_1 = 3, T_2 = 6, and for n >= 3,
T_n = (n + 4)T_{n-1} - 4n T_{n-2} + (4n - 8)T_{n-3}.
The first few terms are 2, 3, 6, 14, 40, 152, 784, 5168, 40576, 363392.
Find, with proof, a formula for T_n of the form T_n = A_n + B_n, where
(A_n) and (B_n) are well-known sequences.

Problem A-2
Is \sqrt{2} the limit of a sequence of numbers of the form
\root3{n} - \root3{m}, (n, m = 0, 1, 2, ...) ? Justify your answer.

Problem A-3
Prove that any convex pentagon whose vertices (no three of which are
collinear) have integer coordinates must have area >= 5/2.

Problem A-4
Consider a paper punch that can be centered at any point of the plane
and that, when operated, removes from the plane precisely those points
whose distance from the center is irrational. How many punches are
needed to remove every point?

Problem A-5
If A and B are square matrices of the same size such that ABAB = 0, does
it follow that BABA = 0?

Problem A-6
If X is a finite set, let |X| denote the number of elements in X. Call
an ordered pair (S,T) of subsets of {1,2,...,n} admissible if s > |T|
for each s \in S, and t > |S| for each t \in T. How many admissible
ordered pairs of subsets of {1,2,...,10} are there? Prove your answer.

Problem B-1
Find all real-valued continuously differentiable functions f on the real
line such that for all x
(f(x))^2 = \int_0^x ((f(t))^2 + (f'(t))^2) dt + 1990.

Problem B-2
Prove that for |x| < 1, |z| > 1, 1 + \sum_{j = 1}^\infty
(1 + x^j) { (1 - z)(1 - zx)(1 - zx^2)...(1 - zx^{j-1})
\over (z - x)(z - x^2)(z - x^3)...(z - x^j) } = 0.

Problem B-3
Let S be a set of 2x2 integer matrices whose entries a_{ij} (1) are all
squares of integers, and, (2) satisfy a_{ij} <= 200. Show that if S has
more than 50387 (= 15^4 - 15^2 - 15 + 2) elements, then it has two
elements that commute.

Problem B-4
Let G be a finite group of order n generated by a and b. Prove or
disprove: there is a sequence g_1, g_2, g_3, ..., g_{2n} such that
(1) every element of G occurs exactly twice, and
(2) g_{i+1} equals g_i a or g_i b, for i = 1, 2, ..., 2n. (Interpret
g_{2n+1} as g_1.)

Problem B-5
Is there an infinite sequence a_0, a_1, a_2, ... of nonzero real numbers
such that for n = 1, 2, 3, ... the polynomial
p_n(x) = a_0 + a_1x + a_2x^2 + ... + a_nx^n has exactly n distinct real
roots?

Problem B-6
Let S be a closed bounded convex set in the plane. Let K be a line and t
a positive number. Let L_1 and L_2 be support lines for S parallel to K,
and let \overbar{L} be the line parallel to K and midway between L_1 and
L_2. Let B_S(K,t) be the band of points whose distance from \overbar{L}
is at most (t/2)w, where w is the distance between L_1 and L_2. What is
the smallest t such that S \cap \bigcap_K B_S(K,t) \ne 0 for all S?
(K runs over all lines in the plane.) [ picture deleted ]


What follow may or may not be outlines of solutions to these problems.
I'm mainly writing this off the top of my head, so don't expect
perfection. Others will compile more official solutions later.


Problem A-1
Let T_0 = 2, T_1 = 3, T_2 = 6, and for n >= 3,
T_n = (n + 4)T_{n-1} - 4n T_{n-2} + (4n - 8)T_{n-3}.
The first few terms are 2, 3, 6, 14, 40, 152, 784, 5168, 40576, 363392.
Find, with proof, a formula for T_n of the form T_n = A_n + B_n, where
(A_n) and (B_n) are well-known sequences.

Solution:
T_n = n! + 2^n. This is trivial to check. (The sledgehammer for this
problem is to set U_n = T_n - (an + b)T_{n-1} and find for which a and b
you get a nice U_n recurrence.)

Problem A-2
Is \sqrt{2} the limit of a sequence of numbers of the form
\root3{n} - \root3{m}, (n, m = 0, 1, 2, ...) ? Justify your answer.

Solution:
It's intuitively obvious that any positive r, not just the square root
of 2, can be found as differences of values at integers of functions
increasing but concave down. An elementary proof for this case starts
with the fact that b/7x^2 <= \root3{x^3 + b} - x <= 3b/7x^2, where x is
at least 1 and b is between 0 and 7x^2; put \alpha = b/7x^2 and expand
(x + \alpha)^3 and (x + 3\alpha)^3. Then, for a given m, set n to an
integer between (say) (\root3{m} + r)^3 and (\root3{m} + r)^3 + 3, and
set b to n - (\root3{m} + r)^3. b is between 0 and 3, so the previous
inequality gives a sufficiently tight bound on \root3{n}-\root3{m} - r. 

Problem A-3
Prove that any convex pentagon whose vertices (no three of which are
collinear) have integer coordinates must have area >= 5/2.

Solution (thanks to Melvin Hausner):
The five vertices can have only four different pairs of coordinates
mod 2; hence two must have the same parity. Their midpoint is a lattice
point and is inside the pentagon. (If it is on the boundary, replace one
of the initial vertices with it, and apply the theorem to the reduced
figure. This preserves non-collinearity.) Then the triangle between that
interior point and two successive vertices is of area at least 1/2.
There are five such triangles.

Problem A-4
Consider a paper punch that can be centered at any point of the plane
and that, when operated, removes from the plane precisely those points
whose distance from the center is irrational. How many punches are
needed to remove every point?

Solution:
Once again the Putnam features an old problem. Anyone keeping track of
how many times in the last few years this exam has repeated problems
brought up in lectures by Halmos, or presented in MAA journals?

In any case, 4 punches suffice, namely at 0, 1, e, and e + 1 (where e
can be replaced by any irrational number---I remember that it was \pi
the first time I saw this problem in print). f + gi can only pass
through those 4 punches if (f-x)^2 + g^2 is the square of a rational for
x = 0, 1, e, e + 1. Subtract the 0 case from the others to see that
-2fx + x^2 is rational for x = 1, e, e + 1. But 2f - 1, e^2 - 2ef, and
e^2 + 2e + 1 - 2ef - 2f add up to 2e, which is irrational.

It's trivial to see that 3 punches are necessary. If they are at 0,
positive real x, and complex z = a + bi, then f + gi can only pass
through if f^2 + g^2, (f - a)^2 + (g - b)^2, and (f - x)^2 + g^2 are
simultaneously squares of rational numbers. One way to work with this is
to take f = r_1 cos t_1, g = r_1 sin t_1, f - a = r_2 cos t_2, g - b =
r_2 sin t_2, f - x = r_3 cos t_3, and g = r_3 sin t_3. The conditions
reduce to a = r_1 cos t_1 - r_2 cos t_2, b = r_2 sin t_2,
x = r_1 cos t_1 - r_3 cos t_3; if these can be solved for rational r_i,
then r_1 e^{i t_1} makes it through the sieve. Three equations in six
variables can generally be solved for rational values of three of the
variables; here r_2 should be chosen rational larger than |b|, then r_1
chosen rational larger than |a + r_2 cos t_2|, then r_3 chosen rational
and large enough, with the t's falling into place. Something like that,
anyway. So 4 punches are necessary and sufficient.

Problem A-5
If A and B are square matrices of the same size such that ABAB = 0, does
it follow that BABA = 0?

Solution:
Why should it? Take, for instance, A = (0 0 0   1 0 2   6 4 0), and
B = (0 -4 -2   0 5 3   0 2 1). Then AB is zero on and above the diagonal
and hence has square 0. But BA is (-16 -8 -8   23 12 10   8 4 4), whose
square is not 0.

Problem A-6
If X is a finite set, let |X| denote the number of elements in X. Call
an ordered pair (S,T) of subsets of {1,2,...,n} admissible if s > |T|
for each s \in S, and t > |S| for each t \in T. How many admissible
ordered pairs of subsets of {1,2,...,10} are there? Prove your answer.

Solution:
For a given |S| = f and |T| = g, clearly there are {10 - f\binom g}
times {10 - g\binom f} ways to choose the elements of S and T. Hence the
answer is the sum of that product over all f and g between 0 and 10. (Of
course, the term drops out whenever f + g exceeds 10.)

Presumably some transformation described in Knuth suffices to find a
closed-form answer for all n.

Problem B-1
Find all real-valued continuously differentiable functions f on the real
line such that for all x
(f(x))^2 = \int_0^x ((f(t))^2 + (f'(t))^2) dt + 1990.

Solution:
Differentiate and solve the equation to see that f(x) is e^x times
either square root of 1990.

Problem B-2
Prove that for |x| < 1, |z| > 1, 1 + \sum_{j = 1}^\infty
(1 + x^j) { (1 - z)(1 - zx)(1 - zx^2)...(1 - zx^{j-1})
\over (z - x)(z - x^2)(z - x^3)...(z - x^j) } = 0.

Solution:
Sum from j = 0 to n by induction; the denominator of the nth term
clearly suffices for the previous terms, and everything collapses.
Then x^j goes to 0, the numerator is as 1, and the denominator is
as z^j.

Problem B-3
Let S be a set of 2x2 integer matrices whose entries a_{ij} (1) are all
squares of integers, and, (2) satisfy a_{ij} <= 200. Show that if S has
more than 50387 (= 15^4 - 15^2 - 15 + 2) elements, then it has two
elements that commute.

Solution:
The entries are chosen from 0^2, 1^2, 2^2, and so on up to 14^2.

There are 15^2 diagonal matrices. 15 of them are multiples of the
identity and commute with everything. The other 15^2 - 15 commute with
each other. Hence if S has no elements that commute, it has at most 1
element in these 15^2, and the other 15^4 - 15^2 - 15 + 1 in the
15^4 - 15^2 nondiagonal matrices.

There are 15^3 - 15^2 nondiagonal matrices with bottom left corner 0.
Two of these commute with each other if they have the same top right
corner and same difference along the diagonal. For a given nonzero top
right corner, there are 15^2 nondiagonal matrices with bottom left
corner 0; of these, 15 have a constant diagonal, and there are 15^2 - 15
others.

There are 15^4 - 15^3 matrices with bottom left corner nonzero; S has at
most 15^4 - 15^3 in this set, so it has at least 15^3 - 15^2 - 15 + 1 in
the nondiagonal-but-bottom-left-corner-0 set. One of the 14 top right
corners must get at least 1/14 of this amount, i.e., 15^2 - 1. Then at
most 15^2 - 15 have non-constant diagonals. The other 14 have constant
diagonals, and hence commute with each other.

(I may have messed up the arithmetic here, as most Putnam bounds are at
least meant to be exact. Then again, one problem last year had a linear
bound where a more obvious analysis gave a [better] quadratic bound.)

Problem B-4
Let G be a finite group of order n generated by a and b. Prove or
disprove: there is a sequence g_1, g_2, g_3, ..., g_{2n} such that
(1) every element of G occurs exactly twice, and
(2) g_{i+1} equals g_i a or g_i b, for i = 1, 2, ..., 2n. (Interpret
g_{2n+1} as g_1.)

Solution:
I don't know. Any takers?

Problem B-5
Is there an infinite sequence a_0, a_1, a_2, ... of nonzero real numbers
such that for n = 1, 2, 3, ... the polynomial
p_n(x) = a_0 + a_1x + a_2x^2 + ... + a_nx^n has exactly n distinct real
roots?

Solution:
It's reasonably obvious that the truncated exp series does this; examine
the Sturm sequence. I seem to remember seeing this problem before too,
though I'm not sure.

Problem B-6
Let S be a closed bounded convex set in the plane. Let K be a line and t
a positive number. Let L_1 and L_2 be support lines for S parallel to K,
and let \overbar{L} be the line parallel to K and midway between L_1 and
L_2. Let B_S(K,t) be the band of points whose distance from \overbar{L}
is at most (t/2)w, where w is the distance between L_1 and L_2. What is
the smallest t such that S \cap \bigcap_K B_S(K,t) \ne 0 for all S?
(K runs over all lines in the plane.) [ picture deleted ]

Solution:
The stated intersection decreases with t. Choose a point inside all the
nonempty intersections. Parametrize S as c(x) e^{ix}. Now if K has angle
x + \pi/2, the support lines L_1 and L_2 touch S at c(x) e^{ix} and
-c(-x) e^{ix}. 0 must be inside the stated band, i.e., c(x) - c(-x)
plus q times c(x) + c(-x) must equal 0, for some q between -t and t.
This is equivalent to (c(x) - c(-x))/(c(x) + c(-x)) being between -t and
t. Now convexity implies more about c(x) than the fact that it exists;
this should translate into a statement about t, though I'm getting
bogged down in the manipulations.

---Dan