1999 Putnam problems and unofficial solutions

As usual, first come the problems, then the problems with solutions. Comments and criticism at the end. Send any followup remarks to the USENET newsgroup sci.math.

Problems

Problem A1 Find polynomials f(x), g(x) and h(x), if they exist, such that, for all x,

|f(x)| − |g(x)| + h(x) = \begin{cases}−1 if & x < −1 \\ 3x + 2 if & −1 ≤ x ≤ 0 \\ −2x + 2 if & x > 0. \end{cases}

Problem A2 Let p(x) be a polynomial that is non-negative for all x. Prove that, for some k, there are polynomials f_{1}(x), …, f_{k}(x) such that

p(x) = ∑_{j=1}^{k}(f_{j}(x))^{2}.

Problem A3 Consider the power series expansion

\frac{1}{1 − 2x − x^{2}} = ∑_{n=0}^{∞} a_{n}x^{n}.

Prove that, for each integer n ≥ 0, there is an integer m such that a_{n}^{2} + a_{n+1}^{2} = a_{m}.

Problem A4 Sum the series

∑_{m=1}^{∞} ∑_{n=1}^{∞} \frac{m^{2}n}{3^{m}(n3^{m} + m3^{n})}.

Problem A5 Prove that there is a constant C such that, if p(x) is a polynomial of degree 1999, then

|p(0)| ≤ C ∫_{−1}^{1} |p(x)| dx.

Problem A6 The sequence (a_{n})_{n≥1} is defined by a_{1} = 1, a_{2} = 2, a_{3} = 24, and, for n ≥ 4,

a_{n} = \frac{6a_{n−1}^{2}a_{n−3} − 8a_{n−1}a_{n−2}^{2}}{a_{n−2}a_{n−3}} .

Show that, for all n, a_{n} is an integer multiple of n. Problem B1 Right triangle ABC has right angle at C and ^{}B̸AC = θ; the point D is chosen on AB so that |AC| = |AD| = 1; the point E is chosen on BC so that ^{}C̸DE = θ. The perpendicular to BC at E meets AB at F. Evaluate lim_{θ→0} |EF |. [Here, |P Q| denotes the length of the line segment P Q.]

[figure: A; θ; B; C; D; θ; E; F]

Problem B2 Let P (x) be a polynomial of degree n such that P (x) = Q(x)P′′(x), where Q(x) is a quadratic polynomial and P′′(x) is the second derivative of P (x). Show that if P (x) has at least two distinct roots then it must have n distinct roots. [The roots may be either real or complex.] Problem B3 Let A = {(x, y) : 0 ≤ x, y < 1}. For (x, y) ∈ A, let

S(x, y) = ∑_{\frac{1}{2} ≤ \frac{m}{n} ≤2} x^{m}y^{n},

where the sum ranges over all pairs (m, n) of positive integers satisfying the indicated inequalities. Evaluate

lim_{{(x,y)→(1,1) \atop (x,y)∈A}}(1 − xy^{2})(1 − x^{2}y)S(x, y).

Problem B4

Let f be a real function with a continuous third derivative such that f(x), f′(x), f′′(x), f′′′(x) are positive for all x. Suppose that f′′′(x) ≤ f(x) for all x. Show that f′(x) < 2f(x) for all x.

Problem B5

For an integer n ≥ 3, let θ = 2π/n. Evaluate the determinant of the n × n matrix I + A, where I is the n × n identity matrix and A = (a_{jk}) has entries a_{jk} = cos(jθ + kθ) for all j, k.

Problem B6

Let S be a finite set of integers, each greater than 1. Suppose that for each integer n there is some s ∈ S such that gcd(s, n) = 1 or gcd(s, n) = s. Show that there exist s, t ∈ S such that gcd(s, t) is prime. [Here, gcd(a, b) denotes the greatest common divisor of a and b.]

Unofficial solutions

Problem A1

Find polynomials f(x), g(x) and h(x), if they exist, such that, for all x,

|f(x)| − |g(x)| + h(x) = \begin{cases}−1 if & x < −1 \\ 3x + 2 if & −1 ≤ x ≤ 0 \\ −2x + 2 if & x > 0. \end{cases}

Solution: Take f(x) = (3/2)(x + 1), g(x) = (5/2)x, and h(x) = 1/2 − x.

If x < −1 then |f(x)| = −(3/2)(x + 1) and |g(x)| = −(5/2)x so |f(x)| − |g(x)| + h(x) = −(3/2)x − 3/2 + (5/2)x + 1/2 − x = −1.

