SIXTY-SIXTH ANNUAL WILLIAM LOWELL PUTNAM MATHEMATICAL COMPETITION

Saturday, December 3, 2005 Examination A

A1. Show that every positive integer is a sum of one or more numbers of the form 2^{r}3^{s}, where r and s are nonnegative integers and no summand divides another. (For example, 23 = 9 + 8 + 6.)

A2. Let S = {(a, b) | a = 1, 2, …, n, b = 1, 2, 3}. A rook tour of S is a polygonal path made up of line segments connecting points p_{1}, p_{2}, …, p_{3n} in sequence such that (i) p_{i} ∈ S, (ii) p_{i} and p_{i+1} are a unit distance apart, for 1 ≤ i < 3n, (iii) for each p ∈ S there is a unique i such that p_{i} = p. How many rook tours are there that begin at (1, 1) and end at (n, 1)? (An example of such a rook tour for n = 5 is depicted below.)

• • • • • • • • • • • • • • •

A3. Let p(z) be a polynomial of degree n, all of whose zeros have absolute value 1 in the complex plane. Put g(z) = p(z)/z^{n/2}. Show that all zeros of g′(z) = 0 have absolute value 1.

A4. Let H be an n × n matrix all of whose entries are ±1 and whose rows are mutually orthogonal. Suppose H has an a × b submatrix whose entries are all 1. Show that ab ≤ n.

A5. Evaluate

∫_{0}^{1} \frac{log(x + 1)}{x^{2} + 1} dx.

A6. Let n be given, n ≥ 4, and suppose that P_{1}, P_{2}, …, P_{n} are n randomly, independently and uniformly, chosen points on a circle. Consider the convex n-gon whose vertices are the P_{i}. What is the probability that at least one of the vertex angles of this polygon is acute?

SIXTY-SIXTH ANNUAL WILLIAM LOWELL PUTNAM MATHEMATICAL COMPETITION

Saturday, December 3, 2005 Examination B

B1. Find a nonzero polynomial P (x, y) such that P (⌊a⌋, ⌊2a⌋) = 0 for all real numbers a. (Note: ⌊ν⌋ is the greatest integer less than or equal to ν.)

B2. Find all positive integers n, k_{1}, …, k_{n} such that k_{1} + ⋯ + k_{n} = 5n − 4 and

\frac{1}{k_{1}} + ⋯ + \frac{1}{k_{n}} = 1.

B3. Find all differentiable functions f : (0, ∞) → (0, ∞) for which there is a positive real number a such that

f′ (\frac{a}{x}) = \frac{x}{f(x)}

for all x > 0.

B4. For positive integers m and n, let f(m, n) denote the number of n-tuples (x_{1}, x_{2}, …, x_{n}) of integers such that |x_{1}| + |x_{2}| + ⋯ + |x_{n}| ≤ m. Show that f(m, n) = f(n, m).

B5. Let P (x_{1}, …, x_{n}) denote a polynomial with real coefficients in the variables x_{1}, …, x_{n}, and suppose that

(a)  (\frac{∂^{2}}{∂x_{1}^{2}} + ⋯ + \frac{∂^{2}}{∂x_{n}^{2}} ) P (x_{1}, …, x_{n}) = 0 (identically)

and that

(b)  x_{1}^{2} + ⋯ + x_{n}^{2} divides P (x_{1}, …, x_{n}).

Show that P = 0 identically.

B6. Let S_{n} denote the set of all permutations of the numbers 1, 2, …, n. For π ∈ S_{n}, let σ(π) = 1 if π is an even permutation and σ(π) = −1 if π is an odd permutation. Also, let ν(π) denote the number of fixed points of π. Show that

∑_{π∈S_{n}} \frac{σ(π)}{ν(π) + 1} = (−1)^{n+1} \frac{n}{n + 1}.