Putnam Mathematical Competition, 2 December 2000

Problem 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? Problem 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^{2}, and 2 = 1^{2} + 1^{2}.] Problem 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. Problem A4 Show that the improper integral

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

converges. Problem 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}. Problem 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.

Problem 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. Problem 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 divisior of m and n.] Problem 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.

Problem 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. Problem 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}}. Problem 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.

Solutions

D. J. Bernstein, 3 December 2000

Problem 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?

Solution: One can achieve any real number s with 0 < s < A^{2} as follows. Define u = s/A^{2}; then 0 < u < 1. Define r = (1 − u)/(1 + u); then 0 < r < 1. Define x_{j} = A(1 − r)r^{j}; then x_{j} > 0. Finally ∑ x_{j} = A(1 − r) ∑ r^{j} = A and ∑ x_{j}^{2} = A^{2}(1 − r)^{2} ∑ r^{2j} = A^{2}(1 − r)^{2}/(1 − r^{2}) = A^{2}(1 − r)/(1 + r) = A^{2}u = s.

One cannot achieve any other number, since 0 < ∑ x_{j}^{2} < (∑ x_{j})^{2} = A^{2}.

Problem 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^{2}, and 2 = 1^{2} + 1^{2}.]

Solution: There are infinitely many integers n of the form 2k^{2}(k + 1)^{2}; note that n = (k^{2}+k)^{2}+(k^{2}+k)^{2}, n+1 = (k^{2}+2k)^{2}+(k^{2}−1)^{2}, and n+2 = (k^{2}+k+1)^{2}+(k^{2}+k−1)^{2}.

Problem 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.

Solution: The circle circumscribes a square of area 5, so the circle has radius \sqrt{5/2}. Hence the rectangle has sides \sqrt{2} and \sqrt{8}. Without loss of generality assume that P_{2}P_{4} has length \sqrt{2}.

Put P_{2}, P_{4}, P_{6}, P_{8} into the complex plane at \sqrt{2}(1/2 + i), \sqrt{2}(−1/2 + i), \sqrt{2}(−1/2 − i), \sqrt{2}(1/2 − i). Put P_{1} into the complex plane at \sqrt{5/2} exp(iθ); then P_{3}, P_{5}, P_{7} are at i\sqrt{5/2} exp(iθ), −\sqrt{5/2} exp(iθ), −i\sqrt{5/2} exp(iθ).

The triangles P_{8}P_{1}P_{2} and P_{4}P_{5}P_{6} each have area \sqrt{5} cos θ − 1. The triangles P_{2}P_{3}P_{4} and P_{6}P_{7}P_{8} each have area \sqrt{5/4} cos θ − 1. Hence the octagon has area 3\sqrt{5} cos θ. The maximum possible area is 3\sqrt{5}, achieved for θ = 0.

Problem A4 Show that the improper integral

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

converges.

Solution: Rewrite sin x sin x^{2} as (cos(x^{2} − x) − cos(x^{2} + x))/2. In the improper integral ∫_{0}^{∞} cos(x^{2} + x) dx substitute u = x^{2} + x to obtain ∫_{0}^{∞} 2 cos u du/(\sqrt{1 + 4u} − 1). The integrand is negative on (π/2, 3π/2), positive on (3π/2, 5π/2), etc. The corresponding integrals form an alternating decreasing series since

∫_{s}^{s+π} \frac{2 |cos u| du}{\sqrt{1 + 4u} − 1} > ∫_{s}^{s+π} \frac{2 |cos u| du}{\sqrt{1 + 4u + 4π} − 1} = ∫_{s+π}^{s+2π} \frac{2 |cos v| dv}{\sqrt{1 + 4v} − 1}.

Thus ∫_{0}^{∞} cos(x^{2} + x) dx converges. Similar comments apply to ∫_{0}^{∞} cos(x^{2} − x) dx.

Problem 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}.

Solution: The following solution is stolen from Dave Rusin.

The triangle formed by the points has area abc/4r where a, b, c are the distances between the points. If a, b, c < r^{1/3} then the area is smaller than 1/4; but the area is at least 1/2 since the points have integer coordinates.

Problem 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.

Solution: The stated conclusion is false, because the word “either” means that exactly one is true. Presumably the intent was to say that a_{1} = 0 or a_{2} = 0.

Fact 1: a_{m−1} divides a_{1}. Proof: a_{m−1} divides f(a_{m−1}) − f(0) = a_{m} − a_{1} = −a_{1}.

Fact 2: a_{1} divides a_{n} if n ≥ 0. Proof: If n = 0 then a_{n} = 0. Otherwise a_{1} divides a_{n−1} by induction, so it divides f(a_{n−1}) − f(0) = a_{n} − a_{1}.