If −1 ≤ x ≤ 0 then |f(x)| = (3/2)(x+1) and |g(x)| = −(5/2)x so |f(x)|−|g(x)|+h(x) = (3/2)x + 3/2 + (5/2)x + 1/2 − x = 3x + 2.

If x > 0 then |f(x)| = (3/2)(x + 1) and |g(x)| = (5/2)x so |f(x)| − |g(x)| + h(x) = (3/2)x + 3/2 − (5/2)x + 1/2 − x = −2x + 2.

Problem A2 Let p(x) be a polynomial that is non-negative for all x. Prove that, for some k, there are polynomials f_{1}(x), …, f_{k}(x) such that

p(x) = ∑_{j=1}^{k}(f_{j}(x))^{2}.

Solution: If p is constant then p(x) = (p(0)^{1/2})^{2}. Otherwise find a root r + si of p. If s ≠ 0 then r − si is another root of p, so p(x) is divisible by (x − r − si)(x − r + si) = (x − r)^{2} + s^{2}. If s = 0 then p(x) must be divisible by (x − r)^{2}; otherwise p(r + ϵ)p(r − ϵ) would be negative for small ϵ. Either way p(x) = ((x − r)^{2} + s^{2})q(x) for some polynomial q. Now (x − r)^{2} + s^{2} is positive for all x ≠ r, so q(x) is nonnegative for all x ≠ r; by continuity, q(x) is nonnegative for all x. By induction on degree, q(x) = ∑_{j} f_{j}(x)^{2} for some f_{1}, f_{2}, . . .. Thus p(x) = ∑_{j}((x − r)f_{j}(x))^{2} + ∑_{j}(sf_{j}(x))^{2} as desired. Problem A3 Consider the power series expansion

\frac{1}{1 − 2x − x^{2}} = ∑_{n=0}^{∞} a_{n}x^{n}.

Prove that, for each integer n ≥ 0, there is an integer m such that

a_{n}^{2} + a_{n+1}^{2} = a_{m}.

Solution: Write r = 1 + \sqrt{2} and s = 1 − \sqrt{2}. Then rs = −1 and r + s = 2, so

\begin{aligned}∑_{n} a_{n}x^{n} & = \frac{1}{1 − 2x − x^{2}} = \frac{1}{(1 − rx)(1 − sx)} = \frac{r/(r − s)}{1 − rx} − \frac{s/(r − s)}{1 − sx} \\ & = ∑_{n} \frac{r^{n+1} − s^{n+1}}{r − s} x^{n}. \end{aligned}

Thus a_{n} = (r^{n+1} − s^{n+1})/(r − s), and

a_{n}^{2} + a_{n+1}^{2} = \frac{r^{2n+2} + s^{2n+2} − 2(rs)^{n+1} + r^{2n+4} + s^{2n+4} − 2(rs)^{n+2}}{(r − s)^{2}}

= \frac{r^{2n+3}(r + 1/r) + s^{2n+3}(s + 1/s) − 2(rs)^{n+1}(1 + rs)}{(r − s)^{2}}

= \frac{r^{2n+3}(r − s) + s^{2n+3}(s − r) − 2(rs)^{n+1}(1 − 1)}{(r − s)^{2}} = \frac{r^{2n+3} − s^{2n+3}}{r − s} = a_{2n+2}.

Another approach: Define b_{n} = a_{n}^{2} + a_{n+1}^{2}; then b_{0} = a_{2} and b_{1} = a_{4}. Starting from the identity a_{n+2} = 2a_{n+1} + a_{n} one can check that b_{n+2} = 6b_{n+1} − b_{n} and that a_{2n+6} = 6a_{2n+4} − a_{2n+2}, so b_{n} = a_{2n+2} for all n by induction. Yet another approach: Convert the identity a_{n} = 2a_{n−1} + a_{n−2} into the matrix equation

( \begin{matrix}2 & 1 \\ 1 & 0 \end{matrix} )^{n} = ( \begin{matrix}a_{n} & a_{n−1} \\ a_{n−1} & a_{n−2} \end{matrix} )

and square both sides to obtain

( \begin{matrix}a_{2n} & a_{2n−1} \\ a_{2n−1} & a_{2n−2} \end{matrix} ) = ( \begin{matrix}a_{n} & a_{n−1} \\ a_{n−1} & a_{n−2} \end{matrix} )^{2} = ( \begin{matrix}a_{n}^{2} + a_{n−1}^{2} & a_{n−1}(a_{n} + a_{n−2}) \\ a_{n−1}(a_{n} + a_{n−2}) & a_{n−1}^{2} + a_{n−2}^{2} \end{matrix} ) .

Problem A4 Sum the series

