Contents

Introduction vii
1 Structure of this book . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
2 The Putnam Competition over the years . . . . . . . . . . . . . . . . . viii
3 Advice to the student reader . . . . . . . . . . . . . . . . . . . . . . . ix
4 Scoring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x
5 Some basic notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi
6 Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi

Problems 1

Hints 35

Solutions 51
The Forty-Sixth Competition (1985) . . . . . . . . . . . . . . . . . . . . . . 53
The Forty-Seventh Competition (1986) . . . . . . . . . . . . . . . . . . . . . 65
The Forty-Eighth Competition (1987) . . . . . . . . . . . . . . . . . . . . . 76
The Forty-Ninth Competition (1988) . . . . . . . . . . . . . . . . . . . . . . 88
The Fiftieth Competition (1989) . . . . . . . . . . . . . . . . . . . . . . . . 101
The Fifty-First Competition (1990) . . . . . . . . . . . . . . . . . . . . . . . 116
The Fifty-Second Competition (1991) . . . . . . . . . . . . . . . . . . . . . 135
The Fifty-Third Competition (1992) . . . . . . . . . . . . . . . . . . . . . . 154
The Fifty-Fourth Competition (1993) . . . . . . . . . . . . . . . . . . . . . 171
The Fifty-Fifth Competition (1994) . . . . . . . . . . . . . . . . . . . . . . 191
The Fifty-Sixth Competition (1995) . . . . . . . . . . . . . . . . . . . . . . 204
The Fifty-Seventh Competition (1996) . . . . . . . . . . . . . . . . . . . . . 217
The Fifty-Eighth Competition (1997) . . . . . . . . . . . . . . . . . . . . . . 232
The Fifty-Ninth Competition (1998) . . . . . . . . . . . . . . . . . . . . . . 250
The Sixtieth Competition (1999) . . . . . . . . . . . . . . . . . . . . . . . . 262
The Sixty-First Competition (2000) . . . . . . . . . . . . . . . . . . . . . . 278

Results 295
Individual Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
Team Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
xiii
xiv The William Lowell Putnam Mathematical Competition

Putnam Trivia for the Nineties

by Joseph A. Gallian 307
Answers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321

Some Thoughts on Writing for the Putnam

by Bruce Reznick 311

Bibliography 323

Index 333

About the Authors 337

 Problems

The Forty-Sixth William Lowell Putnam Mathematical Competition

December 7, 1985
Questions Committee: Bruce Reznick, Richard P. Stanley, and Harold M. Stark
See page 35 for hints.

A1. Determine, with proof, the number of ordered triples (A1 , A2 , A3 ) of sets which
have the property that
(i) A1 ∪ A2 ∪ A3 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, and
(ii) A1 ∩ A2 ∩ A3 = ∅,
where ∅ denotes the empty set. Express the answer in the form 2a 3b 5c 7d , where a, b,
c, and d are nonnegative integers. (page 53)

A2. Let T be an acute triangle. Inscribe a pair R, S of rectangles in T as shown:

❏
❏
❏
S ❏
❏
❏
R ❏
❏
❏
Let A(X) denote the area of polygon X. Find the maximum value, or show that no
maximum exists, of A(R)+A(S)
A(T ) , where T ranges over all triangles and R, S over all
rectangles as above. (page 54)

A3. Let d be a real number. For each integer m ≥ 0, define a sequence {am (j)},
j = 0, 1, 2, . . . by the condition

am (0) = d/2m , and am (j + 1) = (am (j))2 + 2am (j), j ≥ 0.

Evaluate limn→∞ an (n). (page 56)

A4. Define a sequence {ai } by a1 = 3 and ai+1 = 3ai for i ≥ 1. Which integers
between 00 and 99 inclusive occur as the last two digits in the decimal expansion of
infinitely many ai ? (page 57)
1
2 The William Lowell Putnam Mathematical Competition

 2π
A5. Let Im = 0
cos(x) cos(2x) · · · cos(mx) dx. For which integers m, 1 ≤ m ≤ 10,
is Im = 0? (page 58)

A6. If p(x) = a0 + a1 x + · · · + am xm is a polynomial with real coefficients ai , then

set
Γ(p(x)) = a20 + a21 + · · · + a2m .

Let f (x) = 3x2 + 7x + 2. Find, with proof, a polynomial g(x) with real coefficients
such that
(i) g(0) = 1, and
(ii) Γ(f (x)n ) = Γ(g(x)n )
for every integer n ≥ 1. (page 59)

B1. Let k be the smallest positive integer with the following property:
There are distinct integers m1 , m2 , m3 , m4 , m5 such that the polynomial

p(x) = (x − m1 )(x − m2 )(x − m3 )(x − m4 )(x − m5 )

has exactly k nonzero coefficients.

Find, with proof, a set of integers m1 , m2 , m3 , m4 , m5 for which this minimum k is
achieved. (page 60)

B2. Define polynomials fn (x) for n ≥ 0 by f0 (x) = 1, fn (0) = 0 for n ≥ 1, and

d
(fn+1 (x)) = (n + 1)fn (x + 1)
dx
for n ≥ 0. Find, with proof, the explicit factorization of f100 (1) into powers of distinct
primes. (page 61)

B3. Let
a1,1 a1,2 a1,3 . . .
a2,1 a2,2 a2,3 . . .
a3,1 a3,2 a3,3 . . .
.. .. .. ..
. . . .
be a doubly infinite array of positive integers, and suppose each positive integer
appears exactly eight times in the array. Prove that am,n > mn for some pair of
positive integers (m, n). (page 61)

B4. Let C be the unit circle x2 + y 2 = 1. A point p is chosen randomly on the

circumference of C and another point q is chosen randomly from the interior of C
(these points are chosen independently and uniformly over their domains). Let R be
the rectangle with sides parallel to the x- and y-axes with diagonal pq. What is the
probability that no point of R lies outside of C? (page 62)
∞ −1 ∞ 2 √
B5. Evaluate 0
t−1/2 e−1985(t+t )
dt. You may assume that −∞
e−x dx = π.
(page 62)
Problems: The Forty-Sixth Competition (1985) 3

B6. Let G be a finite set of real n × n matrices


{Mi }, 1 ≤ i ≤ r, which form a group
r
under matrix multiplication. Suppose that i=1 tr(Mi ) = 0, where tr(A) denotes the
r
trace of the matrix A. Prove that i=1 Mi is the n × n zero matrix. (page 63)
4 The William Lowell Putnam Mathematical Competition

The Forty-Seventh William Lowell Putnam Mathematical Competition

December 6, 1986
Questions Committee: Richard P. Stanley,
Harold M. Stark, and Abraham P. Hillman
See page 36 for hints.

A1. Find, with explanation, the maximum value of f (x) = x3 − 3x on the set of all
real numbers x satisfying x4 + 36 ≤ 13x2 . (page 65)
 
1020000
A2. What is the units (i.e., rightmost) digit of 10100 +3 ? Here x is the greatest
integer ≤ x. (page 65)
∞
A3. Evaluate n=0Arccot(n2 + n+ 1), where Arccot t for t ≥ 0 denotes the number
θ in the interval 0 < θ ≤ π/2 with cot θ = t. (page 65)

A4. A transversal of an n×n matrix A consists of n entries of A, no two in the same

row or column. Let f (n) be the number of n × n matrices A satisfying the following
two conditions:
(a) Each entry αi,j of A is in the set {−1, 0, 1}.
(b) The sum of the n entries of a transversal is the same for all transversals of A.
An example of such a matrix A is
 
