SIXTY-FOURTH ANNUAL WILLIAM LOWELL PUTNAM MATHEMATICAL COMPETITION

Saturday, December 6, 2003 Examination A

A1. Let n be a fixed positive integer. How many ways are there to write n as a sum of positive integers,

n = a_{1} + a_{2} + ⋯ a_{k},

with k an arbitrary positive integer and a_{1} ≤ a_{2} ≤ ⋯ ≤ a_{k} ≤ a_{1} + 1 ? For example, with n = 4, there are four ways: 4, 2 + 2, 1 + 1 + 2, 1 + 1 + 1 + 1.

A2. Let a_{1}, a_{2}, …, a_{n} and b_{1}, b_{2}, …, b_{n} be nonnegative real numbers. Show that

(a_{1}a_{2} ⋯ a_{n})^{1/n} + (b_{1}b_{2} ⋯ b_{n})^{1/n} ≤ ((a_{1} + b_{1})(a_{2} + b_{2}) ⋯ (a_{n} + b_{n}))^{1/n} .

A3. Find the minimum value of

| sin x + cos x + tan x + cot x + sec x + csc x|

for real numbers x.

A4. Suppose that a, b, c, A, B, C are real numbers, a ≠ 0 and A ≠ 0, such that

|ax^{2} + bx + c| ≤ |Ax^{2} + Bx + C|

for all real numbers x. Show that

|b^{2} − 4ac| ≤ |B^{2} − 4AC|.

A5. A Dyck n-path is a lattice path of n upsteps (1, 1) and n downsteps (1, −1) that starts at the origin O and never dips below the x-axis. A return is a maximal sequence of contiguous downsteps that terminates on the x-axis. For example, the Dyck 5-path (up, up, down, up, up, down, down, down, up, down) has two returns, of length 3 and 1 respectively. Show that there is a one-to-one correspondence between the Dyck n-paths with no return of even length and the Dyck (n − 1)-paths.

A6. For a set S of nonnegative integers, let r_{S}(n) denote the number of ordered pairs (s_{1}, s_{2}) such that s_{1} ∈ S, s_{2} ∈ S, s_{1} ≠ s_{2}, and s_{1} + s_{2} = n. Is it possible to partition the nonnegative integers into two sets A and B in such a way that r_{A}(n) = r_{B}(n) for all n?

SIXTY-FOURTH ANNUAL WILLIAM LOWELL PUTNAM MATHEMATICAL COMPETITION

Saturday, December 6, 2003 Examination B

B1. Do there exist polynomials a(x), b(x), c(y), d(y) such that

1 + xy + x^{2}y^{2} = a(x)c(y) + b(x)d(y)

holds identically?

B2. Let n be a positive integer. Starting with the sequence 1, \frac{1}{2}, \frac{1}{3}, …, \frac{1}{n}, form a new

sequence of n − 1 entries \frac{3}{4}, \frac{5}{12}, …, \frac{2n − 1}{2n(n − 1)}, by taking the averages of two consecutive

entries in the first sequence. Repeat the averaging of neighbors on the second sequence to obtain a third sequence of n − 2 entries and continue until the final sequence consists of a

single number x_{n}. Show that x_{n} < \frac{2}{n}.

B3. Show that for each positive integer n,

n! = ∏_{i=1}^{n} lcm {1, 2, …, ⌊n/i⌋} .

(Here lcm denotes the least common multiple, and ⌊x⌋ denotes the greatest integer ≤ x.)

B4. Let f(z) = az^{4} + bz^{3} + cz^{2} + dz + e = a(z − r_{1})(z − r_{2})(z − r_{3})(z − r_{4}) where a, b, c, d, e are integers, a ≠ 0. Show that if r_{1} + r_{2} is a rational number, and if r_{1} + r_{2} ≠ r_{3} + r_{4}, then r_{1}r_{2} is a rational number.

B5. Let A, B and C be equidistant points on the circumference of a circle of unit radius centered at O, and let P be any point in the circle’s interior. Let a, b, c be the distances from P to A, B, C respectively. Show that there is a triangle with side lengths a, b, c, and that the area of this triangle depends only on the distance from P to O.

B6. Let f(x) be a continuous real-valued function defined on the interval [0, 1]. Show that

∫_{0}^{1} ∫_{0}^{1} |f(x) + f(y)| dx dy ≥ ∫_{0}^{1} |f(x)| dx.