∑_{m=1}^{∞} ∑_{n=1}^{∞} \frac{m^{2}n}{3^{m}(n3^{m} + m3^{n})}.

Solution: All sums here are absolutely convergent. Write S for the desired sum. Then

\begin{aligned}2S & = ∑_{m,n} \frac{m^{2}n}{3^{m}(n3^{m} + m3^{n})} + ∑_{m,n} \frac{n^{2}m}{3^{n}(m3^{n} + n3^{m})} \\ & = ∑_{m,n} \frac{m^{2}n3^{n} + n^{2}m3^{m}}{3^{m}3^{n}(m3^{n} + n3^{m})} = ∑_{m,n} \frac{mn}{3^{m}3^{n}} = T^{2} \end{aligned}

where T = ∑_{m}(m/3^{m}). If 0 < x < 1 then x/(1 − x) = ∑_{m} x^{m}. Differentiate: 1/(1 − x)^{2} = ∑_{m} mx^{m−1}. Substitute x = 1/3: 9/4 = ∑_{m} m/3^{m−1} = 3T. Thus T = 3/4 and S = T^{2}/2 = 9/32.

Problem A5 Prove that there is a constant C such that, if p(x) is a polynomial of degree 1999, then

|p(0)| ≤ C ∫_{−1}^{1} |p(x)| dx.

Solution: Factor p(x) as ℓ ∏_{1≤j≤1999}(x − r_{j}).

Define S_{k} = {x : 0.999 − 0.001k < x < 1 − 0.001k}. The 2000 sets S_{0}, S_{1}, …, S_{1999} are disjoint, so there is some k such that S_{k} contains none of the real parts of r_{1}, …, r_{1999}. Write u = 0.9995 − 0.001k and v = 0.9996 − 0.001k.

Fix x ∈ [u, v]. If |r_{j}| ≤ 2 then |x − r_{j}| ≥ 0.0002 ≥ |r_{j}| /10000 by choice of k. If |r_{j}| > 2 then |x − r_{j}| ≥ |r_{j}| − 1 ≥ |r_{j}| /10000 since [u, v] ⊆ [−1, 1]. Consequently |p(x)| = |ℓ| ∏_{j} |x − r_{j}| ≥ |ℓ| ∏_{j}(|r_{j}| /10000) = |p(0)| /10000^{1999}.

Thus ∫_{−1}^{1} |p(x)| dx ≥ ∫_{u}^{v} |p(x)| dx ≥ (v − u) |p(0)| /10000^{1999} = |p(0)| /10000^{2000}.

Problem A6

The sequence (a_{n})_{n≥1} is defined by a_{1} = 1, a_{2} = 2, a_{3} = 24, and, for n ≥ 4,

a_{n} = \frac{6a_{n−1}^{2}a_{n−3} − 8a_{n−1}a_{n−2}^{2}}{a_{n−2}a_{n−3}} .

Show that, for all n, a_{n} is an integer multiple of n.

Solution: Define b_{n} = a_{n+1}/a_{n}, so that a_{n} = b_{n−1}b_{n−2} ⋯ b_{2}b_{1}. Then b_{1} = 2, b_{2} = 12, and b_{k+2} = 6b_{k+1} − 8b_{k}; by induction b_{k} = 4^{k} − 2^{k} = (2^{k} − 1)2^{k}.

It suffices to show that ord_{p} a_{n} ≥ ord_{p} n for all primes p. If p is odd then p divides 2^{k} −1, and hence b_{k}, whenever p − 1 divides k; if p = 2 then p divides 2^{k}, and hence b_{k}, for all k. In either case

ord_{p} a_{n} ≥ ⌊\frac{n − 1}{p − 1}⌋ ≥ ⌊\frac{p^{ord_{p} n} − 1}{p − 1}⌋ ≥ ⌊\frac{(p − 1) ord_{p} n}{p − 1}⌋ = ord_{p} n.

Problem B1

Right triangle ABC has right angle at C and ^{}B̸AC = θ; the point D is chosen on AB so that |AC| = |AD| = 1; the point E is chosen on BC so that ^{}C̸DE = θ. The perpendicular to BC at E meets AB at F. Evaluate lim_{θ→0} |EF |. [Here, |P Q| denotes the

length of the line segment P Q.]

[figure: A; θ; B; C; D; θ; E; F]

Solution: The answer is 1/3.

Put A, B, C into the complex plane with A = 0, C = 1, and B at positive angle θ. Then B = 1 + i tan θ and D = e^{iθ}.