−1 0 −1
A =  0 1 0 .
0 1 0
Determine with proof a formula for f (n) of the form
f (n) = a1 bn1 + a2 bn2 + a3 bn3 + a4 ,
where the ai ’s and bi ’s are rational numbers. (page 67)

A5. Suppose f1 (x), f2 (x), . . . , fn (x) are functions of n real variables x = (x1 , . . . , xn )
with continuous second-order partial derivatives everywhere on Rn . Suppose further
that there are constants cij such that
∂fi ∂fj
− = cij
∂xj ∂xi
for all i and j, 1 ≤ i ≤ n, 1 ≤ j ≤ n. Prove that there is a function g(x) on Rn such
that fi + ∂g/∂xi is linear for all i, 1 ≤ i ≤ n. (A linear function is one of the form
a0 + a1 x1 + a2 x2 + · · · + an xn .)
(page 68)

A6. Let a1 , a2 , . . . , an be real numbers, and let b1 , b2 , . . . , bn be distinct positive

integers. Suppose there is a polynomial f (x) satisfying the identity
n
(1 − x)n f (x) = 1 + ai xbi .
i=1
Problems: The Forty-Seventh Competition (1986) 5

Find a simple expression (not involving any sums) for f (1) in terms of b1 , b2 , . . . , bn
and n (but independent of a1 , a2 , . . . , an ). (page 69)

B1. Inscribe a rectangle of base b and height h and an isosceles triangle of base b
in a circle of radius one as shown. For what value of h do the rectangle and triangle
have the same area?

(page 70)

B2. Prove that there are only a finite number of possibilities for the ordered triple
T = (x − y, y − z, z − x), where x, y, and z are complex numbers satisfying the
simultaneous equations
x(x − 1) + 2yz = y(y − 1) + 2zx = z(z − 1) + 2xy,
and list all such triples T . (page 71)

B3. Let Γ consist of all polynomials in x with integer coefficients. For f and g in
Γ and m a positive integer, let f ≡ g (mod m) mean that every coefficient of f − g
is an integral multiple of m. Let n and p be positive integers with p prime. Given
that f , g, h, r, and s are in Γ with rf + sg ≡ 1 (mod p) and f g ≡ h (mod p), prove
that there exist F and G in Γ with F ≡ f (mod p), G ≡ g (mod p), and F G ≡ h
(mod pn ). (page 71)
√
B4. For a positive real number r, let G(r) be the minimum value of r − m2 + 2n2
for all integers m and n. Prove or disprove the assertion that limr→∞ G(r) exists and
equals 0. (page 72)

B5. Let f (x, y, z) = x2 + y 2 + z 2 + xyz. Let p(x, y, z), q(x, y, z), r(x, y, z) be
polynomials with real coefficients satisfying
f (p(x, y, z), q(x, y, z), r(x, y, z)) = f (x, y, z).
Prove or disprove the assertion that the sequence p, q, r consists of some permutation
of ±x, ±y, ±z, where the number of minus signs is 0 or 2. (page 73)

B6. Suppose A, B, C, D are n × n matrices with entries in a field F , satisfying the

conditions that AB t and CDt are symmetric and ADt − BC t = I. Here I is the n × n
identity matrix, and if M is an n × n matrix, M t is the transpose of M . Prove that
At D − C t B = I. (page 74)
6 The William Lowell Putnam Mathematical Competition

The Forty-Eighth William Lowell Putnam Mathematical Competition

December 5, 1987
Questions Committee: Harold M. Stark, Abraham P. Hillman, and Gerald A. Heuer
See page 37 for hints.

A1. Curves A, B, C, and D are defined in the plane as follows:†


x
A= (x, y) : x − y = 2
2 2
,
x + y2

y
B= (x, y) : 2xy + =3 ,
x2 + y 2
 
C= (x, y) : x3 − 3xy 2 + 3y = 1 ,
 
D = (x, y) : 3x2 y − 3x − y 3 = 0 .
Prove that A ∩ B = C ∩ D. (page 76)

A2. The sequence of digits

123456789101112131415161718192021 . . .
is obtained by writing the positive integers in order. If the 10n th digit in this sequence
occurs in the part of the sequence in which the m-digit numbers are placed, define
f (n) to be m. For example, f (2) = 2 because the 100th digit enters the sequence in
the placement of the two-digit integer 55. Find, with proof, f (1987). (page 76)

A3. For all real x, the real-valued function y = f (x) satisfies

y  − 2y  + y = 2ex .
(a) If f (x) > 0 for all real x, must f  (x) > 0 for all real x? Explain.
(b) If f  (x) > 0 for all real x, must f (x) > 0 for all real x? Explain. (page 78)

A4. Let P be a polynomial, with real coefficients, in three variables and F be a

function of two variables such that
P (ux, uy, uz) = u2 F (y − x, z − x) for all real x, y, z, u,
and such that P (1, 0, 0) = 4, P (0, 1, 0) = 5, and P (0, 0, 1) = 6. Also let A, B, C be
complex numbers with P (A, B, C) = 0 and |B − A| = 10. Find |C − A|. (page 78)

A5. Let


- −y x
G(x, y) = , , 0 .
x2 + 4y 2 x2 + 4y 2
Prove or disprove that there is a vector-valued function
F- (x, y, z) = (M (x, y, z), N (x, y, z), P (x, y, z))
with the following properties:

† The equations defining A and B are indeterminate at (0, 0). The point (0, 0) belongs to neither.
Problems: The Forty-Eighth Competition (1987) 7

(i) M, N, P have continuous partial derivatives for all (x, y, z) = (0, 0, 0);
(ii) Curl F- = -0 for all (x, y, z) = (0, 0, 0);
(iii) F- (x, y, 0) = G(x,
- y).
(page 79)

A6. For each positive integer n, let a(n) be the number of zeros in the base 3
representation of n. For which positive real numbers x does the series
∞
xa(n)
n=1
n3

converge? (page 79)

B1. Evaluate
 
4
ln(9 − x) dx
  .
2 ln(9 − x) + ln(x + 3)
(page 80)

B2. Let r, s, and t be integers with 0 ≤ r, 0 ≤ s, and r + s ≤ t. Prove that

s s  s
t+1
0t  +  1t  + ··· +  s 
=  .
r r+1
t
r+s (t + 1 − s) t−s
r
n n(n−1)···(n+1−k)
(Note: k denotes the binomial coefficient k(k−1)···3·2·1 .) (page 81)

B3. Let F be a field in which 1 + 1 = 0. Show that the set of solutions to the
equation x2 + y 2 = 1 with x and y in F is given by (x, y) = (1, 0) and

2 
r −1 2r
(x, y) = , ,
r2 + 1 r2 + 1
where r runs through the elements of F such that r2 = −1. (page 83)

B4. Let (x1 , y1 ) = (0.8, 0.6) and let xn+1 = xn cos yn − yn sin yn and yn+1 =
xn sin yn + yn cos yn for n = 1, 2, 3, . . . . For each of limn→∞ xn and limn→∞ yn , prove
that the limit exists and find it or prove that the limit does not exist. (page 85)

B5. Let On be the n-dimensional vector (0, 0, . . . , 0). Let M be a 2n × n matrix of

complex numbers such that whenever (z1 , z2 , . . . , z2n )M = On , with complex zi , not
all zero, then at least one of the zi is not real. Prove that for arbitrary real numbers
r1 , r2 , . . . , r2n , there are complex numbers w1 , w2 , . . . , wn such that
    
w1 r1
    
Re M  ...  =  ...  .
wn r2n
(Note: if C is a matrix of complex numbers, Re(C) is the matrix whose entries are
the real parts of the entries of C.) (page 85)
8 The William Lowell Putnam Mathematical Competition

