Putnam 1998 (Problems and Solutions)

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. Consider the cross section obtained by slicing vertically by a plane
that contains a diagonal of the base of the
√ cube. We obtain a rectangle of height
s = side-length of the cube and width 2s. By similar triangles
3 s
= 1
√ ⇒
1 1− 2 2s
¡ √ ¢ √
6 6 3 2−2 9 2−6
s = √ =¡ √ ¢¡ √ ¢= .
3 2+2 3 2+2 3 2−2 7

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 of s and not on the position of s.

Solution. Let s run from θ 1 to θ2 . Then

Z cos θ1 p Z θ1
A = 1 − x2 dx = − sin2 θ dθ
cos θ2 θ2
Z sin θ2 p Z θ2
B = 2
1 − y dy = cos2 θ dθ
sin θ1 θ1

Note that
∂
∂θ 1 (A + B) = − sin2 θ 1 − cos2 θ1 = −1 ⇒ A + B = −θ1 + f (θ2 )

while
∂
∂θ2 (A + B) = sin2 θ2 + cos2 θ2 = 1 ⇒ A + B = θ 2 + g (θ1 ) .

Hence, since A + B = 0 when θ 1 = θ2 ,

A + B = θ2 − θ1 + C = θ2 − θ1 .

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 0 (a) · f 00 (a) · f 000 (a) ≥ 0.

1
Solution. Assume otherwise. Then
f (x) · f 0 (x) · f 00 (x) · f 000 (x) < 0.
In particular, each of the factors is never zero. By replacing f (x) by −f (x) if
necessary, we may assume that f (x) > 0, and by replacing f (x) by f (−x) if
necessary, we may assume that f 0 (x) > 0. There are two cases:
Case 1: f 00 (x) > 0 and f 000 (x) < 0.
Since f 000 (x) < 0, the graph of f 0 (x) is concave down and hence the graph
of f 0 (x) lies below its tangent line at x = 0. Thus,
µ 0 ¶
−f (0)
f 0 (x) ≤ f 0 (0) + f 00 (0) x and f 0 ≤ 0 (contradiction).
f 00 (0)
Case 2: f 00 (x) < 0 and f 000 (x) > 0.
Since f 00 (x) < 0, the graph of f (x) is concave down and hence the graph of
f (x) lies below its tangent line at x = 0. Thus,
µ ¶
−f (0)
f (x) ≤ f (0) + f 0 (0) x and f ≤ 0 (contradiction).
f 0 (0)

A4. Let A1 = 0 and let A2 = 1. For n > 2, the number An is defined by

concatenating the decimal expansions of An−1 and An−2 from left to right. For
example A3 = A2 A1 = 10, A4 = A3 A2 = 101, A5 = A4 A3 = 10110, and so
forth. Determine all n such that 11 divides An .
n
Solution. Since 10n ≡ (−1) mod 11, an integer is divisible by 11 iff the alter-
nating sum of its digits (from right to left so that the first term is positive) is 0
mod 11. Let en be the alternating sum of the digits mod 11 of An from right to
left, and let Fn be the number digits in An . Of course Fn is just the Fibonacci
F
sequence. Note that en+2 = (−1) n en+1 + en . We have Fn+2 = Fn+1 + Fn and
F1 = 1, and F2 = 1, we see that Fn is even iff n is divisible by 3. We have (all
mod 11)

en+2 = (−1)Fn en+1 + en

e3k+3 = (−1)F3k+1 e3k+2 + e3k+1 = −e3k+2 + e3k+1
e3k+4 = (−1)F3k+2 e3k+3 + e3k+2 = −e3k+3 + e3k+2 = − (−e3k+2 + e3k+1 ) + e3k+2
= −e3k+1 + 2e3k+2
e3k+5 = (−1)F3k+3 e3k+4 + e3k+3 = e3k+4 + e3k+3 = (−e3k+1 + 2e3k+2 ) + (−e3k+2 + e3k+1 )
= e3k+2
e3k+6 = (−1)F3k+4 e3k+5 + e3k+4 = −e3k+5 + e3k+4 = −e3k+2 + (−e3k+1 + 2e3k+2 )
= e3k+2 − e3k+1
e3k+7 = (−1)F3k+5 e3k+6 + e3k+5 = −e3k+6 + e3k+5 = − (e3k+2 − e3k+1 ) + e3k+2 = e3k+1
e3k+8 = (−1)F3k+6 e3k+7 + e3k+6 = e3k+7 + e3k+6 = e3k+1 + e3k+2 − e3k+1 = e3k+2
e3k+9 = (−1)F3k+7 e3k+8 + e3k+7 = −e3k+8 + e3k+7 = −e3k+2 + e3k+1 = e3k+3