Define z = (1 − cos θ)/(cos θ − cos 2θ) and s = sin θ + z(sin θ − sin 2θ). From the power series sin θ = θ +⋯ and cos θ = 1−θ^{2}/2+⋯ we see that z = 1/3+⋯, s = (2/3)θ +⋯, and tan θ = θ + ⋯, so lim_{θ→0}(s/ tan θ) = 2/3. Note that z > 0 and 0 < s < tan θ for sufficiently small θ.

Now define X = 1 + is. Then X − D = z(e^{iθ} − e^{2iθ}) = ze^{iθ}(C − D), so ^{}C̸DX = θ; and X is on the line segment from C to B. Hence E = X. Consequently F = s/ tan θ + is and |E − F | = 1 − s/ tan θ, so lim_{θ→0} |E − F | = 1 − 2/3 = 1/3.

Problem B2

Let P (x) be a polynomial of degree n such that P (x) = Q(x)P′′(x), where Q(x) is a quadratic polynomial and P′′(x) is the second derivative of P (x). Show that if P (x) has at least two distinct roots then it must have n distinct roots. [The roots may be either real or complex.]

Solution: Let r be a complex number. Write P (x) as p_{n}(x − r)^{n} + p_{n−1}(x − r)^{n−1} + ⋯ + p_{k}(x − r)^{k} with p_{k} nonzero, and write Q(x) as q_{2}(x − r)^{2} + q_{1}(x − r) + q_{0}.

If k ≥ 2 then P′′(x) = n(n − 1)p_{n}(x − r)^{n−2} + ⋯ + k(k − 1)p_{k}(x − r)^{k−2}, with k(k − 1)p_{k} nonzero. Compare coefficients of (x − r)^{k−2}, (x − r)^{k−1}, and (x − r)^{k} in P (x) and Q(x)P′′(x) to see that q_{0} = 0, q_{1} = 0, and q_{2} = 1/k(k − 1); compare coefficients of (x − r)^{n} to see that q_{2} = 1/n(n − 1); consequently k = n.

In short, if P has a repeated root r, then P (x) = p_{n}(x − r)^{n}, so P does not have two distinct roots.

Problem B3

Let A = {(x, y) : 0 ≤ x, y < 1}. For (x, y) ∈ A, let

S(x, y) = ∑_{\frac{1}{2} ≤ \frac{m}{n} ≤2} x^{m}y^{n},

where the sum ranges over all pairs (m, n) of positive integers satisfying the indicated inequalities. Evaluate

lim_{{(x,y)→(1,1) \atop (x,y)∈A}}(1 − xy^{2})(1 − x^{2}y)S(x, y).

Solution: All sums here are absolutely convergent.

Define T_{n} = ∑_{n/2≤m≤2n} x^{m}. If n is even then T_{n} = (x^{n/2} − x^{2n+1})/(1 − x); if n is odd then T_{n} = (x^{(n+1)/2} − x^{2n+1})/(1 − x). Thus

(1 − x)S(x, y) = (1 − x) ∑_{n≥1} T_{n}y^{n} = ∑_{k≥1} x^{k}y^{2k} + ∑_{k≥0} x^{k+1}y^{2k+1} − ∑_{n≥1} x^{2n+1}y^{n}

= \frac{xy^{2}}{1 − xy^{2}} + \frac{xy}{1 − xy^{2}} − \frac{x^{3}y}{1 − x^{2}y} = \frac{(xy^{2} + xy)(1 − x^{2}y) − x^{3}y(1 − xy^{2})}{(1 − x^{2}y)(1 − xy^{2})}

= \frac{(1 − x)(xy + xy^{2} + x^{2}y + x^{2}y^{2} − x^{3}y^{3})}{(1 − x^{2}y)(1 − xy^{2})}.

The desired limit is simply lim(xy + xy^{2} + x^{2}y + x^{2}y^{2} − x^{3}y^{3}) = 3.

Problem B4

Let f be a real function with a continuous third derivative such that f(x), f′(x), f′′(x), f′′′(x) are positive for all x. Suppose that f′′′(x) ≤ f(x) for all x. Show that f′(x) < 2f(x) for all x.

Solution: Observe that lim_{x→−∞} f(x) exists and is nonnegative; lim_{x→−∞} f′(x) = 0; and lim_{x→−∞} f′′(x) = 0.

Define p = 4ff′ − 2f′′f′′. Then lim_{x→−∞} p(x) = 0, and p′ = 4f′f′ + 4(f − f′′′)f′′ ≥ 4f′f′ > 0, so p > 0.

Next define q = 3ff −2f′f′′. Then lim_{x→−∞} q(x) ≥ 0, and q′ = p+2(f −f′′′)f′ ≥ p > 0, so q > 0.