B6. Let F be the field of p2 elements where p is an odd prime. Suppose S is a set of
(p2 − 1)/2 distinct nonzero elements of F with the property that for each a = 0 in F ,
exactly one of a and −a is in S. Let N be the number of elements in the intersection
S ∩ { 2a : a ∈ S }. Prove that N is even. (page 86)
Problems: The Forty-Ninth Competition (1988) 9

The Forty-Ninth William Lowell Putnam Mathematical Competition

December 3, 1988
Questions Committee: Abraham P. Hillman, Gerald A. Heuer, and Paul R. Halmos
See page 38 for hints.

A1. Let R be the region consisting of the points (x, y) of the cartesian plane
satisfying both |x| − |y| ≤ 1 and |y| ≤ 1. Sketch the region R and find its area.
(page 88)

A2. A not uncommon calculus mistake is to believe that the product rule for
2
derivatives says that (f g) = f  g  . If f (x) = ex , determine, with proof, whether
there exists an open interval (a, b) and a nonzero function g defined on (a, b) such that
this wrong product rule is true for x in (a, b). (page 88)

A3. Determine, with proof, the set of real numbers x for which
∞
x
1 1
csc − 1
n=1
n n

converges. (page 89)

A4.
(a) If every point of the plane is painted one of three colors, do there necessarily exist
two points of the same color exactly one inch apart?
(b) What if “three” is replaced by “nine”?
Justify your answers. (page 90)

A5. Prove that there exists a unique function f from the set R+ of positive real
numbers to R+ such that
 
f f (x) = 6x − f (x) and f (x) > 0 for all x > 0.
(page 92)

A6. If a linear transformation A on an n-dimensional vector space has n + 1

eigenvectors such that any n of them are linearly independent, does it follow that
A is a scalar multiple of the identity? Prove your answer. (page 93)

B1. A composite (positive integer) is a product ab with a and b not necessarily

distinct integers in {2, 3, 4, . . . }. Show that every composite is expressible as xy +
xz + yz + 1, with x, y, and z positive integers. (page 94)

B2. Prove or disprove: if x and y are real numbers with y ≥ 0 and y(y+1) ≤ (x+1)2 ,
then y(y − 1) ≤ x2 . (page 95)

B3. For every√n in the set Z+ = {1, 2, . . . } of positive integers, let rn be the minimum
value of |c − d 3| for all nonnegative integers c and d with c + d = n. Find, with
proof, the smallest positive real number g with rn ≤ g for all n ∈ Z+ . (page 96)
10 The William Lowell Putnam Mathematical Competition

∞
B4. Prove that if an is a convergent series of positive real numbers, then so
∞ n/(n+1)
n=1
is n=1 (an ) . (page 97)

B5. For positive integers n, let Mn be the 2n + 1 by 2n + 1 skew-symmetric matrix

for which each entry in the first n subdiagonals below the main diagonal is 1 and each
of the remaining entries below the main diagonal is −1. Find, with proof, the rank
of Mn . (According to one definition, the rank of a matrix is the largest k such that
there is a k × k submatrix with nonzero determinant.)
One may note that
 
0 −1 −1 1 1
 
0 −1 1 1 0 −1 −1 1 
 
M1 =  1 0 −1 and M2 =   1 1 0 −1 −1 .
−1 1 0  −1 1 1 0 −1
−1 −1 1 1 0
(page 97)

B6. Prove that there exist an infinite number of ordered pairs (a, b) of integers such
that for every positive integer t the number at + b is a triangular number if and only
if t is a triangular number. (The triangular numbers are the tn = n(n + 1)/2 with n
in {0, 1, 2, . . . }.) (page 100)
Problems: The Fiftieth Competition (1989) 11

The Fiftieth William Lowell Putnam Mathematical Competition

December 2, 1989
Questions Committee: Gerald A. Heuer, Paul R. Halmos, and Kenneth A. Stolarsky
See page 39 for hints.

A1. How many primes among the positive integers, written as usual in base 10, are
such that their digits are alternating 1’s and 0’s, beginning and ending with 1?
(page 101)
 a  b