Fact 3: a_{n} − a_{n−1} divides a_{n+k} − a_{n+k−1} if n ≥ 1 and k ≥ 0. Proof: If k = 0 then a_{n} −a_{n−1} = a_{n+k} −a_{n+k−1}. Otherwise a_{n} −a_{n−1} divides a_{n+k−1} −a_{n+k−2} by induction, so it divides f(a_{n+k−1}) − f(a_{n+k−2}) = a_{n+k} − a_{n+k−1}.

Fact 4: a_{n} − a_{n−1} ∈ {−a_{1}, a_{1}} if 1 ≤ n ≤ m. Proof: Define k = m − n. Then a_{n} − a_{n−1} divides a_{n+k}−a_{n+k−1} = a_{m}−a_{m−1} = −a_{m−1}, which divides a_{1}; and a_{1} divides a_{n}−a_{n−1}.

Fact 5: a_{2} = 0. Proof: a_{2} − a_{1} ∈ {−a_{1}, a_{1}}. Suppose that a_{2} ≠ 0. Then a_{2} = 2a_{1} and a_{1} ≠ 0, so m ≥ 3. Observe that a_{n} = na_{1} for n ∈ {0, 1, 2}, but not for n = m. Find the smallest n ≥ 3 for which a_{n} ≠ na_{1}. Then a_{n−1} = (n − 1)a_{1}, so a_{n} − a_{n−1} ≠ a_{1}, so a_{n} − a_{n−1} = −a_{1}, so a_{n} = (n − 2)a_{1} = a_{n−2}. By induction a_{k} ∈ {a_{n−1}, a_{n−2}} for all k ≥ n. In particular 0 = a_{m} ∈ {a_{n−1}, a_{n−2}}. Thus (n − 1)a_{1} = 0 or (n − 2)a_{1} = 0. Contradiction.

I would have written this problem as follows: “Define a_{0} = 0 and a_{n+1} = f(a_{n}), where f is a polynomial with integer coefficients. Assume that a_{2000} = 0. Prove that a_{2} = 0.”

Problem 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.

Solution: Define f(u, v, w) = # {j : (a_{j} mod 2, b_{j} mod 2, c_{j} mod 2) = (u, v, w)}. Define g(r, s, t) = # {j : ra_{j} + sb_{j} + tc_{j} is odd}. Then

\begin{aligned}g(1, 0, 0) & = f(1, 0, 0) + f(1, 0, 1) + f(1, 1, 0) + f(1, 1, 1), \\ g(0, 1, 0) & = f(0, 1, 0) + f(0, 1, 1) + f(1, 1, 0) + f(1, 1, 1), \\ g(0, 0, 1) & = f(0, 0, 1) + f(0, 1, 1) + f(1, 0, 1) + f(1, 1, 1), \\ g(1, 1, 0) & = f(1, 0, 0) + f(0, 1, 0) + f(1, 0, 1) + f(0, 1, 1), \\ g(1, 0, 1) & = f(1, 0, 0) + f(0, 0, 1) + f(1, 1, 0) + f(0, 1, 1), \\ g(0, 1, 1) & = f(0, 1, 0) + f(0, 0, 1) + f(1, 1, 0) + f(1, 0, 1), \\ g(1, 1, 1) & = f(1, 0, 0) + f(0, 1, 0) + f(0, 0, 1) + f(1, 1, 1). \end{aligned}

Add: g(1, 0, 0) + g(0, 1, 0) + g(0, 0, 1) + g(1, 1, 0) + g(1, 0, 1) + g(0, 1, 1) + g(1, 1, 1) = 4f(1, 0, 0)+4f(0, 1, 0)+4f(0, 0, 1)+4f(1, 1, 0)+4f(1, 0, 1)+4f(0, 1, 1)+4f(1, 1, 1) = 4N. Thus g(r, s, t) ≥ 4N/7 for some (r, s, t).

Problem 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 divisior of m and n.]

Solution: Presumably “divisior” means “divisor.”

Find integers a, b with gcd(m, n) = am + bn. Then (gcd(m, n)/n)\binom{n}{m} = a\binom{n−1}{m−1} + b\binom{n}{m}.

Problem 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.

Solution: The stated conclusion is false: f has infinitely many roots. Presumably the intent was to say “roots in [0, 1).” Does anyone proofread the Putnam problems before they are printed?