Finally define r = 3fff − 2f′f′f′. Then lim_{x→−∞} r(x) ≥ 0, and r′ = 3f′q > 0, so r > 0. Hence f′(x)^{3} < (3/2)f(x)^{3} < (2f(x))^{3}.

Problem B5

For an integer n ≥ 3, let θ = 2π/n. Evaluate the determinant of the n × n matrix I + A, where I is the n × n identity matrix and A = (a_{jk}) has entries a_{jk} = cos(jθ + kθ) for all j, k.

Solution: Define ζ = e^{iθ} and v_{m} = (ζ^{m}, ζ^{2m}, …, ζ^{nm}). Note that v_{t} · v_{m} is n if t + m is divisible by n, otherwise 0. Consequently v_{0}, v_{1}, …, v_{n−1} are linearly independent; the dual basis is v_{0}/n, v_{n−1}/n, …, v_{1}/n.

Now Ax = (v_{1}/2)(v_{1} ·x)+(v_{n−1}/2)(v_{n−1} ·x) for any vector x. Indeed, if x = (x_{1}, …, x_{n}) then (2Ax)_{j} = ∑_{k}(ζ^{j+k} + ζ^{−j−k})x_{k} = ζ^{j} ∑_{k} ζ^{k}x_{k} + ζ^{−j} ∑_{k} ζ^{−k}x_{k} = (v_{1})_{j}(v_{1} · x) + (v_{n−1})_{j}(v_{n−1} · x).

Hence Av_{1} = (n/2)v_{n−1}, Av_{n−1} = (n/2)v_{1}, and Av_{m} = 0 if m = 0 or if 2 ≤ m ≤ n − 2.

Thus I + A is similar to the matrix

( \begin{matrix}1 & 0 & 0 & ⋯ & 0 \\ 0 & 1 & 0 & ⋯ & n/2 \\ 0 & 0 & 1 & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 0 & n/2 & 0 & ⋯ & 1 \end{matrix} ) ,

with determinant 1 − (n/2)^{2}.

Problem B6

Let S be a finite set of integers, each greater than 1. Suppose that for each integer n there is some s ∈ S such that gcd(s, n) = 1 or gcd(s, n) = s. Show that there exist s, t ∈ S such that gcd(s, t) is prime. [Here, gcd(a, b) denotes the greatest common divisor of a and b.]

Solution: The following solution is stolen from Thomas Horine.

Define p(t) as the smallest prime dividing t. Define n = lcm {p(t) : t ∈ S}. By hypothesis there is some s ∈ S such that gcd(s, n) = 1 or gcd(s, n) = s. Now p(s) is a common divisor of s and n, so gcd(s, n) = s, i.e., s divides n.

Next define q as the largest prime dividing s. Then q divides n, so q = p(t) for some t ∈ S. Now q divides s exactly once, and divides t; any prime smaller than q does not divide t; any prime larger than q does not divide s. Therefore gcd(s, t) = q.

Comments

A2 is an ancient result, already known to many of the contestants.

In A4 and B3, is one required to prove convergence of the sums? This is straightforward in both cases, but it takes time away from other problems. Contestants should not have to guess how their work will be graded.

In B1, the condition |AC| = 1 should have been stated earlier; otherwise it is nonsense to choose D “so that |AC| = |AD| = 1.” The limit should have been stated for θ → 0^{+}. The diagram supplied on the official competition was visibly inaccurate, with ^{}A̸CB larger than a right angle and ^{}B̸F E larger than ^{}B̸AC; if the question writers were trying to hide the fact that ^{}A̸DC = ^{}B̸DE, they should have left out the diagram entirely.

It isn’t clear what B2 means for n = −∞. The polynomial 0 has “at least two distinct roots,” and it has at least −∞ distinct roots, but it does not have exactly −∞ distinct roots. The writers should have said that n is a nonnegative integer, or said that n is an integer larger than 2, or simply fixed n = 1999.

The solution to B5 can be rephrased without complex numbers: the cosine-sine vectors v_{1} +v_{−1}, (v_{1} −v_{−1})/i, v_{2} +v_{−2}, (v_{2} −v_{−2})/i, … are independent real eigenvectors of I +A having eigenvalues 1 + n/2, 1 − n/2, 1, 1, . . ..

B6 may be rephrased as follows. Let S be a finite collection of nonempty finite sets. Assume that, for every finite set n, S has an element contained in n or disjoint from n. Then there are s, t ∈ S with s ∩ t of size 1. Presumably this result already appears in the combinatorics literature.

—Daniel J. Bernstein, djb@cr.yp.to, 6 December 1999