SIXTY-FIRST ANNUAL WILLIAM LOWELL PUTNAM MATHEMATICAL COMPETITION

Saturday, December 2, 2000 Examination A

A1. Let A be a positive real number. What are the possible values of ∑_{j=0}^{∞} x_{j}^{2}, given that x_{0}, x_{1}, x_{2}, … are positive numbers for which ∑_{j=0}^{∞} x_{j} = A?

A2. Prove that there exist infinitely many integers n such that n, n + 1, and n + 2 are each the sum of two squares of integers. [Example: 0 = 0^{2} + 0^{2}, 1 = 0^{2} + 1^{1}, and 2 = 1^{1} + 1^{1}.]

A3. The octagon P_{1}P_{2}P_{3}P_{4}P_{5}P_{6}P_{7}P_{8} is inscribed in a circle, with the vertices around the circumference in the given order. Given that the polygon P_{1}P_{3}P_{5}P_{7} is a square of area 5 and the polygon P_{2}P_{4}P_{6}P_{8} is a rectangle of area 4, find the maximum possible area of the octagon.

A4. Show that the improper integral

lim_{B→∞} ∫_{0}^{B} sin(x) sin(x^{2}) dx

converges.

A5. Three distinct points with integer coordinates lie in the plane on a circle of radius r > 0. Show that two of these points are separated by a distance of at least r^{1/3}.

A6. Let f(x) be a polynomial with integer coefficients. Define a sequence A_{0}, a_{1}, … of integers such that a_{0} = 0 and a_{n+1} = f(a_{n}) for all n ≥ 0. Prove that if there exists a positive integer m for which a_{m} = 0, then either a_{1} = 0 or a_{2} = 0.

SIXTY-FIRST ANNUAL WILLIAM LOWELL PUTNAM MATHEMATICAL COMPETITION

Saturday, December 2, 2000 Examination B

B1. Let a_{j}, b_{j}, and c_{j} be integers for 1 ≤ j ≤ N, Assume, for each j, that at least one of a_{j}, b_{j}, c_{j} is odd. Show that there exist integers r, s, t such that ra_{j} + sb_{j} + tc_{j} is odd for at least 4N/7 values of j, 1 ≤ j ≤ N.

B2. Prove that the expression

\frac{gcd(m, n)}{n}\binom{n}{m}

is an integer for all pairs of integers n ≥ m ≥ 1. [Here \binom{n}{m} = \frac{n!}{m!(n−m)!} and gcd(m, n) is the greatest common divisor of m and n.]

B3. Let f(t) = ∑_{j=1}^{N} a_{j} sin(2πjt), where each a_{j} is real and a_{N} ≠ 0. Let N_{k} denote the

number of zeros (including multiplicities) of \frac{d^{k}f}{dt^{k}}. Prove that

N_{0} ≤ N_{1} ≤ N_{2} ≤ ⋯ and lim_{k→∞} N_{k} = 2N.

[Added note: Presumably, one is to restrict t to the interval [0, 1) when counting the zeros.]

B4. Let f(x) be a continuous function such that f(2x^{2} − 1) = 2xf(x) for all x. Show that f(x) = 0 for −1 ≤ x ≤ 1.

B5. Let S_{0} be a finite set of positive integers. We define finite sets S_{1}, S_{2}, … of positive integers as follows:

Integer a is in S_{n+1} if and only if exactly one of a − 1 or a is in S_{n}. Show that there exist infinitely many integers N for which S_{N} = S_{0} ∪ {N + a : a ∈ S_{0}}.

B6. Let B be a set of more than 2^{n+1}/n distinct points with coordinates of the form (±1, ±1, …, ±1) in n-dimensional space, with n ≥ 3. Show that there are three distinct points in B which are the vertices of an equilateral triangle.