2
x2 ,a2 y 2 }
A2. Evaluate emax{b dy dx, where a and b are positive. (page 101)
0 0

A3. Prove that if

11z 10 + 10iz 9 + 10iz − 11 = 0,
then |z| = 1. (Here z is a complex number and i2 = −1.) (page 101)

A4. If α is an irrational number, 0 < α < 1, is there a finite game with an honest
coin such that the probability of one player winning the game is α? (An honest coin
is one for which the probability of heads and the probability of tails are both 1/2. A
game is finite if with probability 1 it must end in a finite number of moves.) (page 102)

A5. Let m be a positive integer and let G be a regular (2m + 1)-gon inscribed in
the unit circle. Show that there is a positive constant A, independent of m, with the
following property. For any point p inside G there are two distinct vertices v1 and v2
of G such that
1 A
|p − v1 | − |p − v2 | < − .
m m3
Here |s − t| denotes the distance between the points s and t. (page 103)

A6. Let α = 1 + a1 x + a2 x2 + · · · be a formal power series with coefficients in the

field of two elements. Let


 1 if every block of zeros in the binary expansion of n

has an even number of zeros in the block,
an =



0 otherwise.
(For example, a36 = 1 because 36 = 1001002 , and a20 = 0 because 20 = 101002 .)
Prove that α3 + xα + 1 = 0. (page 107)

B1. A dart, thrown at random, hits a square target. Assuming that any two parts
of the target of equal area are equally likely to be hit, find the probability that the
point
√ hit is nearer to the center than to any edge. Express your answer in the form
(a b + c)/d, where a, b, c, d are positive integers. (page 108)

B2. Let S be a nonempty set with an associative operation that is left and right
cancellative (xy = xz implies y = z, and yx = zx implies y = z). Assume that for
every a in S the set { an : n = 1, 2, 3, . . . } is finite. Must S be a group? (page 109)
12 The William Lowell Putnam Mathematical Competition

B3. Let f be a function on [0, ∞), differentiable and satisfying

f  (x) = −3f (x) + 6f (2x)
√
for x > 0. Assume that |f (x)| ≤ e− x for x ≥ 0 (so that f (x) tends rapidly to 0 as x
increases). For n a nonnegative integer, define
 ∞
µn = xn f (x) dx
0
(sometimes called the nth moment of f ).
a. Express µn in terms of µ0 .
b. Prove that the sequence {µn 3n /n!} always converges, and that the limit is 0 only
if µ0 = 0. (page 109)

B4. Can a countably infinite set have an uncountable collection of nonempty subsets
such that the intersection of any two of them is finite? (page 111)

B5. Label the vertices of a trapezoid T (quadrilateral with two parallel sides)
inscribed in the unit circle as A, B, C, D so that AB is parallel to CD and A, B, C, D
are in counterclockwise order. Let s1 , s2 , and d denote the lengths of the line segments
AB, CD, and OE, where E is the point of intersection of the diagonals of T , and O is
the center of the circle. Determine the least upper bound of (s1 − s2 )/d over all such
T for which d = 0, and describe all cases, if any, in which it is attained. (page 112)

B6. Let (x1 , x2 , . . . , xn ) be a point chosen at random from the n-dimensional region
defined by 0 < x1 < x2 < · · · < xn < 1. Let f be a continuous function on [0, 1] with
f (1) = 0. Set x0 = 0 and xn+1 = 1. Show that the expected value of the Riemann
sum n
(xi+1 − xi )f (xi+1 )
i=0
1
is 0 f (t)P (t) dt, where P is a polynomial of degree n, independent of f , with 0 ≤
P (t) ≤ 1 for 0 ≤ t ≤ 1. (page 113)
Problems: The Fifty-First Competition (1990) 13

The Fifty-First William Lowell Putnam Mathematical Competition

December 1, 1990
Questions Committee: Paul R. Halmos,
Kenneth A. Stolarsky, and George E. Andrews
See page 40 for hints.

A1. Let
T0 = 2, T1 = 3, T2 = 6,
and for n ≥ 3,
Tn = (n + 4)Tn−1 − 4nTn−2 + (4n − 8)Tn−3 .
The first few terms are
2, 3, 6, 14, 40, 152, 784, 5168, 40576, 363392.
Find, with proof, a formula for Tn of the form Tn = An + Bn , where (An ) and (Bn )
are well-known sequences. (page 116)
√ √ √
A2. Is 2 the limit of a sequence of numbers of the form 3 n − 3 m, (n, m =
0, 1, 2, . . . )? (page 117)

A3. Prove that any convex pentagon whose vertices (no three of which are collinear)
have integer coordinates must have area ≥ 5/2. (page 118)

A4. Consider a paper punch that can be centered at any point of the plane and
that, when operated, removes from the plane precisely those points whose distance
from the center is irrational. How many punches are needed to remove every point?
(page 120)

A5. If A and B are square matrices of the same size such that ABAB = 0, does it
follow that BABA = 0? (page 121)

A6. If X is a finite set, let |X| denote the number of elements in X. Call an ordered
pair (S, T ) of subsets of {1, 2, . . . , n} admissible if s > |T | for each s ∈ S, and t > |S|
for each t ∈ T . How many admissible ordered pairs of subsets of {1, 2, . . . , 10} are
there? Prove your answer. (page 123)

B1. Find all real-valued continuously differentiable functions f on the real line such
that for all x
 x  
2
(f (x)) = (f (t))2 + (f  (t))2 dt + 1990.
0
(page 124)

B2. Prove that for |x| < 1, |z| > 1,

∞
(1 − z)(1 − zx)(1 − zx2 ) · · · (1 − zxj−1 )
1+ (1 + xj ) = 0.
j=1
(z − x)(z − x2 )(z − x3 ) · · · (z − xj )

(page 125)
14 The William Lowell Putnam Mathematical Competition

B3. Let S be a set of 2 × 2 integer matrices whose entries aij (1) are all squares
of integers, and, (2) satisfy aij ≤ 200. Show that if S has more than 50387 (=
154 − 152 − 15 + 2) elements, then it has two elements that commute. (page 125)

B4. Let G be a finite group of order n generated by a and b. Prove or disprove:

there is a sequence
g1 , g2 , g3 , . . . , g2n
such that
(1) every element of G occurs exactly twice, and
(2) gi+1 equals gi a or gi b, for i = 1, 2, . . . , 2n. (Interpret g2n+1 as g1 .)
(page 126)

B5. Is there an infinite sequence a0 , a1 , a2 , . . . of nonzero real numbers such that for
n = 1, 2, 3, . . . the polynomial
pn (x) = a0 + a1 x + a2 x2 + · · · + an xn
has exactly n distinct real roots? (page 127)

B6. Let S be a nonempty closed bounded convex set in the plane. Let K be a line
and t a positive number. Let L1 and L2 be support lines for S parallel to K, and let
L be the line parallel to K and midway between L1 and L2 . Let BS (K, t) be the band
of points whose distance from L is at most (t/2)w, where w is the distance between
L1 and L2 . What is the smallest t such that
!
S∩ BS (K, t) = ∅
K

for all S? (K runs over all lines in the plane.)

Support line L1 w
tw

L S
B S( K,t ) K

Support line L2

(page 128)
Problems: The Fifty-Second Competition (1991) 15

The Fifty-Second William Lowell Putnam Mathematical Competition

December 7, 1991
Questions Committee: Kenneth A. Stolarsky,
George E. Andrews, and George T. Gilbert
See page 41 for hints.

A1. A 2 × 3 rectangle has vertices at (0, 0), (2, 0), (0, 3), and (2, 3). It rotates 90◦
clockwise about the point (2, 0). It then rotates 90◦ clockwise about the point (5, 0),
then 90◦ clockwise about the point (7, 0), and finally, 90◦ clockwise about the point
(10, 0). (The side originally on the x-axis is now back on the x-axis.) Find the area of
the region above the x-axis and below the curve traced out by the point whose initial
position is (1, 1). (page 135)

A2. Let A and B be different n × n matrices with real entries. If A3 = B3 and

A2 B = B2 A, can A2 + B2 be invertible? (page 135)

A3. Find all real polynomials p(x) of degree n ≥ 2 for which there exist real numbers
r1 < r2 < · · · < rn such that
(i) p(ri ) = 0, i = 1, 2, . . . , n, and
" #
 ri +ri+1
(ii) p 2 = 0, i = 1, 2, . . . , n − 1,
where p (x) denotes the derivative of p(x). (page 135)

A4. Does there exist an infinite sequence of closed discs D1 , D2 , D3 , . . . in the plane,
with centers c1 , c2 , c3 , . . . , respectively, such that
(i) the ci have no limit point in the finite plane,
(ii) the sum of the areas of the Di is finite, and
(iii) every line in the plane intersects at least one of the Di ?
(page 137)

A5. Find the maximum value of

 y 
x4 + (y − y 2 )2 dx
0

for 0 ≤ y ≤ 1. (page 138)

A6. Let A(n) denote the number of sums of positive integers a1 + a2 + · · · + ar which
add up to n with a1 > a2 + a3 , a2 > a3 + a4 , . . . , ar−2 > ar−1 + ar , ar−1 > ar . Let
B(n) denote the number of b1 + b2 + · · · + bs which add up to n, with
(i) b1 ≥ b2 ≥ · · · ≥ bs ,
(ii) each bi is in the sequence 1, 2, 4, . . . , gj , . . . defined by g1 = 1, g2 = 2, and
gj = gj−1 + gj−2 + 1, and
(iii) if b1 = gk then every element in {1, 2, 4, . . . , gk } appears at least once as a bi .
Prove that A(n) = B(n) for each n ≥ 1.
16 The William Lowell Putnam Mathematical Competition

(For example, A(7) = 5 because the relevant sums are 7, 6 + 1, 5 + 2, 4 + 3, 4 + 2 + 1,

and B(7) = 5 because the relevant sums are 4 + 2 + 1, 2 + 2 + 2 + 1, 2 + 2 + 1 + 1 + 1,
2 + 1 + 1 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1 + 1 + 1.) (page 139)

B1. For each integer n ≥ 0, let S(n) = n − m2 , where m is the greatest integer with
m2 ≤ n. Define a sequence (ak )∞ k=0 by a0 = A and ak+1 = ak + S(ak ) for k ≥ 0. For
what positive integers A is this sequence eventually constant? (page 141)

B2. Suppose f and g are nonconstant, differentiable, real-valued functions on R.

Furthermore, suppose that for each pair of real numbers x and y,
f (x + y) = f (x)f (y) − g(x)g(y),
g(x + y) = f (x)g(y) + g(x)f (y).
If f  (0) = 0, prove that (f (x))2 + (g(x))2 = 1 for all x. (page 142)

B3. Does there exist a real number L such that, if m and n are integers greater than
L, then an m × n rectangle may be expressed as a union of 4 × 6 and 5 × 7 rectangles,
any two of which intersect at most along their boundaries? (page 143)

B4. Suppose p is an odd prime. Prove that

p


p p+j
≡ 2p + 1 (mod p2 ).
j=0
j j

(page 145)

B5. Let p be an odd prime and let Zp denote† (the field of) integers modulo p. How
many elements are in the set
{ x2 : x ∈ Zp } ∩ { y 2 + 1 : y ∈ Zp }?
(page 148)

B6. Let a and b be positive numbers. Find the largest number c, in terms of a and
b, such that
sinh ux sinh u(1 − x)
ax b1−x ≤ a +b
sinh u sinh u
for all u with 0 < |u| ≤ c and for all x, 0 < x < 1. (Note: sinh u = (eu − e−u )/2.)
(page 151)

† This notation is becoming nonstandard in current mathematics; see the warning preceding the

solution.
Problems: The Fifty-Third Competition (1992) 17

The Fifty-Third William Lowell Putnam Mathematical Competition

December 5, 1992
Questions Committee: George E. Andrews, George T. Gilbert, and Eugene Luks
See page 42 for hints.

A1. Prove that f (n) = 1 − n is the only integer-valued function defined on the
integers that satisfies the following conditions:
(i) f (f (n)) = n, for all integers n;
(ii) f (f (n + 2) + 2) = n for all integers n;
(iii) f (0) = 1. (page 154)

A2. Define C(α) to be the coefficient of x1992 in the power series expansion about
x = 0 of (1 + x)α . Evaluate
 1

1 1 1 1
C(−y − 1) + + + ··· + dy.
0 y+1 y+2 y+3 y + 1992
(page 154)

A3. For a given positive integer m, find all triples (n, x, y) of positive integers, with
n relatively prime to m, which satisfy (x2 + y 2 )m = (xy)n . (page 154)

A4. Let f be an infinitely differentiable real-valued function defined on the real

numbers. If

1 n2
f = 2 , n = 1, 2, 3, . . . ,
n n +1
compute the values of the derivatives f (k) (0), k = 1, 2, 3, . . . . (page 155)

A5. For each positive integer n, let

0 if the number of 1’s in the binary representation of n is even,
an =
1 if the number of 1’s in the binary representation of n is odd.
Show that there do not exist positive integers k and m such that

ak+j = ak+m+j = ak+2m+j ,

for 0 ≤ j ≤ m − 1. (page 156)

A6. Four points are chosen at random on the surface of a sphere. What is the
probability that the center of the sphere lies inside the tetrahedron whose vertices are
at the four points? (It is understood that each point is independently chosen relative
to a uniform distribution on the sphere.) (page 159)

B1. Let S be a set of n distinct real numbers. Let AS be the set of numbers that
occur as averages of two distinct elements of S. For a given n ≥ 2, what is the smallest
possible number of elements in AS ? (page 160)
18 The William Lowell Putnam Mathematical Competition

B2. For nonnegative integers n and k, define Q(n, k) to be the coefficient of xk in

the expansion of (1 + x + x2 + x3 )n . Prove that
k


n n
Q(n, k) = ,
j=0
j k − 2j
 
where ab  is the standard binomial coefficient.
  (Reminder: For integers a and b with
a ≥ 0, ab = b!(a−b)!
a!
for 0 ≤ b ≤ a, with ab = 0 otherwise.) (page 161)

B3. For any pair (x, y) of real numbers, a sequence (an (x, y))n≥0 is defined as
follows:
a0 (x, y) = x,
(an (x, y))2 + y 2
an+1 (x, y) = , for n ≥ 0.
2
Find the area of the region { (x, y)|(an (x, y))n≥0 converges }. (page 161)

B4. Let p(x) be a nonzero polynomial of degree less than 1992 having no nonconstant
factor in common with x3 − x. Let


d1992 p(x) f (x)
=
dx1992 x3 − x g(x)
for polynomials f (x) and g(x). Find the smallest possible degree of f (x). (page 163)

B5. Let Dn denote the value of the (n − 1) × (n − 1) determinant

3 1 1 1 ··· 1
1 4 1 1 ··· 1
1 1 5 1 ··· 1
1 1 1 6 ··· 1 .
.. .. .. .. .. ..
. . . . . .
1 1 1 1 ··· n+1
Is the set {Dn /n!}n≥2 bounded? (page 164)

B6. Let M be a set of real n × n matrices such that

(i) I ∈ M, where I is the n × n identity matrix;
(ii) if A ∈ M and B ∈ M, then either AB ∈ M or −AB ∈ M, but not both;
(iii) if A ∈ M and B ∈ M, then either AB = BA or AB = −BA;
(iv) if A ∈ M and A = I, there is at least one B ∈ M such that AB = −BA.
Prove that M contains at most n2 matrices. (page 166)
Problems: The Fifty-Fourth Competition (1993) 19

The Fifty-Fourth William Lowell Putnam Mathematical Competition

December 4, 1993
Questions Committee: George T. Gilbert, Eugene Luks, and Fan Chung
See page 43 for hints.

A1. The horizontal line y = c intersects the curve y = 2x − 3x3 in the first quadrant
as in the figure. Find c so that the areas of the two shaded regions are equal.
y

y=c

3
y = 2x – 3x

(page 171)

A2. Let (xn )n≥0 be a sequence of nonzero real numbers such that
x2n − xn−1 xn+1 = 1 for n = 1, 2, 3, . . . .
Prove there exists a real number a such that xn+1 = axn − xn−1 for all n ≥ 1.
(page 171)

A3. Let Pn be the set of subsets of {1, 2, . . . , n}. Let c(n, m) be the number of
functions f : Pn → {1, 2, . . . , m} such that f (A ∩ B) = min{f (A), f (B)}. Prove that
m
c(n, m) = jn.
j=1

(page 173)

A4. Let x1 , x2 , . . . , x19 be positive integers each of which is less than or equal to
93. Let y1 , y2 , . . . , y93 be positive integers each of which is less than or equal to 19.
Prove that there exists a (nonempty) sum of some xi ’s equal to a sum of some yj ’s.
(page 174)

A5. Show that

 −10
2  1
2  11
2
x2 − x 11 x2 − x 10 x2 − x
dx + dx + dx
−100 x3 − 3x + 1 1
101
x3 − 3x + 1 101
100
x3 − 3x + 1
is a rational number. (page 175)

A6. The infinite sequence of 2’s and 3’s

2, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 2, 3, 3, 3, 2, . . .
20 The William Lowell Putnam Mathematical Competition

has the property that, if one forms a second sequence that records the number of 3’s
between successive 2’s, the result is identical to the given sequence. Show that there
exists a real number r such that, for any n, the nth term of the sequence is 2 if and
only if n = 1 + rm for some nonnegative integer m. (Note: x denotes the largest
integer less than or equal to x.) (page 178)

B1. Find the smallest positive integer n such that for every integer m, with 0 <
m < 1993, there exists an integer k for which
m k m+1
< < .
1993 n 1994
(page 180)

B2. Consider the following game played with a deck of 2n cards numbered from 1 to
2n. The deck is randomly shuffled and n cards are dealt to each of two players, A and
B. Beginning with A, the players take turns discarding one of their remaining cards
and announcing its number. The game ends as soon as the sum of the numbers on
the discarded cards is divisible by 2n + 1. The last person to discard wins the game.
Assuming optimal strategy by both A and B, what is the probability that A wins?
(page 182)

B3. Two real numbers x and y are chosen at random in the interval (0,1) with
respect to the uniform distribution. What is the probability that the closest integer
to x/y is even? Express the answer in the form r + sπ, where r and s are rational
numbers. (page 182)

B4. The function K(x, y) is positive and continuous for 0 ≤ x ≤ 1, 0 ≤ y ≤ 1, and

the functions f (x) and g(x) are positive and continuous for 0 ≤ x ≤ 1. Suppose that
for all x, 0 ≤ x ≤ 1,
 1  1
f (y)K(x, y) dy = g(x) and g(y)K(x, y) dy = f (x).
0 0
Show that f (x) = g(x) for 0 ≤ x ≤ 1. (page 184)

B5. Show there do not exist four points in the Euclidean plane such that the pairwise
distances between the points are all odd integers. (page 185)

B6. Let S be a set of three, not necessarily distinct, positive integers. Show that
one can transform S into a set containing 0 by a finite number of applications of the
following rule: Select two of the three integers, say x and y, where x ≤ y and replace
them with 2x and y − x. (page 188)
Problems: The Fifty-Fifth Competition (1994) 21

The Fifty-Fifth William Lowell Putnam Mathematical Competition

December 3, 1994
Questions Committee: Eugene Luks, Fan Chung, and Mark I. Krusemeyer
See page 44 for hints.

A1. Suppose that a sequence a , a , a , . . . satisfies 0 < an ≤ a2n + a2n+1 for all
 1 2 3 ∞
n ≥ 1. Prove that the series n=1 an diverges. (page 191)

A2. Let A be the area of the region in the first quadrant bounded by the line y = 12 x,
the x-axis, and the ellipse 19 x2 + y 2 = 1. Find the positive number m such that A is
equal to the area of the region in the first quadrant bounded by the line y = mx, the
y-axis, and the ellipse 19 x2 + y 2 = 1. (page 191)

A3. Show that if the points of an isosceles right triangle of side length 1 are each
colored with one of four colors,
√ then there must be two points of the same color which
are at least a distance 2 − 2 apart. (page 192)

A4. Let A and B be 2 × 2 matrices with integer entries such that A, A + B, A + 2B,
A + 3B, and A + 4B are all invertible matrices whose inverses have integer entries.
Show that A + 5B is invertible and that its inverse has integer entries. (page 193)

A5. Let (rn )n≥0 be a sequence of positive real numbers such that limn→∞ rn = 0.
Let S be the set of numbers representable as a sum

ri1 + ri2 + · · · + ri1994 ,

with i1 < i2 < · · · < i1994 . Show that every nonempty interval (a, b) contains a
nonempty subinterval (c, d) that does not intersect S. (page 194)

A6. Let f1 , f2 , . . . , f10 be bijections of the set of integers such that for each integer
n, there is some composition fi1 ◦ fi2 ◦ · · · ◦ fim of these functions (allowing repetitions)
which maps 0 to n. Consider the set of 1024 functions

F = {f1e1 ◦ f2e2 ◦ · · · ◦ f10

e10
},

ei = 0 or 1 for 1 ≤ i ≤ 10. (fi0 is the identity function and fi1 = fi .) Show that if A
is any nonempty finite set of integers, then at most 512 of the functions in F map A
to itself. (page 195)

B1. Find all positive integers that are within 250 of exactly 15 perfect squares.
(page 196)

B2. For which real numbers c is there a straight line that intersects the curve
y = x4 + 9x3 + cx2 + 9x + 4

in four distinct points? (page 196)

22 The William Lowell Putnam Mathematical Competition

B3. Find the set of all real numbers k with the following property: For any positive,
differentiable function f that satisfies f  (x) > f (x) for all x, there is some number N
such that f (x) > ekx for all x > N . (page 198)

B4. For n ≥ 1, let dn be the greatest common divisor of the entries of An − I, where



3 2 1 0
A= and I = .
4 3 0 1
Show that limn→∞ dn = ∞. (page 198)

B5. For any real number α, define the function fα (x) = αx. Let n be a positive
integer. Show that there exists an α such that for 1 ≤ k ≤ n,†
fαk (n2 ) = n2 − k = fαk (n2 ).
(page 200)

B6. For any integer a, set

na = 101a − 100 · 2a .
Show that for 0 ≤ a, b, c, d ≤ 99, na +nb ≡ nc +nd (mod 10100) implies {a, b} = {c, d}.
(page 202)

† Here fαk (n2 ) = fα (· · · (fα (n2 )) · · · ), where fα is applied k times to n2 .

Problems: The Fifty-Sixth Competition (1995) 23

The Fifty-Sixth William Lowell Putnam Mathematical Competition

December 2, 1995
Questions Committee: Fan Chung, Mark I. Krusemeyer, and Richard K. Guy
See page 45 for hints.

A1. Let S be a set of real numbers which is closed under multiplication (that is, if
a and b are in S, then so is ab). Let T and U be disjoint subsets of S whose union is
S. Given that the product of any three (not necessarily distinct) elements of T is in
T and that the product of any three elements of U is in U , show that at least one of
the two subsets T, U is closed under multiplication. (page 204)

A2. For what pairs (a, b) of positive real numbers does the improper integral

$ $ 
∞ √ √ √ √
x+a− x− x− x − b dx
b

converge? (page 204)

A3. The number d1 d2 . . . d9 has nine (not necessarily distinct) decimal digits. The
number e1 e2 . . . e9 is such that each of the nine 9-digit numbers formed by replacing
just one of the digits di in d1 d2 . . . d9 by the corresponding digit ei (1 ≤ i ≤ 9) is
divisible by 7. The number f1 f2 . . . f9 is related to e1 e2 . . . e9 is the same way: that
is, each of the nine numbers formed by replacing one of the ei by the corresponding
fi is divisible by 7. Show that, for each i, di − fi is divisible by 7. [For example, if
d1 d2 . . . d9 = 199501996, then e6 may be 2 or 9, since 199502996 and 199509996 are
multiples of 7.] (page 205)

A4. Suppose we have a necklace of n beads. Each bead is labelled with an integer
and the sum of all these labels is n − 1. Prove that we can cut the necklace to form a
string whose consecutive labels x1 , x2 , . . . , xn satisfy
k
xi ≤ k − 1 for k = 1, 2, . . . , n.
i=1

(page 205)

A5. Let x1 , x2 , . . . , xn be differentiable (real-valued) functions of a single variable t

which satisfy
dx1
= a11 x1 + a12 x2 + · · · + a1n xn
dt
dx2
= a21 x1 + a22 x2 + · · · + a2n xn
dt
..
.
dxn
= an1 x1 + an2 x2 + · · · + ann xn
dt
for some constants aij > 0. Suppose that for all i, xi (t) → 0 as t → ∞. Are the
functions x1 , x2 , . . . , xn necessarily linearly dependent? (page 206)
24 The William Lowell Putnam Mathematical Competition

A6. Suppose that each of n people writes down the numbers 1, 2, 3 in random order
in one column of a 3 × n matrix, with all orders equally likely and with the orders for
different columns independent of each other. Let the row sums a, b, c of the resulting
matrix be rearranged (if necessary) so that a ≤ b ≤ c. Show that for some n ≥ 1995,
it is at least four times as likely that both b = a + 1 and c = a + 2 as that a = b = c.
(page 207)

B1. For a partition π of {1, 2, 3, 4, 5, 6, 7, 8, 9}, let π(x) be the number of elements in
the part containing x. Prove that for any two partitions π and π  , there are two distinct
numbers x and y in {1, 2, 3, 4, 5, 6, 7, 8, 9} such that π(x) = π(y) and π  (x) = π  (y).
[A partition of a set S is a collection of disjoint subsets (parts) whose union is S.]
(page 209)

B2. An ellipse, whose

 semi-axes have lengths a and b, rolls without slipping on the
curve y = c sin xa . How are a, b, c related, given that the ellipse completes one
revolution when it traverses one period of the curve? (page 209)

B3. To each positive integer with n2 decimal digits, we associate the determinant
of the matrix obtained by writing the digits in
order across
 the rows. For example,
8 6
for n = 2, to the integer 8617 we associate det = 50. Find, as a function of
1 7
n, the sum of all the determinants associated with n2 -digit integers. (Leading digits
are assumed to be nonzero; for example, for n = 2, there are 9000 determinants.)
(page 211)

B4. Evaluate
%
1
8 2207 − .
2207 − 2207−···
1

√
a+b c
Express your answer in the form d , where a, b, c, d are integers. (page 211)

B5. A game starts with four heaps of beans, containing 3, 4, 5 and 6 beans. The
two players move alternately. A move consists of taking either
(a) one bean from a heap, provided at least two beans are left behind in that heap,
or
(b) a complete heap of two or three beans.
The player who takes the last heap wins. To win the game, do you want to move first
or second? Give a winning strategy. (page 212)

B6. For a positive real number α, define

S(α) = { nα : n = 1, 2, 3, . . . }.
Prove that {1, 2, 3, . . . } cannot be expressed as the disjoint union of three sets
S(α), S(β) and S(γ). (page 214)
Problems: The Fifty-Seventh Competition (1996) 25

The Fifty-Seventh William Lowell Putnam Mathematical Competition

December 7, 1996
Questions Committee: Mark I. Krusemeyer, Richard K. Guy, and Michael J. Larsen
See page 46 for hints.

A1. Find the least number A such that for any two squares of combined area 1, a
rectangle of area A exists such that the two squares can be packed in the rectangle
(without the interiors of the squares overlapping). You may assume that the sides of
the squares will be parallel to the sides of the rectangle. (page 217)

A2. Let C1 and C2 be circles whose centers are 10 units apart, and whose radii are
1 and 3. Find, with proof, the locus of all points M for which there exists points X
on C1 and Y on C2 such that M is the midpoint of the line segment XY . (page 218)

A3. Suppose that each of 20 students has made a choice of anywhere from 0 to 6
courses from a total of 6 courses offered. Prove or disprove: there are 5 students and 2
courses such that all 5 have chosen both courses or all 5 have chosen neither course.
(page 218)

A4. Let S be a set of ordered triples (a, b, c) of distinct elements of a finite set A.
Suppose that
(1) (a, b, c) ∈ S if and only if (b, c, a) ∈ S;
(2) (a, b, c) ∈ S if and only if (c, b, a) ∈
/ S [for a, b, c distinct];
(3) (a, b, c) and (c, d, a) are both in S if and only if (b, c, d) and (d, a, b) are both in S.
Prove that there exists a one-to-one function g from A to R such that g(a) < g(b) <
g(c) implies (a, b, c) ∈ S. (page 219)

A5. If p is a prime number greater than 3 and k = 2p/3, prove that the sum




p p p
+ + ··· +
1 2 k
of binomial coefficients is divisible by p2 . (page 220)

A6. Let c ≥ 0 be a constant. Give a complete description, with proof, of the set of
all continuous functions f : R → R such that f (x) = f (x2 + c) for all x ∈ R.
(page 220)

B1. Define a selfish set to be a set which has its own cardinality (number of
elements) as an element. Find, with proof, the number of subsets of {1, 2, . . . , n}
which are minimal selfish sets, that is, selfish sets none of whose proper subsets is
selfish. (page 222)

B2. Show that for every positive integer n,

 2n−1
 2n+1
2n − 1 2
2n + 1 2
< 1 · 3 · 5 · · · (2n − 1) < .
e e
(page 224)
26 The William Lowell Putnam Mathematical Competition

B3. Given that {x1 , x2 , . . . , xn } = {1, 2, . . . , n}, find, with proof, the largest
possible value, as a function of n (with n ≥ 2), of
x1 x2 + x2 x3 + · · · + xn−1 xn + xn x1 .
(page 225)

B4. For any square matrix A, we can define sin A by the usual power series:
∞
(−1)n
sin A = A2n+1 .
n=0
(2n + 1)!
Prove or disprove: there exists a 2 × 2 matrix A with real entries such that


1 1996
sin A = .
0 1
(page 227)

B5. Given a finite string S of symbols X and O, we write ∆(S) for the number of X’s
in S minus the number of O’s. For example, ∆(XOOXOOX) = −1. We call a string
S balanced if every substring T of (consecutive symbols of) S has −2 ≤ ∆(T ) ≤ 2.
Thus, XOOXOOX is not balanced, since it contains the substring OOXOO. Find,
with proof, the number of balanced strings of length n. (page 229)

B6. Let (a1 , b1 ), (a2 , b2 ), . . . , (an , bn ) be the vertices of a convex polygon which
contains the origin in its interior. Prove that there exist positive real numbers x
and y such that
(a1 , b1 )xa1 y b1 + (a2 , b2 )xa2 y b2 + · · · + (an , bn )xan y bn = (0, 0).
(page 230)
Problems: The Fifty-Eighth Competition (1997) 27

The Fifty-Eighth William Lowell Putnam Mathematical Competition

December 6, 1997
Questions Committee: Richard K. Guy, Michael J. Larsen, and David J. Wright
See page 47 for hints.

A1. A rectangle, HOM F , has sides HO = 11 and OM = 5. A triangle ABC has

H as the intersection of the altitudes, O the center of the circumscribed circle, M the
midpoint of BC, and F the foot of the altitude from A. What is the length of BC?
H O

F 11 M
(page 232)

A2. Players 1, 2, 3, . . . , n are seated around a table, and each has a single penny.
Player 1 passes a penny to Player 2, who then passes two pennies to Player 3. Player
3 then passes one penny to Player 4, who passes two pennies to Player 5, and so on,
players alternately passing one penny or two to the next player who still has some
pennies. A player who runs out of pennies drops out of the game and leaves the table.
Find an infinite set of numbers n for which some player ends up with all n pennies.
(page 233)

A3. Evaluate
 ∞


x3 x5 x7 x2 x4 x6
x− + − + ··· 1 + 2 + 2 2 + 2 2 2 + · · · dx.
0 2 2·4 2·4·6 2 2 ·4 2 ·4 ·6
(page 234)

A4. Let G be a group with identity e and φ : G → G a function such that

φ(g1 )φ(g2 )φ(g3 ) = φ(h1 )φ(h2 )φ(h3 )
whenever g1 g2 g3 = e = h1 h2 h3 . Prove that there exists an element a ∈ G such that
ψ(x) = aφ(x) is a homomorphism (that is, ψ(xy) = ψ(x)ψ(y) for all x, y ∈ G).
(page 237)

A5. Let Nn denote the number of ordered n-tuples of positive integers (a1 , a2 , . . . , an )
such that 1/a1 + 1/a2 + · · · + 1/an = 1. Determine whether N10 is even or odd.
(page 237)

A6. For a positive integer n and any real number c, define xk recursively by x0 = 0,
x1 = 1, and for k ≥ 0,
cxk+1 − (n − k)xk
xk+2 = .
k+1
28 The William Lowell Putnam Mathematical Competition

Fix n and then take c to be the largest value for which xn+1 = 0. Find xk in terms of
n and k, 1 ≤ k ≤ n. (page 238)

B1. Let {x} denote the distance between the real number x and the nearest integer.
For each positive integer n, evaluate
6n−1 "& m ' & m '#
Sn = min , .
m=1
6n 3n
(Here min(a, b) denotes the minimum of a and b.) (page 242)

B2. Let f be a twice-differentiable real-valued function satisfying

f (x) + f  (x) = −xg(x)f  (x),
where g(x) ≥ 0 for all real x. Prove that |f (x)| is bounded. (page 243)
n
B3. For each positive integer n, write the sum in the form pqnn , where pn
1
m=1 m
and qn are relatively prime positive integers. Determine all n such that 5 does not
divide qn . (page 244)

B4. Let am,n denote the coefficient of xn in the expansion of (1 + x + x2 )m . Prove

that for all integers k ≥ 0,
2k
3

0≤ (−1)i ak−i,i ≤ 1.
i=0

(page 246)

B5. Prove that for n ≥ 2,

2
' 2
'
·· ··
2· n 2· n−1
2 ≡2 (mod n).
(page 247)

B6. The dissection of the 3–4–5 triangle shown below has diameter 5/2.
❙
❙
❙
❙ 5
4 ❙

 ❙
 ❙
 ❙
 ❙
3
Find the least diameter of a dissection of this triangle into four parts. (The diameter of
a dissection is the least upper bound of the distances between pairs of points belonging
to the same part.) (page 248)
 Problems: The Fifty-Ninth Competition (1998) 29

The Fifty-Ninth William Lowell Putnam Mathematical Competition

December 5, 1998
Questions Committee: Michael J. Larsen, David J. Wright, and Steven G. Krantz
See page 48 for hints.

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? (page 250)

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. (page 250)

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.

(page 251)

A4. Let A1 = 0 and 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 . (page 252)

A5. Let F be a finite collection of open discs in R2 whose union contains a set
E ⊆ R2 . Show that there is a pairwise disjoint subcollection D1 , . . . , Dn in F such
that
(n
E⊆ 3Dj .
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 . (page 252)

A6. Let A, B, C denote distinct points with integer coordinates in R2 . 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. (page 253)

B1. Find the minimum value of

(x + 1/x)6 − (x6 + 1/x6 ) − 2
(x + 1/x)3 + (x3 + 1/x3 )
for x > 0. (page 253)
30 The William Lowell Putnam Mathematical Competition

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. (page 254)

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 + y 2 = 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.
(page 255)

B4. Find necessary and sufficient conditions on positive integers m and n so that
mn−1
i/m + i/n
(−1) = 0.
i=0

(page 256)

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. (page 257)

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. (page 258)
Problems: The Sixtieth Competition (1999) 31

The Sixtieth William Lowell Putnam Mathematical Competition

December 4, 1999
Questions Committee: David J. Wright, Steven G. Krantz, and Andrew J. Granville
See page 49 for hints.

A1. Find polynomials f (x), g(x), and h(x), if they exist, such that, for all x,


−1
 if x < −1
|f (x)| − |g(x)| + h(x) = 3x + 2 if −1 ≤ x ≤ 0


−2x + 2 if x > 0.

(page 262)

A2. Let p(x) be a polynomial that is nonnegative for all real x. Prove that for some
k, there are polynomials f1 (x), . . . , fk (x) such that
k
p(x) = (fj (x))2 .
j=1

(page 263)

A3. Consider the power series expansion

∞
1
= an xn .
1 − 2x − x2 n=0

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

a2n + a2n+1 = am .
(page 264)

A4. Sum the series

∞ ∞
m2 n
.
m=1 n=1
3m (n3m + m3n )

(page 265)

A5. Prove that there is a constant C such that, if p(x) is a polynomial of degree
1999, then
 1
|p(0)| ≤ C |p(x)| dx.
−1

(page 266)

A6. The sequence (an )n≥1 is defined by a1 = 1, a2 = 2, a3 = 24, and, for n ≥ 4,

6a2n−1 an−3 − 8an−1 a2n−2
an = .
an−2 an−3
Show that, for all n, an is an integer multiple of n. (page 267)
32 The William Lowell Putnam Mathematical Competition

B1. Right triangle ABC has right angle at C and ∠BAC = θ; the point D is chosen
on AB so that |AC| = |AD| = 1; the point E is chosen on BC so that ∠CDE = θ.
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.]
C

q
q
A F D B
(page 268)

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.] (page 269)

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

