FORTY-SIXTH ANNUAL WILLIAM LOWELL PUTNAM MATHEMATICAL COMPETITION

Saturday, December 7, 1985 Examination A

A-1. Determine, with proof, the number of ordered triples (A_{1}, A_{2}, A_{3}) of sets which have the property that

(i) A_{1} ∪ A_{2} ∪ A_{3} = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.

and

(ii) A_{1} ∩ A_{2} ∩ A_{3} = ∅,

where ∅ denotes the empty set. Express the answer in the form 2^{a}3^{b}5^{c}7^{d}, where a, b, c and d are nonnegative integers.

A-2. Let T be an acute triangle. Inscribe a pair R, S of rectangles in T as shown:

S R

Let A(X) denote the area of polygon X. Find the maximum value, or show that no maximum

exists, of \frac{A(R) + A(S)}{A(T)}, where T ranges over all triangles and R, S over all rectangles as above.

A-3. Let d be a real number. For each integer m ≥ 0, define a sequence {a_{m}(j)}, j = 0, 1, 2, … by the condition

a_{m}(0) = d/2^{m}, and a_{m}(j + 1) = (a_{m}(j))^{2} + 2a_{m}(j), j ≥ 0.

Evaluate lim_{n→∞} a_{n}(n).

A-4. Define a sequence {a_{i}} by a_{1} = 3 and a_{i+1} = 3^{a_{i}} for i ≥ 1. Which integers between 00 and 99 inclusive occur as the last two digits in the decimal expansion of infinitely many a_{i}?

A-5. Let I_{m} = ∫_{0}^{2π} cos(x) cos(2x) ⋯ cos(mx) dx. For which integers m, 1 ≤ m ≤ 10, is I_{m} ≠ 0?

A-6. If p(x) = a_{0} + a_{1}x + ⋯ + a_{m}x^{m} is a polynomial with real coefficients a_{i}, then set

Γ(p(x)) = a_{0}^{2} + a_{1}^{2} + ⋯ + a_{m}^{2}.

Let f(x) = 3x^{2} + 7x + 2. Find, with proof, a polynomial g(x) with real coefficients such that

(i) g(0) = 1,

and

(ii) Γ(f(x)^{n}) = Γ(g(x)^{n}),

for every integer n ≥ 1.

FORTY-SIXTH ANNUAL WILLIAM LOWELL PUTNAM MATHEMATICAL COMPETITION

Saturday, December 7, 1985 Examination B

B-1. Let k be the smallest positive integer with the following property:

There are distinct integers m_{1}, m_{2}, m_{3}, m_{4}, m_{5} such that the polynomial

p(x) = (x − m_{1})(x − m_{2})(x − m_{3})(x − m_{4})(x − m_{5})

has exactly k nonzero coefficients.

Find, with proof, a set of integers m_{1}, m_{2}, m_{3}, m_{4}, m_{5} for which this minimum k is achieved.

B-2. Define polynomials f_{n}(x) for n ≥ 0 by f_{0}(x) = 1, f_{n}(0) = 0 for n ≥ 1, and

\frac{d}{dx}(f_{n+1}(x)) = (n + 1)f_{n}(x + 1)

for n ≥ 0. Find, with proof, the explicit factorization of f_{100}(1) into powers of distinct primes.

B-3. Let

\begin{matrix}a_{1,1} & a_{1,2} & a_{1,3} & ⋯ \\ a_{2,1} & a_{2,2} & a_{2,3} & ⋯ \\ a_{3,1} & a_{3,2} & a_{3,3} & ⋯ \\ ⋮ & ⋮ & ⋮ & ... \end{matrix}

be a doubly infinite array of positive integers, and suppose each positive integer appears exactly eight times in the array. Prove that a_{m,n} > mn for some pair of positive integers (m, n).

B-4. Let C be the unit circle x^{2} + y^{2} = 1. A point p chosen randomly on the circumference C and another point q chosen randomly from the interior of C (these points are chosen independently and uniformly over their domains). Let R be the rectangle with sides parallel to the x- and y-axes with diagonal pq. What is the probability that no point of R lies outside of C?

B-5. Evaluate ∫_{0}^{∞} t^{−1/2}e^{−1985(t+t^{−1})} dt. You may assume that ∫_{−∞}^{∞} e^{−x^{2}} dx = \sqrt{π}.

B-6. Let G be a finite set of real n × n matrices {M_{i}}, 1 ≤ i ≤ r, which form a group under matrix multiplication. Suppose that ∑_{i=1}^{r} tr(M_{i}) = 0, where tr(A) denotes the trace of the matrix A. Prove that ∑_{i=1}^{r} M_{i} is the n × n zero matrix.