1998 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

A right circular cone has base of radius 1 and height 3. A cube is inscribed in the cone so that one face of the cube is contained in the base of the cone. What is the side-length of the cube?

Problem A2

Let s be any arc of the unit circle lying entirely in the first quadrant. Let A be the area of the region lying below s and above the x-axis and let B be the area of the region lying to the right of the y-axis and to the left of s. Prove that A + B depends only on the arc length, and not on the position, of s.

Problem A3

Let f be a real function on the real line with continuous third derivative. Prove that there exists a point a such that

f(a) · f′(a) · f′′(a) · f′′′(a) ≥ 0.

Problem A4

Let A_{1} = 0 and A_{2} = 1. For n > 2, the number A_{n} is defined by concatenating the decimal expansions of A_{n−1} and A_{n−2} from left to right. For example A_{3} = A_{2}A_{1} = 10, A_{4} = A_{3}A_{2} = 101, A_{5} = A_{4}A_{3} = 10110, and so forth. Determine all n such that 11 divides A_{n}.

Problem A5

Let F be a finite collection of open discs in R^{2} whose union contains a set E ⊆ R^{2}. Show that there is a pairwise disjoint subcollection D_{1}, …, D_{n} in F such that

⋃_{j=1}^{n} 3D_{j} ⊇ E.

Here, if D is the disc of radius r and center P, then 3D is the disc of radius 3r and center P. Problem A6 Let A, B, C denote distinct points with integer coordinates in R^{2}. Prove that if

(|AB| + |BC|)^{2} < 8 · [ABC] + 1

then A, B, C are three vertices of a square. Here |XY | is the length of segment XY and [ABC] is the area of triangle ABC. Problem B1 Find the minimum value of

\frac{(x + 1/x)^{6} − (x^{6} + 1/x^{6}) − 2}{(x + 1/x)^{3} + (x^{3} + 1/x^{3})}

for x > 0. Problem B2 Given a point (a, b) with 0 < b < a, determine the minimum perimeter of a triangle with one vertex at (a, b), one on the x-axis, and one on the line y = x. You may assume that a triangle of minimum perimeter exists. Problem B3 Let H be the unit hemisphere {(x, y, z) : x^{2} + y^{2} + z^{2} = 1, z ≥ 0}, C the unit circle {(x, y, 0) : x^{2} + y^{2} = 1}, and P a regular pentagon inscribed in C. Determine the surface area of that portion of H lying over the planar region inside P, and write your answer in the form A sin α + B cos β, were A, B, α, and β are real numbers. Problem B4 Find necessary and sufficient conditions on positive integers m and n so that

∑_{i=0}^{mn−1}(−1)^{⌊i/m⌋+⌊i/n⌋} = 0.

Problem B5 Let N be the positive integer with 1998 decimal digits, all of them 1; that is,

N = \underbrace{1111 ⋯ 11}_{1998 digits} .

Find the thousandth digit after the decimal point of \sqrt{N}.

Problem B6

Prove that, for any integers a, b, c, there exists a positive integer n such that

\sqrt{n^{3} + an^{2} + bn + c}

is not an integer.

Unofficial solutions

Problem A1

A right circular cone has base of radius 1 and height 3. A cube is inscribed in the cone so that one face of the cube is contained in the base of the cone. What is the side-length of the cube?

Solution: Let x be the side-length of the cube. The top of the cube is at depth 3 − x from the top of the cone, and it has a diagonal of length x\sqrt{2} touching opposite sides of the cone, so 3 − x = (3/2)x\sqrt{2}, so x = 6/(2 + 3\sqrt{2}).

Problem A2

Let s be any arc of the unit circle lying entirely in the first quadrant. Let A be the area of the region lying below s and above the x-axis and let B be the area of the region lying to the right of the y-axis and to the left of s. Prove that A + B depends only on the arc length, and not on the position, of s.

Solution: Say the arc is from angle α to angle β, with α < β. Then

A + B = ∫_{cos β}^{cos α} y dx + ∫_{sin α}^{sin β} x dy = ∫_{α}^{β} sin^{2} θ dθ + ∫_{α}^{β} cos^{2} θ dθ = ∫_{α}^{β} 1 dθ = β − α.

