SIXTY-SECOND ANNUAL WILLIAM LOWELL PUTNAM MATHEMATICAL COMPETITION

Saturday, December 1, 2001 Examination A

A1. Consider a set S and a binary operation ∗ on S (that is, for each a, b in S, a ∗ b is in S). Assume that (a ∗ b) ∗ a = b for all a, b in S. Prove that a ∗ (b ∗ a) = b for all a, b in S.

A2. You have coins C_{1}, C_{2}, …, C_{n}. For each k, coin C_{k} is biased so that, when tossed, it has probability \frac{1}{2k+1} of falling heads. If the n coins are tossed, what is the probability that the number of heads is odd? Express the answer as a rational function of n.

A3. For each integer m, consider the polynomial

P_{m}(x) = x^{4} − (2m + 4)x^{2} + (m − 2)^{2}.

For what values of m is P_{m}(x) the product of two nonconstant polynomials with integer coefficients?

A4. Triangle ABC has area 1. Points E, F, G lie, respectively, on sides BC, CA, AB such that AE bisects BF at point R, BF bisects CG at point S, and CG bisects AE at point T. Find the area of triangle RST.

A5. Prove that there are unique positive integers a, n such that

a^{n+1} − (a + 1)^{n} = 2001.

A6. Can an arc of a parabola inside a circle of radius 1 have length greater than 4?

SIXTY-SECOND ANNUAL WILLIAM LOWELL PUTNAM MATHEMATICAL COMPETITION

Saturday, December 1, 2001 Examination B

B1. Let n be an even positive integer. Write the numbers 1, 2, …, n^{2} in the squares of an n × n grid so that the k^{th} row, from left to right, is

(k − 1)n + 1, (k − 1)n + 2, …, (k − 1)n + n.

Color the squares of the grid so that half of the squares in each row and in each column are red and the other half are black (a checkerboard coloring is one possibility). Prove that for each such coloring, the sum of the numbers on the red squares is equal to the sum of the numbers on the black squares.

B2. Find all pairs of real numbers (x, y) satisfying the system of equations

\begin{aligned}\frac{1}{x} + \frac{1}{2y} & = (x^{2} + 3y^{2})(3x^{2} + y^{2}) \\ \frac{1}{x} − \frac{1}{2y} & = 2(y^{4} − x^{4}). \end{aligned}

B3. For any positive integer n let ⟨n⟩ denote the closest integer to \sqrt{n}. Evaluate

∑_{n=1}^{∞} \frac{2^{⟨n⟩} + 2^{−⟨n⟩}}{2^{n}} .

B4. Let S denote the set of rational numbers different from −1, 0 and 1. Define f : S → S

by f(x) = x − \frac{1}{x}. Prove or disprove that

⋂_{n=1}^{∞} f^{(n)}(S) = ∅,

where f^{(n)} = \underbrace{f ∘ f ∘ ⋯ ∘ f}_{n times}.

(Note: f(S) denotes the set of all values f(s) for s ∈ S.)

B5. Let a and b be real numbers in the interval (0, \frac{1}{2}) and let g be a continuous realvalued function such that g(g(x)) = ag(x) + bx for all real x. Prove that g(x) = cx for some constant c.

B6. Assume that (a_{n})_{n≥1} is an increasing sequence of positive real numbers such that lim_{n→∞} \frac{a_{n}}{n} = 0. Must there exist infinitely many positive integers n such that

a_{n−1} + a_{n+i} < 2a_{n}, for i = 1, 2, …, n − 1 ?