S(x, y) = xm y n ,
1 m
2 ≤ n ≤2

where the sum ranges over all pairs (m, n) of positive integers satisfying the indicated
inequalities. Evaluate
lim (1 − xy 2 )(1 − x2 y)S(x, y).
(x,y)→(1,1)
(x,y)∈A

(page 271)

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. (page 272)

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 = (ajk ) has entries ajk = cos(jθ +kθ)
for all j, k. (page 276)

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. (page 277)
Problems: The Sixty-First Competition (2000) 33

The Sixty-First William Lowell Putnam Mathematical Competition

December 2, 2000
Questions Committee: Steven G. Krantz, Andrew J. Granville,
Carl Pomerance, and Eugene Luks
See page 50 for hints.
∞
A1. Let A be a positive real number. What are 
the possible values of j=0x2j ,
∞
given that x0 , x1 , . . . are positive numbers for which j=0 xj = A? (page 278)

A2. Prove that there exist infinitely many integers n such that n, n + 1, n + 2 are
each the sum of two squares of integers. [Example: 0 = 02 + 02 , 1 = 02 + 12 , and
2 = 12 + 12 .] (page 278)

A3. The octagon P1 P2 P3 P4 P5 P6 P7 P8 is inscribed in a circle, with the vertices

around the circumference in the given order. Given that the polygon P1 P3 P5 P7 is a
square of area 5 and the polygon P2 P4 P6 P8 is a rectangle of area 4, find the maximum
possible area of the octagon. (page 280)

