SEVENTIETH ANNUAL WILLIAM LOWELL PUTNAM MATHEMATICAL COMPETITION

Saturday, December 5, 2009 Examination A

A1. Let f be a real-valued function on the plane such that for every square ABCD in the plane, f(A) + f(B) + f(C) + f(D) = 0. Does it follow that f(P) = 0 for all points P in the plane?

A2. Functions f, g, h are differentiable on some open interval around 0 and satisfy the equations and initial conditions

\begin{aligned}f′ & = 2f^{2}gh + \frac{1}{gh}, f(0) = 1, \\ g′ & = fg^{2}h + \frac{4}{fh}, g(0) = 1, \\ h′ & = 3fgh^{2} + \frac{1}{fg} , h(0) = 1. \end{aligned}

Find an explicit formula for f(x), valid in some open interval around 0.

A3. Let d_{n} be the determinant of the n × n matrix whose entries, from left to right and then from top to bottom, are cos 1, cos 2, …, cos n^{2}. (For example,

d_{3} = | \begin{matrix}cos 1 & cos 2 & cos 3 \\ cos 4 & cos 5 & cos 6 \\ cos 7 & cos 8 & cos 9 \end{matrix} | .

The argument of cos is always in radians, not degrees.) Evaluate lim_{n→∞} d_{n}.

A4. Let S be a set of rational numbers such that (a) 0 ∈ S;

(b) If x ∈ S then x + 1 ∈ S and x − 1 ∈ S; and

(c) If x ∈ S and x ∉ {0, 1}, then 1/(x(x − 1)) ∈ S. Must S contain all rational numbers?

A5. Is there a finite abelian group G such that the product of the orders of all its elements is 2^{2009}?

A6. Let f : [0, 1]^{2} → R be a continuous function on the closed unit square such that \frac{∂f}{∂x} and \frac{∂f}{∂y} exist and are continuous on the interior (0, 1)^{2}. Let a = ∫_{0}^{1} f(0, y) dy, b = ∫_{0}^{1} f(1, y) dy, c = ∫_{0}^{1} f(x, 0) dx, d = ∫_{0}^{1} f(x, 1) dx. Prove or disprove: There must be a point (x_{0}, y_{0}) in (0, 1)^{2} such that

\frac{∂f}{∂x} (x_{0}, y_{0}) = b − a and \frac{∂f}{∂y} (x_{0}, y_{0}) = d − c.

SEVENTIETH ANNUAL WILLIAM LOWELL PUTNAM MATHEMATICAL COMPETITION

Saturday, December 5, 2009 Examination B

B1. Show that every positive rational number can be written as a quotient of products of factorials of (not necessarily distinct) primes. For example,

\frac{10}{9} = \frac{2! · 5!}{3! · 3! · 3!}.

B2. A game involves jumping to the right on the real number line. If a and b are real numbers and b > a, the cost of jumping from a to b is b^{3} − ab^{2}. For what real numbers c can one travel from 0 to 1 in a finite number of jumps with total cost exactly c?

B3. Call a subset S of {1, 2, …, n} mediocre if it has the following property: Whenever a and b are elements of S whose average is an integer, that average is also an element of S. Let A(n) be the number of mediocre subests of {1, 2, …, n}. [For instance, every subset of {1, 2, 3} except {1, 3} is mediocre, so A(3) = 7.] Find all positive integers n such that A(n + 2) − 2A(n + 1) + A(n) = 1.

B4. Say that a polynomial with real coefficients in two variables, x, y, is balanced if the average value of the polynomial on each circle centered at the origin is 0. The balanced polynomials of degree at most 2009 form a vector space V over R. Find the dimension of V.

B5. Let f : (1, ∞) → R be a differentiable function such that

f′(x) = \frac{x^{2} − (f(x))^{2}}{x^{2}((f(x))^{2} + 1)} for all x > 1.

Prove that lim_{x→∞} f(x) = ∞.

B6. Prove that for every positive integer n, there is a sequence of integers a_{0}, a_{1}, …, a_{2009} with a_{0} = 0 and a_{2009} = n such that each term after a_{0} is either an earlier term plus 2^{k} for some nonnegative integer k, or of the form bmodc for some earlier positive terms b and c. [Here bmodc denotes the remainder when b is divided by c, so 0 ≤ (bmodc) < c.]