Alternative solution: A is the area of the circular sector from α to β, plus the area of the triangle (0, 0), (cos α, 0), (cos α, sin α), minus the area of the triangle (0, 0), (cos β, 0), (cos β, sin β); B is the area of the same circular sector, plus the area of the triangle (0, 0), (0, sin β), (cos β, sin β), minus the area of the triangle (0, 0), (0, sin α), (cos α, sin α). Thus A + B is twice the area of the circular sector; the triangle areas cancel.

Problem A3

Let f be a real function on the real line with continuous third derivative. Prove that there exists a point a such that

f(a) · f′(a) · f′′(a) · f′′′(a) ≥ 0.

Solution: If f(0)f′′(0) < 0 or f′(0)f′′′(0) < 0 then, by Lemma 1, there exists a with f(a)f′(a)f′′(a)f′′′(a) = 0. Otherwise f(0)f′(0)f′′(0)f′′′(0) ≥ 0, so take a = 0.

Lemma 1: If g′′ is continuous and g(0)g′′(0) < 0 then there exists a with g(a) = 0 or g′(a) = 0 or g′′(a) = 0. Proof: If g′(0) = 0 then take a = 0. Otherwise define x = −g(0)/g′(0). By the mean value theorem there is some c between 0 and x for which g′(c)x = g(x)−g(0), and there is some b between 0 and c for which g′′(b)c = g′(c)−g′(0). Thus g′′(b)cx = g′(c)x − g′(0)x = g(x) − g(0) + g(0) = g(x). If g′′(0)g′′(b) ≤ 0 then by the intermediate value theorem g′′ has a root; otherwise g(0)g′′(b) < 0 so g(0)g(x) = g(0)g′′(b)cx < 0 so by the intermediate value theorem g has a root.

Problem A4

Let A_{1} = 0 and A_{2} = 1. For n > 2, the number A_{n} is defined by concatenating the decimal expansions of A_{n−1} and A_{n−2} from left to right. For example A_{3} = A_{2}A_{1} = 10, A_{4} = A_{3}A_{2} = 101, A_{5} = A_{4}A_{3} = 10110, and so forth. Determine all n such that 11 divides A_{n}.

Solution: Define d_{n} as the number of digits in A_{n}. Then d_{1} = 1, d_{2} = 1, and d_{n} = d_{n−1} + d_{n−2} for n ≥ 3. By induction d_{n} mod 2 is 0, 1, 1 when n mod 3 is 0, 1, 2.

Now A_{n} = 10^{d_{n−2}}A_{n−1} + A_{n−2} for n ≥ 3, so A_{n} ≡ (−1)^{d_{n−2}}A_{n−1} + A_{n−2} (mod 11). By induction A_{n} mod 11 is 1, 0, 1, 10, 2, 1 when n mod 6 is 0, 1, 2, 3, 4, 5.

Thus A_{n} is divisible by 11 if and only if n mod 6 = 1.

Problem A5

Let F be a finite collection of open discs in R^{2} whose union contains a set E ⊆ R^{2}. Show that there is a pairwise disjoint subcollection D_{1}, …, D_{n} in F such that

⋃_{j=1}^{n} 3D_{j} ⊇ E.

Here, if D is the disc of radius r and center P, then 3D is the disc of radius 3r and center P.

Solution: Select D_{1} ∈ F of maximal radius. Select D_{2} ∈ F, not intersecting D_{1}, of maximal radius. Select D_{3} ∈ F, not intersecting D_{1} or D_{2}, of maximal radius. Continue until every disc in F intersects one of D_{1}, D_{2}, …, D_{n}.

For any point x ∈ E there is a disc C ∈ F with x ∈ C. Find the smallest integer k ≥ 1 such that C intersects D_{k}. Then C does not intersect D_{1}, D_{2}, …, D_{k−1}; by construction of D_{k}, the radius of C is at most the radius of D_{k}. The distance from x to the center of D_{k} is less than twice the radius of C plus the radius of D_{k}, hence less than three times the radius of D_{k}; so x ∈ 3D_{k} ⊆ 3D_{1} ∪ 3D_{2} ∪ ⋯ ∪ 3D_{n} as desired.

Problem A6

