SIXTY-FIFTH ANNUAL WILLIAM LOWELL PUTNAM MATHEMATICAL COMPETITION

Saturday, December 4, 2004 Examination A

A1. Basketball star Shanille O’Keal’s team statistician keeps track of the number, S(N), of successful free throws she has made in her first N attempts of the season. Early in the season, S(N) was less than 80% of N, but by the end of the season, S(N) was more than 80% of N. Was there necessarily a moment in between when S(N) was exactly 80% of N?

A2. For i = 1, 2, let T_{i} be a triangle with side lengths a_{i}, b_{i}, c_{i}, and area A_{i}. Suppose that a_{1} ≤ a_{2}, b_{1} ≤ b_{2}, c_{1} ≤ c_{2}, and that T_{2} is an acute triangle. Does it follow that A_{1} ≤ A_{2}?

A3. Define a sequence {u_{n}}_{n=0}^{∞} by u_{0} = u_{1} = u_{2} = 1, and thereafter by the condition that

det [ \begin{matrix}u_{n} & u_{n+1} \\ u_{n+2} & u_{n+3} \end{matrix} ] = n!

for all n ≥ 0. Show that u_{n} is an integer for all n. (By convention, 0! = 1.)

A4. Show that for any positive integer n there is an integer N such that the product x_{1}x_{2} ⋯ x_{n} can be expressed identically in the form

x_{1}x_{2} ⋯ x_{n} = ∑_{i=1}^{N} c_{i}(a_{i1}x_{1} + a_{i2}x_{2} + ⋯ a_{in}x_{n})^{n}

where the c_{i} are rational numbers and each a_{ij} is one of the numbers, −1, 0, 1.

A5. An m × n checkerboard is colored randomly: each square is independently assigned red or black with probability 1/2. We say that two squares, p and q, are in the same connected monochromatic region if there is a sequence of squares, all of the same color, starting at p and ending at q, in which successive squares in the sequence share a common side. Show that the expected number of connected monochromatic regions is greater that mn/8.

A6. Suppose that f(x, y) is a continuous real-valued function on the unit square 0 ≤ x ≤ 1, 0 ≤ y ≤ 1. Show that

\begin{aligned}∫_{0}^{1} (∫_{0}^{1} f(x, y) dx)^{2} & dy + ∫_{0}^{1} (∫_{0}^{1} f(x, y) dy)^{2} dx \\ & ≤ (∫_{0}^{1} ∫_{0}^{1} f(x, y) dx dy)^{2} + ∫_{0}^{1} ∫_{0}^{1} [f(x, y)]^{2} dx dy. \end{aligned}

SIXTY-FIFTH ANNUAL WILLIAM LOWELL PUTNAM MATHEMATICAL COMPETITION

Saturday, December 4, 2004 Examination B

B1. Let P (x) = c_{n}x^{n} + c_{n−1}x^{n−1} + ⋯ + c_{0} be a polynomial with integer coefficients. Suppose that r is a rational number such that P (r) = 0. Show that the n numbers

c_{n}r, c_{n}r^{2} + c_{n−1}r, c_{n}r^{3} + c_{n−1}r^{2} + c_{n−2}r, …, c_{n}r^{n} + c_{n−1}r^{n−1} + ⋯ + c_{1}r

are integers.

B2. Let m and n be positive integers. Show that

\frac{(m + n)!}{(m + n)^{m+n}} < \frac{m!}{m^{m}} · \frac{n!}{n^{n}} .

B3. Determine all real numbers a > 0 for which there exists a nonnegative continuous function f(x) defined on [0, a] with the property that the region

R = {(x, y) : 0 ≤ x ≤ a, 0 ≤ y ≤ f(x)}

has perimeter k units and area k square units for some real number k.

B4. Let n be a positive integer, n ≥ 2, and put θ = 2π/n. Define points P_{k} = (k, 0) in the xy-plane, for k = 1, 2, …, n. Let R_{k} be the map that rotates the plane counterclockwise by the angle θ about the point P_{k}. Let R denote the map obtained by applying, in order, R_{1}, then R_{2}, …, then R_{n}. For an arbitrary point (x, y), find, and simplify, the coordinates of R(x, y).

B5. Evaluate

lim_{x→1−} ∏_{n=0}^{∞} (\frac{1 + x^{n+1}}{1 + x^{n}} )^{x^{n}} .

B6. Let A be a non-empty set of positive integers, and let N(x) denote the number of elements of A not exceeding x. Let B denote the set of positive integers b that can be written in the form b = a − a′ with a ∈ A and a′ ∈ A. Let b_{1} < b_{2} < ⋯ be the members of B, listed in increasing order. Show that if the sequence b_{i+1} − b_{i} is unbounded, then lim_{x→∞} N(x)/x = 0.