2
Thus, en is periodic of period 6. Now
e1 = 0, e2 = 1, e3 = −e2 + e1 = −1,
e4 = −e1 + 2e2 = 2, e5 = e2 = 1, e6 = e2 − e1 = 1.
Thus, en is divisible by 11 iff n ≡ 1 mod 6.

A5. Let F be a finite collection of open disks in R2 whose union contains a

set E ⊆ R2 . Prove that there is a pairwise disjoint collection D1 , ..., Dn in F
such that
[n
3Dj ⊇ E.
j=1

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

Solution. Note that if D and D0 are open disks of radius r and r0 , with r ≤ r0 ,
then D ∩ D0 6= φ ⇒ 3D0 ⊇ D. Starting with a largest disk, color it (say, red),
and remove the disks which intersect it. The 3-fold enlargement of the colored
disk together with the remaining disks will still cover E, by the above. Then
color a largest remaining uncolored disk, and remove the remaining uncolored
disks which intersect it. Continuing, the process eventually stops, since there
are a finite number of disks. Moreover, at each stage the 3-fold enlargements of
the colored disks and the remaining uncolored disks cover E. At the end of the
process, no uncolored disks remain, and the 3-fold enlargements of the colored
disks cover E. The colored disks are pairwise disjoint by construction.

A6. Let A, B and C denote distinct points with integer coordinates in R2 .

Prove that if
2
(|AB| + |BC|) < 8 · [ABC] + 1
then A, B, C are three vertices of a square. Here |XY | is the length of the
segment XY and [ABC] is the area of triangle ABC.

Solution. We have [ABC] = 12 |AB| |BC| sin θ, where θ is the angle of triangle
ABC at vertex B. Thus, 4 · [ABC] ≤ 2 |AB| |BC| with equality only if θ = 90◦ .
Also 2 |AB| |BC| ≤ |AB|2 + |BC|2 with equality only if |AB| = |BC|, since
2
0 ≤ (|AB| − |BC|) . Hence,
8 · [ABC] ≤ 4 · [ABC] + 2 |AB| |BC|
≤ 4 · [ABC] + |AB|2 + |BC|2
≤ 2 |AB| |BC| + |AB|2 + |BC|2
= (|AB| + |BC|)2 < 8 · [ABC] + 1
2 2
The intermediate expression 4 · [ABC] + |AB| + |BC| is an integer, since
2 · [ABC] is a determinant of a 2 × 2 matrix with integer coefficients. Thus, we
have all equalities, and θ = 90◦ and |AB| = |BC| .

3
B1. Find the minimum value of
6 ¡ ¢
(x + 1/x) − x6 + 1/x6 − 2
(x + 1/x)3 + (x3 + 1/x3 )

Solution. We have
¡ ¢ ¡ ¢2
(x + 1/x)6 − x6 + 1/x6 − 2 6
(x + 1/x) − x3 + 1/x3
=
(x + 1/x)3 + (x3 + 1/x3 ) (x + 1/x)3 + (x3 + 1/x3 )
³ ¡ ¢´ ³ ¡ ¢´
(x + 1/x)3 − x3 + 1/x3 3
(x + 1/x) + x3 + 1/x3
=
(x + 1/x)3 + (x3 + 1/x3 )
¡ ¢
= (x + 1/x)3 − x3 + 1/x3
= 3 (x + 1/x)

d x2 − 1
dx (x + 1/x) = = 0, x > 0 ⇒ x = 1.
x2
As x + 1/x approaches ∞ as x → +∞ and x → 0+ , there is a minimum and
the only candidate is x = 1. The minimum value is 3 (1 + 1/1) = 6.

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 with minimum perimeter exists.

Solution. Note that the distance of any point (d, d) on the line y = x to the
point (a, b) is the same as the distance of (d, d) to (b, a) , the reflection of (a, b)
in the line y = x. Also, the distance of any point (c, 0) to (a, b) is the same
as the distance of (c, 0) to (a, −b) , the reflection of (a, b) in the x-axis. Thus,
the perimeter of the triangle (d, d) , (a, b) , (c, 0) is the same as the broken line
segment with vertices (a, −b) , (c, 0) , (d, d) , (b, a). The length of this broken
line segment is no qgreater than the distance between the endpoints (b, a) and
2 2 p
(a, −b) , namely (b − a) + (a + b) = 2 (a2 + b2 ). We can choose c and
d
pso that the broken segment (a, −b) , (c, 0) , (d, d) , (b, a) is straight. Thus,
2 (a2 + b2 ) is the minimum possible perimeter.

B3. Let H be the unit hemisphere {(x, y, z) : x2 + y 2 + z 2 = 1, z ≥ 0}, C the

unit circle {(x, y, 0) : x2 + y2 = 1}, and P the 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 β, where A, B, α, β
are real numbers.

4
Solution. The desired area A is 12 the area of the sphere minus 5 polar caps
that each extends an angle of π5 from its pole. Thus,
à Z 2π Z π5 !
1
A = 4π − 5 sin ϕ dϕdθ
2 0 0
³ π ´
= 2π − 5 · π − cos + 1
5
π π π
= −3π + 5π cos = −3π sin + 5π cos .
5 2 5

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

that
mn−1
X
(−1)bi/mc+bi/nc = 0.
i=0

Solution. The number of terms in the sum is mn which is odd if both m and
n are odd. Thus, the sum (consisting of 1s and −1s) cannot be zero if both m
and n are odd. Suppose that m + n is odd (e.g., m is even and n is odd). In
this case we claim

(bi/mc + bi/nc) + (b(mn − 1 − i) /mc + b(mn − 1 − i) /nc) = m + n − 2 (1)

which is odd, so that for 0 ≤ i ≤ 12 mn, the i-th term and the (mn − 1 − i)-th
term cancel in the sum which is then 0. Note that

bi/mc + b(mn − 1 − i) /mc = bi/mc + bn − (1 + i) /mc

= n + bi/mc + b− (1 + i) /mc
= n + (bi/mc + b−i/m − 1/mc)
= n − 1, (2)

and similarly

bi/nc + b(mn − 1 − i) /nc = m − 1. (3)

Adding (2) and (3), we get (1). Suppose that m and n are both even, say
m = 2m0 and n = 2n0 . Then, for any positive integer i,
¹ º ¹ º ¹ º ¹ º ¹ º ¹ º
2i 2i 2i + 1 2i 2i 2i + 1
= = and = = .
m 2m0 2m0 n 2n0 2n0

5
Thus the sum, say S (m, n), is given by twice the sum over even indices:
1
mn−1
X 2 mn−1
X 0 0
S (m, n) = (−1)bi/mc+bi/nc = 2 (−1)b2i /mc+b2i /nc
i=0 i0 =0
1
2 mn−1
0 0
X 2mXn −1
bi0 /m0 c+bi0 /n0 c 0 0 0 0
= 2 (−1) =2 (−1)bi /m c+bi /n c
i0 =0 i0 =0
0 0 0 0
n −1
mX 2mXn −1
bi0 /m0 c+bi0 /n0 c 0 0 0 0
= 2 (−1) +2 (−1)bi /m c+bi /n c
i0 =0 i0 =m0 n0
0 0
n −1
mX
0 0 0 0 0 0 0 0
= 2S (m0 , n0 ) + 2 (−1)b(i +m n )/m c+b(i +m n )/n c
i0 =0
³ 0 0
´
0 0
= 2S (m , n ) 1 + (−1)n +m .
0 0
Now, if 1 + (−1)n +m = 0 ⇔ n0 + m0 is odd, in which case S (m0 , n0 ) = 0 and
S (m, n) = 0. Thus, S (m, n) = 0 ⇔ S (m0 , n0 ) = 0 ⇔ ... ⇔ the highest power
of 2 which divides m differs from the highest power of 2 which divides n.

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

N = 1111 · · · 11.
√
Find the thousandth digit after the decimal point of N.

Solution. Note that 9N = 1111 · · · 11 = 101998 − 1. Thus,

r
√ 101998 − 1 p p
N = = 13 101998 − 1 = 13 10999 1 − 10−1998
9
¡ ¢1
= 13 10999 1 − 10−1998 2

We have the binomial series

1
¡1 ¢ 1
¡1 ¢¡ ¢
1
1 2 2 −1 2 2 2 − 1 12 − 2 3
(1 − x) 2 =1− 2x + x − x +···
2! 3!
1
valid for |x| < 1. The remainder term in (1 − x) 2 = 1 − 12 x + R2 (x) satisfies
¯ µ ¶¯ ¯ ¯ 2
¯ d2 1 ¯ x2 ¯1 ¡1 ¢ − 2 ¯¯ x
3
|R2 (x)| ≤ max ¯¯ dt (1 − t) 2 ¯
¯ 2! = max ¯ − 1 (1 − t)
0≤t≤x ¯ 2 2 ¯ 2!
2
0≤t≤x
¯ ¯ 2
¯ − ¯ x
3
= ¯¯ 14 (1 − x) 2 ¯¯
2!

6
 3
−
For x = 10−1998 , (1 − x) 2 ≤ 2 and so |R2 (x)| ≤ 14 x2 ≤ 14 10−2·1998 . Thus,
¯√ ¯ ¯
¯ ¡ ¢¯¯ 1 999 ¯ 1 ¡ ¢¯
1
¯ N − 3 10 999
1 − 2 x ¯ = 3 10 ¯(1 − x) 2 − 1 − 2 x ¯¯
1 ¯ 1

999 1 2 999−2·1998
≤ 1
3 10 4x ≤ 1
12 10 = 10−2998 .
Now
999
¡ ¢ 999
¡ ¢
1
3 10 1 − 12 x = 1
3 10 1 − 12 10−1998 = 13 10999 − 16 10−999
= .33 × 10999 − .166 × 10−999
999 999 ¡ ¢
= 3· · ·3.3· · ·3 + .333 − .166 × 10−999
999 999
= 3· · ·3.3· · ·3 + .166 × 10−999
999 999
= 3· · ·3.3· · ·3166.
Thus, the 1000-th digit to the right of the decimal is 1.
B6. √Prove that, for any integers a, b, c, there exists a positive integer n such
that n3 + an2 + bn + c is not an integer.
Solution. We try to write the assumed perfect square n3 + an2 + bn + c in the
¡ ¢2
form n3/2 + dn1/2 + f :
³ ´2
n3 + an2 + bn + c = n3/2 + d n1/2 + f
¡√ ¢3 √
= n3 + 2n2 d + 2 n f + nd2 + 2d nf + f 2 .
Choosing d = 12 a, and f = ±1, we then have, for n sufficiently large,
³ ´2 ³ ´2
n3/2 + 12 a n1/2 − 1 < n3 + an2 + bn + c < n3/2 + 12 a n1/2 + 1 .

If n is a perfect square, say n = m2 , then the extreme left and right are
perfect squares and there is only one perfect square between them, namely
¡ 3/2 1 ¢2
n + 2 a n1/2 . Hence, if n = m2 and n3 + an2 + bn + c is a perfect square,
then
³ ´2
n3 + an2 + bn + c = n3/2 + 12 a n1/2 = n3 + a n2 + 14 a2 n.
or
m6 + am4 + bm2 + c = m6 + a m4 + 14 a2 m2
or
bm2 + c = 14 a2 m2
For this to hold for all sufficiently large integers m, we must have c = 0 and
b = 14 a2 . Thus,
³ ´2 ³√ ³ a ´´2
n3 + an2 + bn + c = n3/2 + 12 a n1/2 = n n+ ,
2
which is not a perfect square, unless n is a perfect square.