FIFTY-FIRST ANNUAL WILLIAM LOWELL PUTNAM MATHEMATICAL COMPETITION

Saturday, December 1, 1990 Examination A

A-1. Let

T_{0} = 2, T_{1} = 3, T_{2} = 6,

and for n ≥ 3,

T_{n} = (n + 4)T_{n−1} − 4nT_{n−2} + (4n − 8)T_{n−3}.

The first few terms are

2, 3, 6, 14, 40, 152, 784, 5168, 40576.

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.

A-2. Is \sqrt{2} the limit of a sequence of numbers of the form ^{3} \sqrt{n} − ^{3} \sqrt{m} (n, m = 0, 1, 2, …)?

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

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?

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

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 ∈ S, and t > |S| for each t ∈ T. How many admissible ordered pairs of subsets of {1, 2, …, 10} are there? Prove your answer.

FIFTY-FIRST ANNUAL WILLIAM LOWELL PUTNAM MATHEMATICAL COMPETITION

Saturday, December 1, 1990 Examination B

B-1. Find all real-valued continuously differentiable functions f on the real line such that for all x,

(f(x))^{2} = ∫_{0}^{x}[(f(t))^{2} + (f′(t))^{2}] dt + 1990.

B-2. Prove that for |x| < 1, |z| > 1,

1 + ∑_{j=1}^{∞}(1 + x^{j})\frac{(1 − z)(1 − zx)(1 − zx^{2}) ⋯ (1 − zx^{j−1})}{(z − x)(z − x^{2})(z − x^{3}) ⋯ (z − x^{j})} = 0.

B-3. Let S be a set of 2×2 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.

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}.)

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_{1}x + a_{2}x^{2} + ⋯ + a_{n}x^{n}

has exactly n distinct real roots?

B-6. Let S be a nonempty 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_{1}, and let \overline{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 \overline{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 ∩ ⋂_{K} B_{S}(K, t) ≠ ∅

for all S? (K runs over all lines in the plane.)