Let A, B, C denote distinct points with integer coordinates in R^{2}. Prove that if

(|AB| + |BC|)^{2} < 8 · [ABC] + 1

then A, B, C are three vertices of a square. Here |XY | is the length of segment XY and [ABC] is the area of triangle ABC.

Solution: Define x = |AB| and y = |BC|, and let T be the area of the triangle. Then 2T ≤ xy so x^{2} + y^{2} + 4T ≤ (x + y)^{2} < 8T + 1 so x^{2} + y^{2} < 4T + 1. Both x^{2} + y^{2} and 4T are integers, so x^{2} + y^{2} ≤ 4T, so 0 ≤ (x − y)^{2} ≤ 4T − 2xy ≤ 0. Thus 2T = xy and x = y.

Problem B1

Find the minimum value of

\frac{(x + 1/x)^{6} − (x^{6} + 1/x^{6}) − 2}{(x + 1/x)^{3} + (x^{3} + 1/x^{3})}

for x > 0.

Solution: The ratio is 3(x + 1/x), so its minimum value is 6.

Problem B2

Given a point (a, b) with 0 < b < a, determine the minimum perimeter of a triangle with one vertex at (a, b), one on the x-axis, and one on the line y = x. You may assume that a triangle of minimum perimeter exists.

Solution: (Thanks to Martin Tangora for pointing out this solution to me.) The perimeter of the triangle (a, b), (d, d), (c, 0) equals the sum of distances from (b, a) to (d, d) to (c, 0) to (a, −b), which is at least the distance from (b, a) to (a, −b), namely \sqrt{2a^{2} + 2b^{2}}. This bound can be achieved: the line segment from (b, a) to (a, −b) intersects the lines y = x and y = 0 by the hypotheses on a and b.

Problem B3

Let H be the unit hemisphere {(x, y, z) : x^{2} + y^{2} + z^{2} = 1, z ≥ 0}, C the unit circle {(x, y, 0) : x^{2} + y^{2} = 1}, and P a regular pentagon inscribed in C. Determine the surface area of that portion of H lying over the planar region inside P, and write your answer in the form A sin α + B cos β, were A, B, α, and β are real numbers.

Solution: The surface area of the hemisphere is 2π. The portion not over the pentagon consists of five copies of the surface obtained by rotating {(cos θ, sin θ) : 0 ≤ θ ≤ π/5} halfway around the x-axis. That surface has area π ∫_{0}^{π/5}(sin θ)\sqrt{sin^{2} θ + cos^{2} θ} dθ = π(1 − cos(π/5)), so the answer is 5π cos(π/5) − 3π. One solution in the stated form is (A, α, B, β) = (−3π, π/2, 5π, π/5).

Problem B4 Find necessary and sufficient conditions on positive integers m and n so that

∑_{i=0}^{mn−1}(−1)^{⌊i/m⌋+⌊i/n⌋} = 0.

Solution: Define S(m, n) = ∑_{0≤i<mn}(−1)^{⌊i/m⌋+⌊i/n⌋}. Write ord_{2} t for the number of powers of 2 dividing t. If ord_{2} m = ord_{2} n then S(m, n) ≠ 0. Indeed, write m = 2^{e}u and n = 2^{e}v, with u and v odd. Then S(u, v) has an odd number of odd terms, so it is nonzero; and S(m, n) = 2^{2e}S(u, v) by Lemma 1. If ord_{2} m ≠ ord_{2} n then S(m, n) = 0. Indeed, write m = 2^{d}x and n = 2^{e}v, with x and v odd; without loss of generality assume d > e. Write u = 2^{d−e}x, and substitute i = uv − 1 − j in S(u, v):

S(u, v) = ∑_{0≤j<uv}(−1)^{⌊(uv−1−j)/u⌋+⌊(uv−1−j)/v⌋}

= ∑_{0≤j<uv}(−1)^{u−1+v−1−⌊j/u⌋−⌊j/v⌋}

= ∑_{0≤j<uv}(−1)^{1+⌊j/u⌋+⌊j/v⌋} = −S(u, v).

Thus S(u, v) = 0; and S(m, n) is a multiple of S(u, v) by Lemma 1. Lemma 1. S(bu, bv) is a multiple of S(u, v); if u + v is even then S(bu, bv) = b^{2}S(u, v). Proof: Write i = buvq + br + s, with 0 ≤ r < uv and 0 ≤ s < b. Then