Say the roots of f in [0, 1) are r_{1} < r_{2} < ⋯ < r_{n} with multiplicities m_{1}, m_{2}, …, m_{n}. Then f′ has a root at r_{i} with multiplicity m_{i} − 1 if m_{i} ≥ 2; a root in (r_{i}, r_{i+1}) for 1 ≤ i ≤ n − 1; a root in (r_{n}, 1 + r_{1}); and possibly more roots. Thus there are at least 1 + (n − 1) + ∑_{i}(m_{i} − 1) = ∑_{i} m_{i} roots of f′ in [r_{1}, 1 + r_{1}), hence in [0, 1); and there are exactly ∑_{i} m_{i} roots of f in [0, 1). Thus N_{0} ≤ N_{1}. By the same argument N_{1} ≤ N_{2}, N_{2} ≤ N_{3}, etc.

Find k_{0} such that ∑_{1≤j<N}(j/N)^{k} |a_{j}/a_{N}| < 1/2 for all k ≥ k_{0}. Abbreviate d/dt as D. I will show that D^{k}f has exactly 2N roots in [0, 1) for k ≥ k_{0}.

Find a real number s with (D^{k} sin)(2πNs) = 1. Then (D^{k} sin)(2πNt) decreases from 1 at s to −1 at s + 1/2N, increases to 1 at s + 2/2N, etc. By construction

\frac{(D^{k}f)(t)}{(2πN)^{k}a_{N}} = (D^{k} sin)(2πNt) + ∑_{1≤j<N}(\frac{j}{N} )^{k} \frac{a_{j}}{a_{N}} (D^{k} sin)(2πjt),

so (D^{k}f)(t) has the same sign as a_{N}(D^{k} sin)(2πNt) whenever |(D^{k} sin)(2πNt)| > 1/2: in particular, at s, s + 1/2N, s + 2/2N, . . .. Therefore D^{k}f has at least one root in [s, s + 1/2N).

It is not possible for D^{k}f to have two roots in [s, s + 1/2N). Indeed, the roots are in the subinterval [s + 1/6N, s + 1/3N] where (D^{k} sin)(2πNt) is in [−1/2, 1/2]. If there were two roots then D^{k+1}f would also have a root in the subinterval, so (D^{k+1} sin)(2πNt) would be in [−1/2, 1/2]; contradiction.

The same comments apply to [s + 1/2N, s + 2/2N) and so on. Thus D^{k}f has exactly 2N roots in [s, s + 1), hence in [0, 1).

Problem 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.

Solution: Thanks to Kahan for pointing out the role of cos here. My original solution constructed cos manually.

Define g(y) = f(cos 2πy). Then g is continuous; g is even; g has period 1; and g(2y) = f(cos 4πy) = f(2(cos 2πy)^{2} − 1) = 2(cos 2πy)f(cos 2πy) = 2(cos 2πy)g(y).

In particular, g(1/3) = g(−1/3) = g(2/3) = −g(1/3), so g(1/3) = 0. Thus g(n+1/3) = 0 for all integers n. In fact, g((n+1/3)/2^{k}) = 0 for all n and all k ≥ 0. Indeed, if k ≥ 1, then g((n+1/3)/2^{k−1}) = 0 by induction, and cos(2π(n+1/3)/2^{k}) ≠ 0, so g((n+1/3)/2^{k}) = 0.

The set {(n + 1/3)/2^{k}} is dense, so g is 0 everywhere. Thus f is 0 on the range of cos, namely [−1, 1].

Robin Chapman comments that one can remove the 2 cos 2πy factor by considering f(cos 2πy)/ sin 2πy for all non-integer y.

Problem 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}}.

Solution: Define a polynomial f_{n} as ∑_{a∈S_{n}} x^{a}. Then f_{n+1} ≡ (x + 1)f_{n} (mod 2), so f_{n} ≡ (x + 1)^{n}f_{0}.

In particular, if n is a power of 2 larger than deg f_{0}, then f_{n} ≡ (x+1)^{n}f_{0} ≡ (x^{n} +1)f_{0} = x^{n}f_{0} + f_{0}, and all coefficients of x^{n}f_{0} + f_{0} are 0 or 1, so f_{n} = x^{n}f_{0} + f_{0}; i.e., a ∈ S_{n} if and only if a ∈ S_{0} or a − n ∈ S_{0}.

Problem 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.

Solution: The following solution is a composite of solutions from several other people.

Define A = {(±1, ±1, …, ±1)}. For each p ∈ A define Δ_{p} = {q ∈ B : |p − q| = 2}. Then ∑_{p∈A} #Δ_{p} = ∑_{q∈B} # {p ∈ A : |p − q| = 2} = ∑_{q∈B} n = n#B > 2^{n+1} = 2#A. Thus #Δ_{p} > 2 for some p ∈ A. Any distinct q_{1}, q_{2}, q_{3} ∈ Δ_{p} form an equilateral triangle in B.