A4. Show that the improper integral

 B
lim sin(x) sin(x2 ) dx
B→∞ 0
converges. (page 281)

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
r1/3 . (page 285)

A6. Let f (x) be a polynomial with integer coefficients. Define a sequence a0 , a1 , . . .

of integers such that a0 = 0 and an+1 = f (an ) for all n ≥ 0. Prove that if there exists
a positive integer m for which am = 0 then either a1 = 0 or a2 = 0. (page 288)

B1. Let aj , bj , cj be integers for 1 ≤ j ≤ N . Assume, for each j, at least one of

aj , bj , cj is odd. Show that there exist integers r, s, t such that raj + sbj + tcj is odd
for at least 4N/7 values of j, 1 ≤ j ≤ N . (page 289)

B2. Prove that the expression


gcd(m, n) n
n m
is an integer for all pairs of integers n ≥ m ≥ 1. (page 290)

B3. Let f (t) = N j=1 aj sin(2πjt), where each aj is real and aN is not equal to 0.
dk f
Let Nk denote the number of zeros† (including multiplicities) of dtk
. Prove that
N0 ≤ N1 ≤ N2 ≤ · · · and lim Nk = 2N.
k→∞

(page 290)

† The proposers intended for Nk to count only the zeros in the interval [0, 1).
34 The William Lowell Putnam Mathematical Competition

B4. Let f (x) be a continuous function such that f (2x2 − 1) = 2xf (x) for all x.
Show that f (x) = 0 for −1 ≤ x ≤ 1. (page 292)

B5. Let S0 be a finite set of positive integers. We define finite sets S1 , S2 , . . . of

positive integers as follows: the integer a is in Sn+1 if and only if exactly one of
a − 1 or a is in Sn . Show that there exist infinitely many integers N for which
SN = S0 ∪ { N + a : a ∈ S0 }. (page 293)

B6. Let B be a set of more than 2n+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. (page 294)