S(bu, bv) = ∑_{0≤q<b} ∑_{0≤r<uv} ∑_{0≤s<b}(−1)^{⌊(buvq+br+s)/bu⌋+⌊(buvq+br+s)/bv⌋}

= ∑_{0≤q<b} ∑_{0≤r<uv} ∑_{0≤s<b}(−1)^{(u+v)q+⌊r/u⌋+⌊r/v⌋}

= bS(u, v) ∑_{0≤q<b}(−1)^{(u+v)q}.

If u + v is even then ∑_{0≤q<b}(−1)^{(u+v)q} = b. Problem B5 Let N be the positive integer with 1998 decimal digits, all of them 1; that is,

N = \underbrace{1111 ⋯ 11}_{1998 digits} .

Find the thousandth digit after the decimal point of \sqrt{N}. Solution: The answer is 1. More generally, for any positive integer h, write N = (10^{2h} − 1)/9. By Lemma 1,

10^{h+1}\sqrt{N} = 10^{2h+1}\sqrt{1 − 10^{−2h}}/3
= 10^{2h+1}(1 − 10^{−2h}/2 − 10^{−4h}x/4)/3
= 10^{2h+1}/3 − 10/6 − 10^{1−2h}x/12
= (10^{2h+1} − 10)/3 + 1 + 2/3 − 10^{1−2h}x/12

for some x between 0 and 1. Now 0 < 2/3 − 10^{1−2h}x/12 < 1, and (10^{2h+1} − 10)/3 is a multiple of 10, so ⌊10^{h+1}\sqrt{N}⌋ mod 10 = 1. For example, \sqrt{11} ≈ 3.3166, and \sqrt{1111} ≈ 33.3316666. Lemma 1. If 0 < d < 1/2 then 1 − d/2 − d^{2}/4 < \sqrt{1 − d} < 1 − d/2. Proof: d + d^{2}/4 < 1 so (1 − d/2 − d^{2}/4)^{2} = 1 − d − (1 − d − d^{2}/4)d^{2}/4 < 1 − d < 1 − d + d^{2}/4 = (1 − d/2)^{2}. Problem B6 Prove that, for any integers a, b, c, there exists a positive integer n such that

\sqrt{n^{3} + an^{2} + bn + c}

is not an integer. Solution: Write f(n) = n^{3} + an^{2} + bn + c. Find an integer m large enough that 8m^{3} exceeds both (a^{2} − 4b)m^{2} − am − c + 1/4 and (4b − a^{2})m^{2} − am + c − 1/4. Then

(8m^{3} + am − 1/2)^{2} < f(4m^{2}) < (8m^{3} + am + 1/2)^{2},

so if f(4m^{2}) is a square then f(4m^{2}) = (8m^{3} + am)^{2}, i.e., (a^{2} − 4b)m^{2} = c. This cannot hold for more than one value of m unless 4b = a^{2} and c = 0. But then f(n) = n(n+a/2)^{2}; this is not a square if n is a non-square different from −a/2.

Comments

In A1, is one required to prove that the 6/(2 + 3\sqrt{2}) cube fits inside the cone, and that larger cubes do not? In A2, can one assume that the arc length from (cos α, sin α) to (cos β, sin β) is β −α? In A6, can one take “parallelogram with equal sides and with area equal to product of sides” as the definition of a square? In B3, can one use standard facts about areas of portions of a sphere? Contestants should not have to guess how their work will be graded.

The form of answer for B3—“A sin α+B cos β, where A, B, α, and β are real numbers”— was rather strange. Did the question writers mean to say “Aπ + Bπ cos(Cπ), where A, B, C are rational numbers”?

There are many solutions to B6; what makes the problem difficult is the weakness of its conclusion. Here is a very fast proof by Brian R. Hunt: f(4k + b + 1) − f(4k + b − 1) ≡ 2 (mod 4) so it is not possible for both f(4k + b + 1) mod 4 and f(4k + b − 1) mod 4 to be in {0, 1}.

—Daniel J. Bernstein, djb@cr.yp.to, 7 December 1998