Solutions
Solutions
51
Solutions: The Forty-Sixth Competition (1985) 53
maps onto the set T of 10 × 3 matrices with 0, 1 entries such that no row is (000) or
(111). The number of possibilities for each row of such a matrix is 23 − 2 = 6, so
#T = 610 . Hence #S = #T = 210 310 .
Reinterpretation. Equivalently, this problem asks for the number of ways of placing
the numbers 1 through 10 in the Venn diagram of Figure 1, where no numbers are
placed in the two regions marked with an “×”.
A1
A2 A3
FIGURE 1.
Venn diagram interpretation of the solution to 1985A1.
54 The William Lowell Putnam Mathematical Competition
A2. (29, 15, 31, 14, 38, 11, 2, 15, 6, 4, 21, 15)
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.
❆
❆
Rn−1 ❆
❆
Rn−2 ❆
.. ❆
. ❆
❆
❆
R2 ❆
❆
R1
❆
❆
❆
FIGURE 2.
A generalization of 1985A2.
A(R)+A(S)
Answer. The maximum value of A(T ) exists and equals 2/3.
Solution. In fact, for any n ≥ 2, we can find the maximum value of
A(R1 ) + · · · + A(Rn−1 )
A(T )
for any stack of rectangles inscribed in T as shown in Figure 2. The altitude of T
divides T into right triangles U on the left and V on the right. For i = 1, . . . , n − 1, let
Ui denote the small right triangle to the left of Ri , and let Un denote the small right
triangle above Rn−1 and to the left of the altitude of T . Symmetrically define V1 , . . . ,
Vn to be the right triangles on the right. Each Ui is similar to U , so A(Ui ) = a2i A(U ),
where ai is the altitude of Ui , measured as a fraction of the altitude of T . Similarly,
A(Vi ) = a2i A(V ). Hence
A(U1 ) + · · · + A(Un ) + A(V1 ) + · · · + A(Vn ) = (a21 + · · · + a2n )(A(U ) + A(V ))
= (a21 + · · · + a2n )A(T ).
Solutions: The Forty-Sixth Competition (1985) 55
The ai must be positive numbers with sum 1, and conversely any such ai give rise to
a stack of rectangles in T .
It remains to minimize a21 + · · · + a2n subject to the constraints ai > 0 for all i and
a1 + · · · + an = 1. That the minimum is attained when a1 = · · · = an = 1/n can be
proved in many ways:
1. The identity
implies that
1 1
a21 + · · · + a2n ≥
(a1 + · · · + an )2 = ,
n n
with equality if and only if a1 = a2 = · · · = an .
2. Take b1 = · · · = bn = 1 in the Cauchy-Schwarz Inequality [HLP, Theorem 7]
meets H at P = (1/n, . . . , 1/n). The quantity a21 + · · · + a2n can be viewed as the
square of the distance from 0 to the point (a1 , . . . , an ) on H, and this is minimized
when (a1 , . . . , an ) = P .
In any case, we find that the minimum value of a21 + · · · + a2n is 1/n, so the maximum
value of A(R1 )+···+A(R
A(T )
n−1 )
is 1 − 1/n. For the problem as stated, n = 3, so the
maximum value is 2/3.
Remark. The minimum is unchanged if instead of allowing T to vary, we fix a
particular acute triangle T .
Remark. While we are on the subject of inequalities, we should also mention the
very useful Arithmetic-Mean–Geometric-Mean Inequality (AM-GM), which states that
for nonnegative real numbers a1 , . . . , an , we have
a 1 + a 2 + · · · + an 1/n
≥ (a1 a2 · · · an ) ,
n
with equality if and only if a1 = a2 = · · · = an . This is the special case P1 ≥ P0 of
the Power Mean Inequality. It can also be deduced by taking f (x) = ln x in Jensen’s
Inequality.
Hence 2n
d
lim an (n) = lim 1+ n − 1.
n→∞ n→∞ 2
If f (x) = ln(1 + dx), then f (x) = d/(1 + dx), and in particular
ln(1 + dx)
lim = f (0) = d.
x→0 x
Applying the continuous function ex yields
lim (1 + dx)1/x = ed ,
x→0
Euler’s Theorem [Lar1, p. 148], which is Lagrange’s Theorem (the order of an element
of a finite group divides the order of the group, [Lar1, p. 147]) applied to the group
(Z/nZ)∗ , states that aφ(n) ≡ 1 (mod n) whenever gcd(a, n) = 1.
It shows that ai = 3ai−1 modulo 100 is determined by ai−1 modulo φ(100) = 40,
for i ≥ 2. Similarly ai−1 mod 40 is determined by ai−2 mod 16, which is determined
by ai−3 mod 8, for i ≥ 4. Finally ai−3 mod 8 is determined by ai−4 mod 2 for i ≥ 5,
since 32 ≡ 1 (mod 8). For i ≥ 5, ai−4 is odd, so
ai−3 = 3ai−4 ≡ 31 ≡ 3 (mod 8)
ai−2 = 3 ai−3
≡3 3
≡ 11 (mod 16)
ai−1 = 3 ai−2
≡3 11
≡ 27 (mod 40)
ai =3 ai−1
≡3 27
≡ 87 (mod 100).
Thus the only integer that appears as the last two digits of infinitely many ai is 87.
Remark. Carmichael’s lambda function. The exponent in Euler’s Theorem is not
always best possible. The function λ(n) giving the best possible exponent for n, i.e.,
the least positive integer λ such that aλ ≡ 1 (mod n) whenever gcd(a, n) = 1, is known
as Carmichael’s lambda function or as the reduced totient function. If n = pe11 · · · pekk ,
then
λ(n) = lcm(λ(pe11 ), . . . , λ(pekk )),
where
λ(pe ) = φ(pe ) = pe−1 (p − 1),
unless p = 2 and e ≥ 3 in which case λ(2e ) = 2e−2 instead of 2e−1 . For more
information, see [Ros1, Section 9.6].
One can simplify the computations in the above solution by using λ(n) in place of
φ(n): iteration of λ maps 100 to 20 to 4 to 2, so starting from ai−3 ≡ 1 (mod 2) we
obtain
ai−2 = 3ai−3 ≡ 31 ≡ 3 (mod 4)
ai−1 = 3 ai−2
≡3 ≡73
(mod 20)
ai =3 ai−1
≡ 3 ≡ 87
7
(mod 100).
58 The William Lowell Putnam Mathematical Competition
Stronger result. More generally, one can show that for any integer c ≥ 1, the
sequence defined by a1 = c and ai+1 = cai for i ≥ 1 is eventually constant when
reduced modulo a positive integer n. To prove this, one can use the Chinese Remainder
Theorem to reduce to the case where n is a power of a prime p. If p divides c, then
the sequence is eventually 0 modulo n; otherwise we can use Euler’s Theorem and
strong induction on n, since φ(n) < n for n > 1. See 1997B5 for a related problem,
and further discussion.
where the sum ranges over the 2 m-tuples (C1 , . . . , Cm ) with Ck = ±1 for each k. For
m
integers t, ,
2π
itx 2π, if t = 0
e dx =
0 0, otherwise.
Thus Im = 0 if and only 0 can be written as
C1 + 2C2 + · · · + mCm
for some C1 , . . . , Cm ∈ {1, −1}. If such Ck exist, then
m(m + 1)
0 = C1 + 2C2 + · · · + mCm ≡ 1 + 2 + · · · + m = (mod 2)
2
so m(m + 1) ≡ 0 (mod 4), which forces m ≡ 0 or 3 (mod 4). Conversely, if m ≡ 0
(mod 4), then
0 = (1 − 2 − 3 + 4) + (5 − 6 − 7 + 8) + · · · + ((m − 3) − (m − 2) − (m − 1) + m),
and if m ≡ 3 (mod 4),
0 = (1 + 2 − 3) + (4 − 5 − 6 + 7) + (8 − 9 − 10 + 11) + ((m − 3) − (m − 2) − (m − 1) + m).
Thus Im = 0 if and only m ≡ 0 or 3 (mod 4). The integers m between 1 and 10
satisfying this condition are 3, 4, 7, 8.
Reinterpretation. This is a question in Fourier analysis. The function
cos(x) cos(2x) · · · cos(mx)
is continuous and periodic with period 2π, so it can be written as a Fourier series
∞ ∞
cos(x) cos(2x) · · · cos(mx) = a0 + bj cos(jx) + ck sin(kx).
j=1 k=1
The question asks: For which integers m between 1 and 10 is a0 nonzero? By similar
methods, one can show that:
Solutions: The Forty-Sixth Competition (1985) 59
and γ(p(x)q(x)) = γ(p(x))γ(q(x)) for any polynomials p(x) and q(x), we find
γ(f (x)n ) = γ((3x + 1)n )γ((x + 2)n ) = γ((3x + 1)n )γ((1 + 2x)n ) = γ(g(x)n ),
where g(x) = (3x + 1)(1 + 2x) = 6x2 + 5x + 1. Taking coefficients of x0 , we obtain
Γ(f (x)n ) = Γ(g(x)n ). Moreover g(0) = 1, so we are done.
i
j
Remark. One could also show by brute force that Γ ( ai x )( bj x ) is un-
changed by reversing the order of the bj , without mentioning γ or Laurent polynomials.
The coefficient of x0 in a Laurent polynomial can also be expressed as a contour
integral, via the residue theorem; hence one could begin a solution with the observation
-
1 dz
Γ(p(x)) = p(z)p(z −1 ) .
2πi |z|=1 z
Remark. The solution is not unique: for any integer k ≥ 1, the polynomials
g(x) = (3xk + 1)(2xk + 1) and g(x) = (3xk − 1)(2xk − 1) also have the desired
properties. We do not know if these are the only ones. Using the fact that the ring
R[x, 1/x] of Laurent polynomials is a unique factorization domain (UFD), we could
prove that these are the only ones if we could prove the following conjecture of Greg
Kuperberg (communicated electronically):
Suppose h1 , h2 ∈ R[x, 1/x] satisfy h1 (x) = h1 (1/x) and h2 (x) = h2 (1/x).
Then the following are equivalent:
60 The William Lowell Putnam Mathematical Competition
Solution. Let p = (cos θ, sin θ) and q = (a, b). The other two vertices of R are
(cos θ, b) and (a, sin θ). If |a| ≤ | cos θ| and |b| ≤ | sin θ|, then each vertex (x, y) of
R satisfies x2 + y 2 ≤ cos2 θ + sin2 θ = 1, and no points of R can lie outside of C.
Conversely, if no points of R lies outside of C, then applying this to the two vertices
other than p and q, we find
or equivalently
These conditions imply that (a, b) lies inside or on C, so for any given θ, the probability
that the random point q = (a, b) satisfies (1) is
2| cos θ| · 2| sin θ| 2
= | sin(2θ)|,
π π
and the overall probability is
2π π/2
1 2 4 4
| sin(2θ)| dθ = 2 sin(2θ) dθ = 2 .
2π 0 π π 0 π
The integral converges, since the integrand is bounded by t−1/2 on (0, 1] and by e−at
on [1, ∞). Hence
0 B 1
1
−1/2 −a(t+t−1 ) −1/2 −a(t+t−1 )
I(a) = lim t e dt + t e dt .
B→∞ 1/B 1
for Re(z) > 0 [O, p. 250]. When ν = 1/2, the substitution u = et relates this to
expressions occurring in the solution above; to be precise, I(a) = 2K1/2 (2a) for all
π −z
a > 0. Thus K1/2 (z) = 2z e for z > 0. Similar formulas exist for Kn+1/2 (z) for
each integer n. For arbitrary ν, the function w = Kν (z) is a solution of the differential
equation
z 2 w + zw − (z 2 + ν 2 )w = 0.
3200 9100
= < 1.
10100 + 3 10100 + 3
By (1),
I ≡ −3199 ≡ −33 (81)49 ≡ −27 ≡ 3 (mod 10),
so the units digit of I is 3.
xy ≥ 1. Verifying the xy ≥ 1 condition at each step, we use (1) to compute the first
few partial sums
Arccot 1 = Arccot 1
Arccot 1 + Arccot 3 = Arccot(1/2)
Arccot 1 + Arccot 3 + Arccot 7 = Arccot(1/3),
m−1
and guess that n=0 Arccot(n2 + n + 1) = Arccot(1/m) for all m ≥ 1. This is easily
proved by induction on m: the base case is above, and the inductive step is
m m−1
Arccot(n2 + n + 1) = Arccot(m2 + m + 1) + Arccot(n2 + n + 1)
n=0
n=0
2 1
= Arccot(m + m + 1) + Arccot (inductive hypothesis)
m
2
(m + m + 1)/m − 1
= Arccot (by (1))
m2 + m + 1 + 1/m
1
= Arccot .
m+1
Hence
∞
1
2
Arccot(n + n + 1) = lim Arccot = Arccot(0) = π/2.
n=0
m→∞ m
The first is problem 26 of [WH], and both appeared in a problem due to J. Anglesio
in the Monthly [Mon3, Mon5].
Literature note. The value
ofseries such as these have been known for a long time.
∞
In particular, n=1 Arctan n22 and some similar series were evaluated at least as
early as 1878 [Gl]. Ramanujan [Berndt, p. 37] independently evaluated this and other
Solutions: The Forty-Seventh Competition (1986) 67
either (0, . . . , 0) or (−1, ..., −1), by the Lemma and condition (a), so there are 2n−1
possibilities for these rows. This gives a total of 2n−1 (2n − 2) possibilities in this case.
68 The William Lowell Putnam Mathematical Competition
Case 3: both 0 and −1 appear in the first row, but not 1. These are just the negatives
of the matrices in case 2, so we again have 2n−1 (2n − 2) possibilities.
Case 4: Both 1 and −1 (and possibly also 0) appear in the first row. This covers
all other possibilities for the first row, i.e., the remaining 3n − 2 · 2n + 1 possibilities.
Then every row must be equal to the first, by the Lemma and condition (a), so we
have a total of 3n − 2 · 2n + 1 possibilities in this case.
Adding the four cases gives f (n) = 4n + 2 · 3n − 4 · 2n + 1.
Related question.
If an n × n matrix M with nonnegative integer entries satisfies condition (b),
that the sum of the n entries of a transversal is the same number m for all
transversals of A, show that M is the sum of m permutation matrices. (A
permutation matrix is a matrix with one 1 in each row and each column, and
all other entries 0.)
For a card trick related to this result, see [Kl].
This result is a discrete version of the following result.
Birkhoff-von Neumann Theorem. The convex hull of the permutation matrices
is precisely the set of doubly stochastic matrices: matrices with entries in [0, 1] with
each row and column summing to 1.
a0 + a1 x1 + a2 x2 + · · · + an xn .)
Solution. Note that cij = −cji for all i and j. Let hi = 1
2 j cij xj , so
1
∂hi /∂xj = 2 cij . Then
∂hi ∂hj 1 1 ∂fi ∂fj
− = cij − cji = cij = − ,
∂xj ∂xi 2 2 ∂xj ∂xi
so
∂(hi − fi ) ∂(hj − fj )
=
∂xj ∂xi
for all i and j. Hence (h1 − f1 , . . . , hn − fn ) is a gradient, i.e., there is a differentiable
function g on Rn such that ∂g/∂xi = hi − fi for each i. Then fi + ∂g/∂xi = hi is
linear for each i.
Solutions: The Forty-Seventh Competition (1986) 69
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 ).
Answer. The number f (1) equals b1 b2 · · · bn /n!.
0=1+ ai ,
0= ai bi ,
0= ai (bi )2 ,
..
.
0= ai (bi )n−1 ,
bn−1
1 bn−1
2 · · · bn−1
n bn1 bn2 ··· bnn
Factoring bi out of the ith column of V shows that det(V ) = b1 b2 · · · bn det(V ).
Hence −b1 b2 · · · bn det(V ) + n!f (1) det(V ) = 0. Since the bi are distinct, det(V ) = 0
(see below). Thus f (1) = b1 b2 · · · bn /n!.
Remark (The Vandermonde determinant). The matrix V is called the Vandermonde
matrix. Its determinant D is a polynomial of total degree n2 in the bi , and D vanishes
whenever bi = bj for i > j, so D is divisible by bi − bj whenever i > j. These bi − bj
3
have no common
factor, so i>j (bi − bj ) divides D. But this product also has total
3
degree n2 , and the coefficient of b2 b23 · · · bn−1 in D and in i>j (bi − bj ) both equal
3 n
1, so D = i>j (bi − bj ). In particular, if the bi are distinct numbers, then D = 0.
See Problem 1941/14(ii) [PutnamI, p. 17] for an extension, and 1999B5 for another
application.
Solution 2. Subtract 1 from both sides, set x = et , and expand the left-hand side
in a power series. Since 1 − et = t + (higher order terms), we get
n
−1 + (−1)n f (1)tn + (higher order terms) = ai e b i t . (1)
i=1
B1. (183, 3, 7, 0, 0, 0, 0, 0, 4, 2, 1, 1)
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?†
Answer. The only such value of h is 2/5.
Solution. The radius OX (see Figure 3) has length equal to h/2 plus the altitude
of the triangle, so the altitude of the triangle is 1 − h/2. If the rectangle and triangle
have the same area, then bh = 12 b(1 − h/2). Cancel b and solve for h to get h = 2/5.
† The figure is omitted here, since it is almost identical to Figure 3 used in the solution.
Solutions: The Forty-Seventh Competition (1986) 71
h O
FIGURE 3.
Solution. Subtracting y(y − 1) + 2zx from x(x − 1) + 2yz, z(z − 1) + 2xy from
y(y − 1) + 2zx, and x(x − 1) + 2yz from z(z − 1) + 2xy, we find that the given system
is equivalent to
(x − y)(x + y − 1 − 2z) = 0
(y − z)(y + z − 1 − 2x) = 0
(z − x)(z + x − 1 − 2y) = 0.
so pk (∆2 Fk +∆1 Gk ) ≡ pk t (mod pk+1 ), and Fk+1 Gk+1 ≡ Fk Gk +pk t = h (mod pk+1 ),
completing the inductive step.
Remark. This problem is a special case of a version of Hensel’s Lemma [Ei,
p. 208], a fundamental result in number theory. Here is a different version [NZM,
Theorem 2.23], which can be thought of as a p-adic analogue of Newton’s method for
solving polynomial equations via successive approximation:
Hensel’s Lemma. Suppose that f (x) is a polynomial with integral coefficients. If
f (a) ≡ 0 (mod pj ) and f (a) ≡ 0 (mod p), then there is a unique t (mod p) such that
f (a + tpj ) ≡ 0 (mod pj+1 ).
p2 + rpq + q 2 = x2 + y 2 + z 2 + xyz − r2 .
The quadratic form in p, q on the left must take on negative values, since the right-hand
side is negative for x, y, and z chosen equal and sufficiently negative. Thus its
discriminant ∆ = r2 − 4 is positive, so |r| > 2. The right-hand side is irreducible
in R[x, y, z], since as a polynomial in z it is a monic quadratic with discriminant
∆ = (xy)2 − 4(x2 + y 2 − r2 ) which cannot be the square of any polynomial, since
∆ as a quadratic polynomial in x has nonzero x2 and x0 coefficients but zero x1
coefficient. Therefore the factorization (p − αq)(p − βq) of the left-hand side matches
a trivial factorization of the right-hand side, so (p, q, r) is a solution of the second type
described above.
It remains to consider the case deg p < 2. Then p, q, r are at most linear. Equating
the homogeneous degree 3 parts in
p2 + q 2 + r2 + pqr = x2 + y 2 + z 2 + xyz
x2 + y 2 + z 2 = 3xyz
are exactly those obtained from (1, 1, 1) by iterations of (x, y, z) !→ (x, y, 3xy − z)
and permutations. For the connection of this equation to binary quadratic forms and
continued fractions and much more, see [CF]. For an unsolved problem about the set
of solutions, see [Guy, p. 166].
Related question. The key idea in this problem is also essential to the solution to
Problem 6 of the 1988 International Mathematical Olympiad [IMO88, p. 38]:
Let a and b be positive integers such that ab + 1 divides a2 + b2 . Show that
a2 +b2
ab+1 is the square of an integer.
Taking the transpose of (3) gives DAt −CB t = I. These four equations are the entries
in the block matrix identity
t
A B D −B t I 0
= .
C D −C t At 0 I
(Here the matrices should be considered (2n) × (2n) matrices in the obvious way.) If
X, Y are m × m matrices with XY = Im , the m × m identity matrix, then Y = X −1
and Y X = Im too. Applying this to our product with m = 2n, we obtain
t
D −B t A B I 0
= ,
−C t At C D 0 I
and equating the lower right blocks shows that −C t B + At D = I, as desired.
76 The William Lowell Putnam Mathematical Competition
Prove that A ∩ B = C ∩ D.
Solution 1. Let z = x + iy. The equations defining A and B are the real and
imaginary parts of the equation z 2 = z −1 + 3i, and similarly the equations defining C
and D are the real and imaginary parts of z 3 − 3iz = 1. Hence for all real x and y,
we have
Thus A ∩ B = C ∩ D.
Solution 2. Let F = x2 −y 2 − x2 +y
x
2 , G = 2xy + x2 +y 2 −3, H = x −3xy +3y −1,
y 3 2
123456789101112131415161718192021 . . .
† The equations defining A and B are indeterminate at (0, 0). The point (0, 0) belongs to neither.
Solutions: The Forty-Eighth Competition (1987) 77
100th digit enters the sequence in the placement of the two-digit integer
55. Find, with proof, f (1987).
Answer. The value of f (1987) is 1984.
Solution. Let g(m) denote the total number of digits in the integers with m or
fewer digits. Then f (n) equals the integer m such that g(m − 1) < 10n ≤ g(m).
m
There are 10r −10r−1 numbers with exactly r digits, so g(m) = r=1 r(10r −10r−1 ).
We have 1983
g(1983) ≤ 1983(10r − 10r−1 ) ≤ 1983 · 101983 < 101987
r=1
and
g(1984) ≥ 1984(101984 − 101983 ) = 1984 · 9 · 101983 > 104 · 101983 = 101987
so f (1987) = 1984.
Motivation. Based on the growth of geometric series one might guess that g(m)
has size roughly equal to its top term, which is 9 · m · 10m−1 . Thus we seek m such
that 9 · m · 10m−1 ≈ 101987 . Using 9 ≈ 10, the condition becomes m ≈ 101987−m . This
leads to the guess m = 1984, since 1984 ≈ 103 .
Remark. There is a closed form for g(m):
m m
g(m) = r10r − r10r−1
r=1 r=1
m m−1
= r10r − (s + 1)10s
r=1 s=0
4 m−1
5 m−1
= m10 + m
r10 r
− (s + 1)10s
r=0 s=0
m−1
= m10m − 10s
s=0
= m10m − (10m − 1)/9.
b
More generally, there is a closed form for r=a P (r)xr for any integers a ≤ b, fixed
polynomial P , and number x. Rearrangement as above shows that
b b
(1 − x) P (r)xr = P (a)xa − P (b)xb+1 + (P (r) − P (r − 1))xr ,
r=a r=a+1
and the last sum is of the same type but with a polynomial P (r) − P (r − 1) of lower
degree than P , or zero if P was constant to begin with. Hence one can evaluate the
sum by induction on deg P .
b r
Alternatively, r=a P (r)x can be evaluated by repeatedly differentiating the
formula for the geometric series
b
xb+1 − xa
xr =
r=a
x−1
and taking linear combinations of the resulting identities.
78 The William Lowell Putnam Mathematical Competition
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.
is positive, we have
Similarly
∞ a(n) 3
The given series n=1 x /n has all terms positive, so it will converge if and
∞
only if S converges. For 3k ≤ n < 3k+1 , we have 33k ≤ n3 < 33k+3 , so
k=0 k
∞ ∞
Tk /3 3k+3
≤ Sk ≤ Tk /3 . Therefore k=0 Sk converges if and only if k=0 Tk /33k
3k
converges.
k k+1−i
The number of n with
k
k + 1 digits base 3 and satisfying a(n) = i is
i 2 , because there are i possibilities for the set of positions of the i zero
digits (since the leading digit cannot be zero), and then 2k+1−i ways to select 1 or 2
as each of the remaining digits. Therefore
k
k k+1−i i
Tk = 2 x = (x + 2)k .
i=0
i
Hence k
∞ ∞
x+2
Tk /33k = ,
27
k=0 k=0
which converges if and only if |(x + 2)/27| < 1. For positive x, this condition is
equivalent to 0 < x < 25.
Remark. More generally, let αk (n) be the number of zeros in the base k expansion
∞ αk (n) k
of n, and let Ak (x) = n=1 x /n . Then Ak (x) converges at a positive real
number x if and only if x < kk − k + 1.
Literature note. For more other convergent sums involving digits in base b
representations, see [BB]. This article contains exact formulas for certain sums, as
well as approximations by “nice” numbers that agree to a remarkable number of
decimal places.
Solution. The integrand is continuous on [2, 4]. Let I be the value of the integral.
As x goes from 2 to 4, 9 − x and x + 3 go from 7 to 5, and from 5 to 7, respectively.
This symmetry suggests the substitution x = 6 − y reversing the interval [2, 4]. After
interchanging the limits of integration, this yields
4
ln(y + 3) dy
I= .
2 ln(y + 3) + ln(9 − y)
Thus
4
ln(x + 3) + ln(9 − x) 4
2I = dx = dx = 2,
2 ln(x + 3) + ln(9 − x) 2
and I = 1.
√
Remark. The same argument applies if ln x is replaced by any continuous function
such that f (x + 3) + f (9 − x) = 0 for 2 ≤ x ≤ 4.
Solutions: The Forty-Eighth Competition (1987) 81
We will show that both sides of (3) count the number of sequences of s zeros and
t − s ones, punctuated by a comma such that the number of ones occurring before the
comma is r. On one hand, the number of such
sequences of t + 1 symbols (including
the comma) equals the right-hand side t+1s of (3), because they can be constructed
by choosing the s positions for the zeros: of the remaining positions, the (r + 1)st
must contain the comma and the others must contain ones. On the other hand, we
can count the sequences according to the position of the comma: given that there are
Solutions: The Forty-Eighth Competition (1987) 83
exactly j digits before the comma, there are rj possibilities for the digits before
t−jthe
comma (since r of them are to be ones and the rest are to be zeros), and t−r−s
possibilities for the digits after the comma (since one needs t − r − s more ones to
bring the total number of ones to t − s). Summing over j shows that the total number
of sequences is the left-hand side of (3).
Motivation. To find the generating function solution, first observe that the sum
in (1) looks like the coefficient of xs in a product of two series, and then figure out
what the two series must be.
Remark. Vandermonde’s identity can also be used in 1991B4.
Literature note. Generating functions are a powerful method for proving combi-
natorial identities. A comprehensive introduction to this method is [Wi].
Related question. Problem 20 of [WH] is similar:
Evaluate the sum n n
S= 2n−1
k
k=0 k
2 2
x +y =1
(1, 0)
(x, y)
FIGURE 4.
Points with coordinates in F correspond to lines through (1, 0) with slopes in F .
If Ls is the line through (1, 0) with slope s ∈ F , its intersection with x2 + y 2 = 1 can
be computed by substituting y = s(x − 1) into x2 + y 2 = 1, and solving the resulting
equation
x2 + s2 (x − 1)2 = 1.
This equation is guaranteed to have the solution x = 1, because (1, 0) is in the
intersection. Therefore we obtain a factorization,
(x − 1) (s2 + 1)x + (1 − s2 ) = 0,
which yields the solutions x = 1 and, if s2 = −1, also x = (s2 − 1)/(s2 + 1). (If
s2 = −1, then 1 − s2 = −2 = 0, and the second " 2 factor gives
# no solution.) Using
s −1 −2s
y = s(x − 1), we find that these give (1, 0) and s2 +1 , s2 +1 , which, as we verify, do
satisfy x2 + y 2 = 1 and y = s(x − 1). We finish by substituting s = −r.
Remark. Let C be any nondegenerate conic over F with an F -rational point P :
this means that C is given by a polynomial f (x, y) ∈ F [x, y] of total degree 2 that does
not factor into linear polynomials over any field extension of F , and P = (a, b) ∈ F 2
is a point such that f (a, b) = 0. The same method (of drawing all lines through P
with slope in F , and seeing where they intersect f (x, y) = 0 other than at P ) lets one
parameterize the set of F -rational points of C in terms of a single parameter s. In the
language of algebraic geometry, one says that any conic over k with a k-rational point
is birationally equivalent to the line [Shaf, p. 11]. The same method works on certain
equations of higher degree [NZM, Section 5.6].
The parameterization in the preceding paragraph is the reason why indefinite
integrals of rational functions in t and p(t) for a single quadratic polynomial p(t)
can be expressed in terms of elementary functions [Shaf, p. 7]. It also explains why
sin θ and cos θ can be expressed as rational functions of a single function:
1 − t2 2t
(cos θ, sin θ) = , where t = tan(θ/2).
1 + t2 1 + t2
This, in turn, explains why rational functions in sin θ and cos θ, such as
sin3 θ − 7 sin θ cos θ
,
1 + cos3 θ
have elementary antiderivatives.
Solutions: The Forty-Eighth Competition (1987) 85
Solution.
Write M = A + iB where A and B are real 2n × n matrices. If
z = z1 z2 · · · z2n is a row vector with real entries such that
z A B = 0, then
zM = zA + izB = 0, so z = 0 by hypothesis. Hence A B is an invertible real
2n × 2n matrix.
Let r be the real column vector (r1 , . . . , r2n ). If w is a complex column vector
of length n, and we write w = u + iv where u and v are the real and imaginary
the condition Re [M w] = r is equivalent to Au − Bv = r, and to
parts of w, then
u
A B = r. Since A B is invertible, we can find a real column vector
−v
u
satisfying this.
−v
We write 2S for { 2a : a ∈ S }.
Solution 1. For a ∈ S, there is a unique way to write 2a = Ca sa where Ca = ±1
3
and sa ∈ S. Then S ∩ 2S = { a ∈ S : Ca = 1 }, so a∈S Ca = (−1)#S−N = (−1)N ,
since #S = (p − 1) · (p + 1)/2 is even. In F , we have
2 + + +
2(p −1)/2 a= Ca sa = (−1)N a
a∈S a∈S a∈S
† This lemma rarely appears outside the context of the proof of quadratic reciprocity. It should not
be confused with the more important result called Gauss’s Lemma that is stated after Solution 3 to
1998B6.
Solutions: The Forty-Eighth Competition (1987) 87
Case In S ∩ 2S? N − N
α 2α −α −2α
(1) α/2 ∈ S, 2α ∈ S yes yes no no −2
(2) α/2 ∈ S, −2α ∈ S yes no no yes 0
(3) −α/2 ∈ S, 2α ∈ S no yes yes no 0
(4) −α/2 ∈ S, −2α ∈ S no no yes yes 2
In each row of the table, N − N equals the number of times “yes” appears under the
−α and −2α headers minus the number of times “yes” appears under the α and 2α
headers. Hence N − N is even in each case, as desired.
Related question. The following problem, proposed by Iceland for the 1985 Inter-
national Mathematical Olympiad, is susceptible to the approach of the second solution.
Suppose x1 , . . . , xn ∈ {−1, 1}, and
x1 x2 x3 x4 + x2 x3 x4 x5 + · · · + xn−3 xn−2 xn−1 xn
+ xn−2 xn−1 xn x1 + xn−1 xn x1 x2 + xn x1 x2 x3 = 0.
Show that n is divisible by 4.
88 The William Lowell Putnam Mathematical Competition
A1. (202, 0, 0, 0, 0, 0, 0, 0, 4, 2, 0, 0)
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.
Remark. For this problem, the average of the scores of the top 200 or so participants
was approximately 9.76, higher than for any other problem in this volume. The second
easiest problem by this measure was 1988B1, from the same year, with an average of
9.56. At the other extreme, the average for each of 1999B4 and 1999B5 was under
0.01.
Answer. The area of R is 6.
(–2, 1) (2, 1)
(–1, 0) (1, 0)
x
FIGURE 5.
The region R.
" # We are asked for a solution g to f g + gf = f g 2, which is equivalent
Solution.
to g + f −f g = 0 if we avoid the zeros of f − f = (1 − 2x)ex , i.e., avoid x = 1/2.
f
By the existence and uniqueness theorem for first order linear ordinary differential
equations [BD, Theorem 2.4.1], if x0 = 1/2, and y0 is any real number, then there exists
a unique solution g(x), defined in some neighborhood (a, b) of x0 , with g(x0 ) = y0 .
By taking y0 nonzero, we obtain a nonzero solution g.
Remark. One can solve the differential equation by separation of variables, to find
all possible g. If g is nonzero, the differential equation is equivalent to
2
g f 2xex 1
= = 2 = 1 + ,
g f −f (2x − 1)e x 2x − 1
1
ln |g(x)| = x + ln |2x − 1| + c,
2
from which one finds that the nonzero solutions are of the form g(x) = Cex |2x − 1|1/2
for any nonzero number C, on any interval not containing 1/2.
Related question. What other pairs of functions f and g satisfy (f g) = f g ? For
some discussion, see [Hal, Problem 2G].
1
= −1
1 − 6n2 + O n14
1
1 1
= 2 +O .
6n n4
In particular, if bn = 1/n2 , then axn /bxn has a finite limit as n → ∞, so by the
∞ x
Limit Comparison Test [Spv, Ch. 22, Theorem 2], n=1 an converges if and only
∞ x ∞ −2x
if n=1 nb = n=1 n converges, which by the Integral Comparison Test [Spv,
Ch. 22, Theorem 4] holds if and only if 2x > 1, i.e., x > 1/2.
Remark (big-O and little-o notation). Recall that O(g(n)) is a stand-in for a
function f (n) for which there exists a constant C such that |f (n)| ≤ C|g(n)| for all
sufficiently large n. (This does not necessarily imply that limn→∞ f (n)/g(n) exists.)
90 The William Lowell Putnam Mathematical Competition
Similarly “f (t) = O(g(t)) as t → 0” means that there exists a constant C such that
|f (t)| ≤ C|g(t)| for sufficiently small nonzero t.
On the other hand, o(g(n)) is a stand-in for a function f (n) such that
f (n)
lim = 0.
n→∞ g(n)
One can similarly define “f (t) = o(g(t)) as t → 0”.
A B
FIGURE 6.
(a) Suppose, for the sake of obtaining a contradiction, that we have a coloring of the
plane with three colors such that any
√ two points at distance 1 have different colors. If
A and B are two points at distance 3, then the circles of radius 1 centered at A and B
meet in two points P, Q forming equilateral triangles AP Q and BP Q. (See Figure 6.)
The three points of each equilateral triangle have different colors, and this forces
√ A
and B to have equal colors. Now consider a triangle CDE with CD = CE = 3 and
DE = 1. (See Figure 7.) We know that C, D have the same color and C, E have the
same color, so D, E have the same color, contradicting our hypothesis about points at
distance 1.
D
3
C 1
3
E
FIGURE 7.
Color the nine elements of {0, 1, 2}2 with the nine different colors, and give P the
color of f (P ). (Thus the plane is covered by blocks of 3 × 3 squares, where the little
squares have side length 2/3. See Figure 8.) If P and Q are points with the √ same
color, either they belong to the same little square, in which case P Q ≤ (2/3) 2 < 1,
or to different little squares. In the latter case, either their x-coordinates differ by at
least 4/3, or their y-coordinates differ by at least 4/3, so P Q ≥ 4/3 > 1.
3/2
(0, 0) (1, 0) (2, 0) (0, 0)
FIGURE 8.
Remark. Part (a) appears in [New, p. 7], as does the following variation:
Assume that the points of the plane are each colored red or blue. Prove that
one of these colors contains pairs of points at every distance.
Remark. Figure 9 shows a well-known coloring of the plane with seven colors
such that points at distance 1 always√have different colors. Such a coloring can be
constructed as follows. Let ω = −1+2 −3 , and view the ring of Eisenstein integers
Z[ω] = { a + bω : a, b ∈ Z } as a lattice in the complex plane. Then p = (2 − ω)Z[ω]
is a sublattice of index |2 − ω|2 = 7. (In fact, p is one of the two prime ideals of Z[ω]
that divide (7).) Give each coset of p in Z[ω] its own color. Next color each point in
C according to the color of a nearest point
in Z[ω]. This gives a coloring by hexagons.
The diameter of each hexagon equals 4/3, and if two distinct hexagons have the
same
color, the
smallest distance between points of their closures is 7/3. Hence if
4/3 < d < 7/3, no two points in the plane at distance d have the same color.
Scaling the whole picture by 1/d, we find a coloring in which no two points in the
plane at distance 1 have the same color.
Remark. Let χ(n) denote the minimum number of colors needed to color the
points in Rn so that each pair of points separated by distance 1 have different colors.
Parts (a) and (b) show χ(2) > 3 and χ(2) ≤ 9, respectively. Because of the hexagonal
92 The William Lowell Putnam Mathematical Competition
✧✧❜❜✧✧❜❜✧✧❜❜✧✧❜❜✧✧❜❜✧✧❜❜
A B C D E F
✧✧❜❜✧
❜❜✧ ❜✧✧❜❜✧ ❜✧✧❜❜
❜✧✧❜❜✧ ❜✧✧✧❜❜✧
❜ ✧
F G A B C
✧✧❜❜
❜✧✧✧❜❜✧
❜✧✧❜❜
❜✧✧✧❜❜✧ ❜✧✧❜❜
❜✧✧❜❜✧
C D E F G A
❜❜✧
✧✧❜❜✧
❜✧✧❜❜✧
❜✧✧❜❜✧
❜✧✧❜❜
❜✧✧✧❜❜✧
❜ ✧
A B C D E
✧✧❜❜
❜✧ ❜✧✧❜❜
✧✧❜❜✧ ❜✧✧✧❜❜✧ ❜✧✧❜❜
❜✧✧❜❜✧
E F G A B C
❜❜✧✧❜❜✧✧❜❜✧✧❜❜✧✧❜❜✧✧❜❜✧✧
FIGURE 9.
Solution. We will show that f (x) = 2x for x > 0. Fix x > 0, and consider the
sequence (an ) of positive numbers defined by a0 = x and an+1 = f (an ). The given
functional equation implies that an+2 +an+1 −6an = 0. The zeros of the characteristic
polynomial t2 + t − 6 of this linear recursion are −3 and 2, so there exist real constants
c1 , c2 such that an = c1 2n + c2 (−3)n for all n ≥ 0. If c2 = 0, then for large n, an has
the same sign as c2 (−3)n , which alternates with n; this contradicts an > 0. Therefore
c2 = 0, and an = c1 2n . In particular f (x) = a1 = 2a0 = 2x. This holds for any x.
Finally, the function f (x) = 2x does satisfy the conditions of the problem.
Related question. The following, which was Problem 5 of the 1989 Asian-Pacific
Mathematical Olympiad [APMO], can be solved using a similar method:
Determine all functions f from the reals to the reals for which
(1) f (x) is strictly increasing,
(2) f (x) + g(x) = 2x for all real x,
Solutions: The Forty-Ninth Competition (1988) 93
where g(x) is the composition inverse function to f (x). (Note: f and g are
said to be composition inverses if f (g(x)) = x and g(f (x)) = x for all real x.)
Remark (linear recursive sequences with constant coefficients). We can describe the
general sequence x0 , x1 , x2 , . . . satisfying the linear recursion
over a field large enough to contain all its zeros. If the zeros r1 , . . . , rk of f (t)
k
are distinct, then the general solution is xn = i=1 ci rin where the ci are arbitrary
3s
i=1 (t − ri )
mi
constants not depending on n. More generally, if f (t) = , then,
provided that we are working over a field of characteristic zero, the general solution
s
is xn = i=1 ci (n)rin where ci (n) is a polynomial of degree less than mi . For any
characteristic, the latter statement remains true if we replace the polynomial
ci (n)
by a general linear combination of the binomial coefficients n0 , n1 , . . . , min−1 .
(These combinations are the same as the polynomials in n of degree less than mi if
the characteristic is zero, or if the characteristic is at least as large as mi .) All of
∞
these statements can be proved by showing that the generating function i=0 xi ti is
a rational function of t, and then decomposing it as a sum of partial fractions and
expanding each partial fraction in a power series to get a formula for xi . For more
discussion, see [NZM, Appendix A.4].
For example, these results can be used to show that the Fibonacci sequence, defined
by F0 = 0, F1 = 1, and Fn+2 = Fn+1 + Fn for n ≥ 0, satisfies
" √ #n " √ #n
1+ 5
2 − 1−2 5
Fn = √ .
5
The formula for the general solution to linear recursions with constant coefficients
can be thought of as the discrete analogue of the general solution to homogeneous
linear ordinary differential equations with constant coefficients.
a diagonal matrix with equal entries on the diagonal, so A is a scalar multiple of the
identity.
Remark. One could have worked with the multiset of roots of the characteristic
polynomial, instead of their sum (the trace).
Solution 2 (Lenny Ng). Let x1 , . . . , xn+1 be the eigenvectors of A, with
eigenvalues λ1 , . . . , λn+1 . Since x1 , . . . , xn are linearly independent, they span the
vector space; hence
n
xn+1 = αi xi
i=1
Thus αi λn+1 = αi λi for all i between 1 and n. If αi = 0 for some i, then xn+1 can
be expressed as a linear combination of x1 , . . . , xi−1 , xi+1 , . . . , xn , contradicting the
linear independence hypothesis. Hence αi = 0 for all i, so λn+1 = λi for all i. This
implies A = λn+1 I.
[Wh], and [Mord2, p. 291]. The GRH implies the nonexistence of a Siegel zero for the
Dirichlet L-functions associated to these fields, and this is what is used in the proof
of Theorem 1.1 of [BC].
in which 0 and ∗ represent blocks of size (2n − 1) × 2 and 2 × (2n − 1), respectively.
Thus rank(Mn ) = 2 + rank(Mn−1 ) = 2 + 2(n − 1) = 2n.
so
Now, (a) implies RS(Mn ) ⊆ V , and (b) and (c) imply V ⊆ RS(Mn ). Thus
RS(Mn ) = V . Hence rank(Mn ) = dim V = 2n.
Solution 3. The matrix is circulant, i.e., the entry mij depends only on j − i
modulo 2n + 1. Write aj−i = mij , where all subscripts are considered modulo 2n + 1.
(Thus ai equals 0, −1, 1 according as i = 0, 1 ≤ i ≤ n, or n + 1 ≤ i ≤ 2n.) For each
of the 2n + 1 complex numbers ζ satisfying ζ 2n+1 = 1, let vζ = (1, ζ, ζ 2 , . . . , ζ 2n ).
The vζ form a basis for C2n+1 , since they are the columns of a Vandermonde matrix
with nonzero determinant: see 1986A6. Since Mn is circulant, Mn vζ = λζ vζ where
λζ = a0 + a1 ζ + · · · + a2n ζ 2n . Thus { λζ : ζ 2n+1 = 1 } are all the eigenvalues of Mn
Solutions: The Forty-Ninth Competition (1988) 99
for k = 0, 1, . . . , 9 its value is 22(−1)k + 20 cos(4θ), which has the sign of (−1)k . By
the Intermediate Value Theorem [Spv, Ch. 7, Theorem 5], p(eiθ ) has at least one zero
between θ = 2πk/10 and θ = 2πi(k + 1)/10 for k = 0, . . . , 9; this makes at least 10
zeros. Thus g(z) also has at least 10 zeros on the circle |z| = 1, and these are all the
zeros since g(z) is of degree 10.
Solution 3. Rouché’s Theorem [Ah, p. 153] states that if f and g are analytic
functions on an open set containing a closed disc, and if |g(z) − f (z)| < |f (z)|
everywhere on the boundary of the disc, then f and g have the same number of
zeros inside the disc. Let f (z) = 10iz − 11 and g(z) = 11z 10 + 10iz 9 + 10iz − 11, and
consider the discs |z| ≤ α with α ∈ (0, 1). Then
|g(z) − f (z)| = |11z 10 + 10iz 9 | = |z|9 |11z + 10i| < |10iz − 11| = |f (z)|
if |z| < 1, by the same calculation as in Solution 2. But f has its only zero at 11/(10i),
outside |z| = 1, so g has no zeros with |z| < α for any α ∈ (0, 1), and hence no zeros
with |z| < 1. Finally, g(−1/z) = −z −10 g(z), so the nonvanishing of g for |z| < 1
implies the nonvanishing of g for |z| > 1. Therefore, if g(z) = 0, then |z| = 1.
Similarly, say that player 2 wins after N tosses, if it is guaranteed then that X will
be greater than α.
Solutions: The Fiftieth Competition (1989) 103
The game will terminate if X = α, which happens with probability 1; in fact it will
terminate at the N th toss or earlier if |X − α| > 1/2N . The probability that player 1
wins is the probability that X ∈ [0, α), which is α.
Remark. The solution shows that the answer is yes for all real α ∈ [0, 1]: there is
no need to assume that α is irrational.
Remark. Essentially the same idea appears in [New, Problem 8]:
Devise an experiment which uses only tosses of a fair coin, but which has
success probability 1/3. Do the same for any success probability p, 0 ≤ p ≤ 1.
Related question. Show that if α ∈ [0, 1] is not a dyadic rational (i.e., not a rational
number with denominator equal to a power of 2), the expected number of tosses in
the game in the solution equals 2.
Related question. For α ∈ [0, 1], let f (α) be the minimum over all games satisfying
the conditions of the problem (such that player 1 wins with probability α) of the
expected number of tosses in the game. (For some games, the expected number
may be infinite; ignore those.) Prove that if α ∈ [0, 1] is a rational number whose
denominator in lowest terms is 2m for some m ≥ 0, then f (α) = 2 − 1/2m−1 . Prove
that if α is any other real number in [0, 1], then f (α) = 2. (This is essentially [New,
Problem 103].)
2 cos (4mp+ 2 )
1
1
FIGURE 10.
there exist vertices v1 , v2 of G such that ||p − v1 | − |p − v2 || < π 2 /n2 . Center the
polygon at (0, 0) and rotate to assume that p = (−r, 0) with 0 ≤ r ≤ 1. Let the two
vertices of G closest to (1, 0) be vi = (cos θi , sin θi ) for i = 1, 2 where θ1 ≤ 0 ≤ θ2 and
θ2 = θ1 + 2π/n. Then
where
fr (θ) = |(−r, 0) − (cos θ, sin θ)| = r2 + 2r cos θ + 1.
since f1 (θ) = 2 cos(θ/2) for −π ≤ θ ≤ π, and since the inequality cos x > 1 − x2 /2 for
x ∈ (0, π/3] follows from the Taylor series of cos x.
In order to solve the problem posed, we must deal with the case n = 3, i.e., m = 1,
since the bound
"π #
||p − v1 | − |p − v2 || ≤ 2 − 2 cos =1
3
is not quite good enough in that case. The proof shows, however, that equality holds
for the chosen v1 and v2 only when p is on the circle and diametrically opposite v1 ,
and in this case p is equidistant from the other two vertices. Hence the minimum of
||p−v1 |−|p−v2 || over all choices of v1 and v2 is always less than 1, and by compactness
there exists A > 0 such that it is less than 1 − A for all p in the disc, as desired.
Solutions: The Fiftieth Competition (1989) 105
v2
fr (2π/n)
p v2 v1
FIGURE 11.
Geometric interpretation of fr (0) − fr (2π/n).
Stronger result. By considering the three vertices farthest from p instead of just
v1 and v2 , one can improve this to (2/3)π 2 /n2 . Moreover, (2/3)π 2 cannot be replaced
by any smaller constant, even if one insists that n be odd and that p be in G.
First let us prove the improvement. As in Solution 2, assume that p = (−r, 0). The
vertex of G closest to (1, 0) is qθ = (cos θ, sin θ) for some θ ∈ [−π/n, π/n]. Reflecting
if necessary, we may assume θ ∈ [0, π/n]. Then fr (θ − 2π/n), fr (θ), and fr (θ + 2π/n)
are among the distances from p to the vertices of G. We use a lemma that states that
for fixed θ , θ ∈ [−π, π], the function |fr (θ ) − fr (θ )| of r ∈ [0, 1] is increasing (or
zero if |θ | = |θ |): to prove this, we may assume that 0 ≤ θ < θ ≤ π and observe
that for fixed r ∈ (0, 1), the derivative
equals the cosine of the angle q0 pqθ , whose measure increases with θ , so
If 0 ≤ θ ≤ π/(3n), then
2π 2π 2π 2π
fr θ − − fr θ + ≤ f1 θ − − f1 θ + (by the lemma)
n n n n
θ π θ π
= 2 cos − − 2 cos +
2 n 2 n
"π #
θ
= 4 sin sin
2 n
2
2π
< 2,
3n
since 0 < sin x < x for 0 < x < π/2. If instead π/(3n) ≤ θ ≤ π/n, then
2π 2π
fr (θ) − fr θ − ≤ f1 (θ) − f1 θ − (by the lemma)
n n
"π #
π θ
= 4 sin − sin
2n 2 2n
2
2π
< 2.
3n
Thus there is always a pair of vertices of G whose distances to p differ by less than
(2/3)π 2 /n2 .
Now let us show that the constant (2/3)π 2 cannot be replaced by anything smaller,
even if p is required to be inside G. Without loss of generality, we may assume that the
regular n-gon G is inscribed in the circle x2 + y 2 = 1 and has one vertex at (cos θ, sin θ)
where θ = π/(3n). Take p = (−r, 0) where r = cos(π/n). Then r is the radius of the
circle inscribed in G, but since θ and −π do not differ by an odd multiple of π/n, the
point p lies strictly inside G.
Finally we show that for this choice of p, if v1 and v2 are distinct vertices of G, then
2π 2 1
||p − v1 | − |p − v2 || ≥ 2 − O .
3n n4
Since fr (θ ) is a decreasing function of |θ |, the distances from p to the vertices, in
decreasing order, are
with an error of at most π 2 /(2n2 ) for each term. The latter sequence is
"π #
5π 7π 11π 13π
2 cos , 2 cos , 2 cos , 2 cos , 2 cos , ....
6n 6n 6n 6n 6n
Hence the consecutive differences in the original sequence are within π 2 /n2 of the
Solutions: The Fiftieth Competition (1989) 107
or of the form
"π #
(6k − 1)π (6k + 1)π 6kπ
2 cos − 2 cos = 4 sin sin
6n 6n 6n 6n
" #
kπ π 1
= 4 sin −O ,
n 6n n3
where 1 ≤ k ≤ n/2+O(1). If k ≥ 3, then bounding the sines from below by their values
at k = 3 and then applying sin x = x − O(x3 ) as x → 0 shows that these differences in
2π 2 π2
the approximating sequence exceed 3n 2 + n2 so the corresponding differences in the
2
2π
original sequence exceed 3n 2 . For k < 3 (the first four differences), we forgo use of the
approximating sequence and instead observe that for r = cos(π/n) and fixed integer
j, Taylor series calculations give
jπ (18 + j 2 )π 2 1
fr =2− + O ,
3n 36n2 n4
which implies that the first four differences in the original sequence (between the terms
corresponding to j = 1, 5, 7, 11, 13) are at least
2π 2 1
−O .
3n2 n4
Literature note. For an introduction to Taylor series, see [Spv, Ch. 23].
FIGURE 12.
Solutions: The Fiftieth Competition (1989) 109
Solution. We may assume that the dartboard has corners at (±1, ±1). A
point
(x, y) in the square is closer to the center than to the top edge if and only if
x + y ≤ 1−y, which is equivalent to x2 +y 2 ≤ (1−y)2 , and to y ≤ (1−x2 )/2. This
2 2
describes a region below a parabola. The region consisting of points in the board closer
to the center than to any edge is the intersection of the four symmetrical parabolic
regions inside the board: it is union of eight symmetric copies of the region A bounded
by x ≥ 0, y ≥ x, y ≤ (1 − x2 )/2. (See Figure 12.) A short calculation
√ shows
√ that the
bounding curves y = x and y = (1 − x2 )/2 intersect at (x, y) = ( 2 − 1, 2 − 1). Thus
the desired probability is
√2−1 √
8 Area(A) 1 − x2 4 2−5
= 2 Area(A) = 2 − x dx = .
Area(board) 0 2 3
Related question. If a billiard table had the same shape as the region of points of
the square closer to the center than to any edge, and a ball at the center were pushed
in some direction not towards the corners, what would its path be?
Using integration by parts [Spv, Ch. 18, Theorem 1] on the left, and the substitution
u = 2x on the last term converts this into
B
B B B/2
6
x f (x) − n
n
f (x)x n−1
dx = −3 n
x f (x) dx + n+1 un f (u) du.
0 0 0 2 0
where the coefficients ai are to be solved for. Let a0 = 1. If we differentiate (1) term
by term, temporarily disregarding convergence issues, then for k ≥ 1, the coefficient
k
of e−3·2 x in the expression f (x) + 3f (x) − 6f (2x) is −3 · 2k ak + 3ak − 6ak−1 . If this
is to be zero, then ak = 2k−2 a
−1 k−1
.
All this so far has been motivation. Now we define the sequence a0 , a1 , . . . by
a0 = 1 and ak = 2k−2 a
−1 k−1
for k ≥ 1, so
(−2)n
ak = ,
(2 − 1)(22 − 1) · · · (2k − 1)
Solutions: The Fiftieth Competition (1989) 111
∞
and define f (x) by (1). The series k=0 |ak | converges by the Ratio Test [Spv,
Ch. 22, Theorem 3], so (1) converges to a continuous function on [0, ∞). Moreover,
k
|ak e−3·2 x | ≤ |ak | for all complex x with Re(x) > 0, so by the Weierstrass M -test and
Weierstrass’s Theorem [Ah, pp. 37, 176], (1) converges to a holomorphic function in
this region. In particular, f (x) is differentiable on (0, ∞), and can be differentiated
term by term, so f (x) = −3f (x) + 6f (2x) holds.
Finally, we will show that if C > 0 is sufficiently small, then
√
Cf (x), which still satisfies
the differential equation, now also satisfies |Cf (x)| ≤ e− x . Since
√
f (x) = O(e−3x + e−6x + e−12x + · · · ) = O(e−3x ) = o(e− x
)
√
as x → ∞, we have |f (x)| ≤ e− x for all x greater than some x0 . √Let M =
supx∈[0,x0 ] |f √ . If C ∈ (0, 1) is chosen so that CM ≤ 1, then |Cf (x)| ≤ e− x both for
(x)|
e− x
x ∈ [0, x0 ] and for x ∈ (x0 , ∞), as desired.
Suppose Cmax were countable, say Cmax = {S1 , S2 , . . . }. Because Sn is infinite while
6n−1
Si ∩ Sn is finite for i = n, there exists bn ∈ Sn − i=1 Si for each n ≥ 1. For
m < n, bm ∈ Sm but bn ∈ Sm , so bm = bn , and the set B = {b1 , b2 , . . . } is countably
infinite. Moreover, bN ∈ Sn for N > n, so B ∩ Sn is finite. Hence {B, S1 , S2 , . . . } is a
good collection, contradicting the maximality of Cmax . Thus Cmax is uncountable, as
desired.
Remark. This question appears as [New, Problem 49], where the countably infinite
set is taken to be Z.
Remark (Zorn’s Lemma). A chain in a partially ordered set (S, ≤) is a subset
in which every two elements are comparable. Zorn’s Lemma states that if S is a
nonempty partially ordered set such that every chain in S has an upper bound in
S, then S contains a maximal element, i.e., an element m such that the only element
s ∈ S satisfying s ≥ m is m itself. Zorn’s Lemma is equivalent to the Axiom of Choice,
which states that the product of a family of nonempty sets indexed by a nonempty
set is nonempty. It is also equivalent to the Well Ordering Principle, which states
that every set admits a well ordering. (A well ordering of a set S is a total ordering
such that every nonempty subset A ⊆ S has a least element.) See pages 151 and 196
of [En].
Related question. Show that the following similar question, a restatement of [Hal,
Problem 11C], has a negative answer:
Can a countably infinite set have an uncountable collection of nonempty
subsets such that the intersection of any two of them has at most 1989
elements?
If d = 0, then
s1 − s2 2m
=2 sgn(e).
d m2 + 1
Solution 2. (See Figure 13.) Again assume that AB and CD are horizontal. The
x-coordinates of B and D are s1 /2 and −s2 /2, so their midpoint M has x-coordinate
(s1 − s2 )/4. Since line OM is the perpendicular bisector of BD, ∠OM E is a right
angle, and M lies on the circle with diameter OE. For fixed d = OE, the x-coordinate
(s1 − s2 )/4 is maximized when M is at the rightmost point of this circle: then
(s1 − s2 )/4 = d/2 and (s1 − s2 )/d = 2. This happens if and only if BD has slope −1
and s1 > s2 , or equivalently if and only if the diagonals BD and AC are perpendicular
and s1 > s2 .
s2
D C
E
M
d
A s1 B
FIGURE 13.
Literature note. For further discussion of this problem, including more solutions,
see [Lar2, pp. 33–38].
Solution 1. We may drop the i = n term in the Riemann sum, since f (xn+1 ) =
f (1) = 0. The volume of the region 0 < x1 < · · · < xn < 1 in Rn is
1 xn x2
··· dx1 dx2 · · · dxn = 1/n!.
0 0 0
" #
n−1
Therefore the expected value of the Riemann sum is E = i=0 Mi /(1/n!), where
1 xn x2
Mi = ··· (xi+1 − xi )f (xi+1 ) dx1 · · · dxn
0 0 0
1 xn xi+1
xi−1
= ···
(xi+1 − xi ) i f (xi+1 ) dxi dxi+1 · · · dxn
(i − 1)!
0 0
1 xn
0
xi+2 4 5
xii+1 xi+1
i+1
= ··· xi+1 − f (xi+1 ) dxi+1 · · · dxn
0 0 0 i! (i + 1) · (i − 1)!
1 xn xi+2
xi+1
i+1
= ··· f (xi+1 ) dxi+1 · · · dxn
(i + 1)!
0 0
0
1 1 1
since − =
i i+1 i(i + 1)
1 1 xn xi+3 i+1
xi+1
= f (xi+1 ) dxi+2 · · · dxn dxi+1
0 xi+1 xi+1 xi+1 (i + 1)!
1 i+1
(1 − xi+1 )n−(i+1) xi+1
= f (xi+1 ) dxi+1
0 (n − (i + 1))! (i + 1)!
1
1 n
= (1 − xi+1 )n−(i+1) xi+1
i+1 f (xi+1 ) dxi+1 .
n! 0 i + 1
Therefore
4n−1
5
1
n
E= (1 − xi+1 )n−(i+1) i+1
xi+1 f (xi+1 ) dxi+1
0 i+1
i=0
1 n
n
= (1 − t)n−j tj f (t) dt (we set j = i + 1 and t = xi+1 )
0 j=1
j
1
= (1 − (1 − t)n )f (t) dt,
0
since the sum is the binomial expansion of ((1 − t) + t)n except that the j = 0 term,
1
which is (1 − t)n , is missing. Hence E = 0 f (t)P (t) dt where P (t) = 1 − (1 − t)n .
Clearly 0 ≤ P (t) ≤ 1 for 0 ≤ t ≤ 1.
Solutions: The Fiftieth Competition (1989) 115
Solution 2. Fix n ≥ 0 and let (y1 , . . . , yn ) be chosen uniformly from [0, 1]n . Fix
t ∈ [0, 1], and let En (t) denote the expected value of
Rn = t − max ({0} ∪ ({y1 , . . . , yn } ∩ [0, t])) .
Let (x1 , . . . , xn ) be the permutation of (y1 , . . . , yn ) such that x1 ≤ · · · ≤ xn . The
distribution of (x1 , . . . , xn ) equals the distribution in the problem. Define
n−1
S= (yi+1 − zi+1 )f (yi+1 )
i=0
where zi+1 is the largest yj less than yi+1 , or 0 if no such yj exists. The terms in S
are a permutation of those in the original Riemann sum (ignoring the final term in the
Riemann sum, which is zero), so the expected 1 values of the Riemann sum and of S are
equal. Each term in S has expected value 0 En−1 (t)f (t) dt, since the expected value
of yi+1 − zi+1 conditioned on the event yi+1 = t for some t ∈ [0, 1] is the definition
1using (yj )j=i+1 ∈ [0, 1]
n−1
of En−1 (t) . Therefore the expected value of the Riemann
sum is n 0 En−1 (t)f (t) dt.
It remains to determine En (t) for n ≥ 0. Let yn+1 be chosen uniformly in [0, 1],
independently of the y1 , . . . , yn in the definition of En (t). Then En (t) equals the
probability that yn+1 is in [0, t] and is closer to t than any other yj , since this
probability conditioned on a choice of y1 , . . . , yn equals Rn . On the other hand, this
probability equals (1 − (1 − t)n+1 )/(n + 1), since the probability that at least one of
y1 , . . . , yn+1 lies in [0, t] equals 1 − (1 − t)n+1 , and conditioned on this, the probability
that the yj in [0, t] closest to t is yn+1 is 1/(n + 1), since all possible indices for this
closest yj are equally likely. Thus En (t) = (1 − (1 − t)n+1 )/(n + 1), and we may take
P (t) = nEn−1 (t) = 1 − (1 − t)n .
Literature note. For more on Riemann sums, see [Spv, Ch. 13, Appendix 1].
116 The William Lowell Putnam Mathematical Competition
f (n) = 1! + 2! + · · · + n!.
for all n ≥ 1.
Solution 2. Fix r ∈ R and C > 0. Then for sufficiently large positive integers n,
(n + r)3 − (n + r − C)3 = 3n2 C + O(n) > 1,
so (n + r − C)3 ≤ (n + r)3 ≤ (n + r)3 , and 3 (n + r)3 is within C of n + r. Hence
" √ #
lim 3 (n + r)3 − 3 n = r.
n→∞
√ √
Solution 3. As in Solution 1, 3 n + 1 − 3 n → 0 as n → ∞, so the set
√ √
S = { 3 n − 3 m} contains arbitrarily small positive numbers. √ Also S√is closed under
√ √ 3 3
multiplication by positive integers k since k( 3 n − 3 m) = k 3 n − k 3 m. Any set
with the preceding two properties is dense in [0, ∞), because any finite open interval
(a, b) in [0, ∞) contains a multiple of any element of S ∩ (0, b − a). By symmetry S is
dense in (−∞, 0] too.
√
Solution 4. Let bn = (n 3 5 mod 1) ∈ [0, 1]. As in the remark √ following 1988B3,
{bn } is dense in [0, 1]. Thus given
√ C > 0,
√ we can√ find n such that n 3
5 − r is within C
3 3
of some integer m ≥ 0. Then 5n − m = n 5 − m is within C of r.
3 3 3
FIGURE 14.
A convex pentagon with area 5/2 whose vertices have integer coordinates.
Solution. Punches at two points P and Q are not enough to remove all points,
because if r is any rational number exceeding P Q/2, the circles of radius r centered
at P and Q intersect in at least one point R, and R is not removed by either punch.
We next show that three carefully chosen punches suffice.
Proof 1: Existential. Punch twice, at distinct centers. Since each punch leaves
countably many circles, and any two distinct circles intersect in at most two points,
the two punches leave behind a countable set. Consider all circles with rational radii
centered at points of this set. Their intersections with a fixed line L form a countable
set S. A point of L − S is at an irrational distance from all unpunched points; apply
the third punch there.
Remark. The fact that the plane is not a countable union of circles can also be
deduced from measure theory: a circle (without its interior) in the plane has measure
zero, and a countable union of measure zero sets still has measure zero, but the entire
plane has infinite measure. See [Ru] for more on measure theory.
√
Proof 2: Constructive. Choose α ∈ R such that α2 is irrational, for example α = 3 2.
Use punches centered at A = (−α, 0), B = (0, 0), and C = (α, 0). If P = (x, y) is any
Solutions: The Fifty-First Competition (1990) 121
point,
AP 2 + CP 2 − 2BP 2 = (x + α)2 + y 2 + (x − α)2 + y 2 − 2(x2 + y 2 ) = 2α2
is irrational, so AP , BP , CP cannot all be rational. Hence all P get removed.
Remark. The motivation for taking AP + CP − 2BP is that it is the linear
2 2 2
A B A B A
#✥#✥#✥#✥#✥
B A B A
e4 e3 e2 e1 0
B
✧✦✧✦✧✦✧✦✧✦
FIGURE 15.
Schematic representation of counterexample in Solution 2 to 1990A5. Alternatively, a
transition diagram for a finite automaton.
is the sum of the two preceding terms. Starting from a0,0 = 1 and a1,0 = 2, we find
that the 21st term in the sequence
is a10,10 = 17711. (The sequence is the Fibonacci sequence defined at the end of
1988A5, but starting with F2 = 1.)
124 The William Lowell Putnam Mathematical Competition
for all n ≥ 0.
For m ≥ 1, let Rm mean “1 × m rectangle,” and let Nm denote the number of ways
to tile an Rm with 1 × 1 squares and 1 × 2 dominos (rectangles). We now prove (1) by
showing that both sides equal N2n+1 . A tiling of an Rm ends either with a square or
a domino, so Nm = Nm−1 + Nm−2 for m ≥ 3. Together with N1 = 1 and N2 = 2, this
proves Nm = Fm+1 by induction. In particular N2n+1 equals F2n+2 , the right-hand
side of (1).
On the other hand, if we start with a pair of tilings, one a tiling of an Rn+i−j by
n − i − j squares and i dominos, and the other a tiling of an Rn+j−i by n − i − j
squares and j dominos, we may form a tiling of an R2n+1 by appending the two, with
a square inserted in between. Conversely, any tiling of an R2n+1 arises from such
a pair: every tiling of an R2n+1 contains an odd number of squares, so there is a
“median” square, and the pieces to the left and right of this square
constitute
a pair
of tilings. The number of such pairs for fixed i and j equals n−j n−i
, so N
n−i i j 2n+1
equals i,j n−j i j , the left-hand side of (1).
This proves (1). The desired value a10,10 = F22 is then found by calculating
F0 , F1 , . . . , F22 successively, using Fn+2 = Fn+1 + Fn .
√
Answer. There are two such functions, namely f (x) =
√ 1990ex , and f (x) =
− 1990ex .
Solution. For a given f , the functions on the left- and right-hand sides are equal
if and only if their values at 0 are equal, i.e., f (0)2 = 1990, and their derivatives are
equal for all x, i.e.,
Remark. The number 50387 is far from the best possible. Liu and Schwenk have
shown, using an inclusion-exclusion argument, that the maximum number of elements
in U in which no two elements commute is 32390 [LS]. Because the bound given in
the problem is so far from being optimal, there are many possible solutions.
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 .)
Solution. We use graph theory terminology; see the remark below. Construct
a directed multigraph D whose vertices are the elements of G, and whose arcs are
indexed by G × {a, b}, such that the arc corresponding to the pair (g, x) goes from
vertex g to vertex gx. (See Figure 16 for an example, with G equal to the symmetric
group S3 , a equal to the transposition (12), and b equal to the 3-cycle (123).) At
the vertex g, there are two arcs going out (to ga and to gb), and two arcs coming in
(from ga−1 and from gb−1 ). Also, D is weakly connected, since a and b generate G.
Hence, by the first theorem in the remark below, D has an Eulerian circuit. Take g1 ,
g2 , . . . , gm to be the the startpoints of the arcs in this circuit, in order. Each element
of G occurs exactly twice in this sequence, since each vertex of D has outdegree 2; in
particular m = 2n. Also, for 1 ≤ i ≤ 2n, the element gi+1 equals either gi a or gi b,
because the two outgoing arcs from gi end at gi a and gi b.
Remark (Eulerian paths and circuits). A directed multigraph D consists of a set V
(whose elements are called vertices), and a set E (whose elements are called arcs or
sometimes edges or directed edges), with a map E → V × V (thought of as sending
an arc to the pair consisting of its startpoint and the endpoint). Typically one draws
each element of V as a point, and each arc of E as an arc from the startpoint to the
endpoint, with an arrow to indicate the direction. What makes it a multigraph is that
for some vertices v, w ∈ V , there may be more than one arc from v to w. Also, there
may be loops: arcs from a vertex to itself. Call D finite if V and E are both finite
sets.
The outdegree of a vertex v is the number of arcs in E having v as startpoint.
Similarly the indegree of v is the number of arcs in E having v as endpoint. If v, w ∈ V
then a path from v to w in D is a finite sequence of arcs in E, not necessarily distinct,
such that the startpoint of the first arc is v, the endpoint of each arc (other than the
last) is the startpoint of the next arc, and the endpoint of the last arc is w. Such a
path is called a circuit or cycle if v = w. An Eulerian path in D is a path in which
each arc in E occurs exactly once. An Eulerian circuit is a circuit in which each arc
in E occurs exactly once. We say that D is strongly connected if for every two distinct
vertices v, w ∈ V , there is a path from v to w in D. On the other hand, D is weakly
connected if for every two distinct vertices v, w ∈ V , there is a path from v to w in
Solutions: The Fifty-First Competition (1990) 127
(12)
a a
b (1) b
b b
(231) (123)
a a
b
a a
(23) (13)
b
FIGURE 16.
Cayley graph of the group S3 with generators a = (12) and b = (123)
the corresponding undirected graph, that is, a path consisting of arcs some of which
may be the reverses of the arcs in E.
Then one can prove the following two theorems.
• A finite directed multigraph with at least one arc has an Eulerian circuit if and only
if it is weakly connected and the indegree and outdegree are equal at each vertex.
• A finite directed multigraph with at least one arc has an Eulerian path but not an
Eulerian circuit if and only if it is weakly connected and the indegree and outdegree
are equal at each vertex, except at one vertex at which indegree is 1 larger than
outdegree, and one other vertex at which outdegree is 1 larger than indegree.
See Chapter 7 of [Ros2], especially §7.4 and §7.5.
Remark. The directed multigraph constructed in the solution is called the Cayley
digraph or Cayley diagram associated to G and its set of generators {a, b}. See [Fr,
pp. 87–91].
pn (x) = a0 + a1 x + a2 x2 + · · · + an xn
Then the signs of pn (α0 ), pn (α1 ), . . . , pn (αn ) alternate. Define an+1 = −C sgn(pn (αn )),
where C is positive and small enough that
sgn pn+1 (αi ) = sgn pn (αi )
for all i. Let
pn+1 (x) = pn (x) + an+1 xn+1 .
By the Intermediate Value Theorem, pn+1 has a zero between αi and αi+1 for
0 ≤ i ≤ n − 1, and a zero greater than αn since
sgn pn+1 (αn ) = lim sgn pn+1 (x) .
x→∞
Because pn+1 (x) is of degree n + 1, it cannot have more than these n + 1 zeros, so
pn+1 (x) has n + 1 distinct real zeros, as desired.
2
Solution 2. For n ≥ 0, let an = (−1)n 10−n . For 0 ≤ k ≤ n,
n
2 2
(−1)k 10−k pn (102k ) = (−1)i−k 10−(i−k)
i=0
n−k
2
= (−1)j 10−j
j=−k
∞
2
>1−2 10−j
j=1
> 0,
so pn (1), pn (102 ), pn (104 ), . . . , pn (102n ) alternate in sign. By the Intermediate Value
Theorem, it follows that pn (x) has at least n distinct real zeros. Since pn (x) has degree
n, there cannot be more than n zeros.
Remark. Solution 2 is motivated by the theory of Newton polygons for polynomials
with coefficients in the field Qp of p-adic numbers. Let | · |p denote the p-adic absolute
value on Qp . If {ai }i≥0 is a sequence of nonzero p-adic numbers such that the lower
convex hull of { (i, − ln |ai |p ) : 0 ≤ i ≤ n } consists of n segments with different slopes,
n 2
then i=0 ai xi has n distinct zeros in Qp ; in particular this holds for ai = pi . The
analogous statement over R, with | · |p replaced by the standard absolute value, is not
true in general, but it is true if the differences between the slopes are sufficiently large
relative to n. For an introduction to p-adic numbers and Newton polygons, see [Kob].
Support line L1 w
tw
L S
B S( K,t ) K
Support line L2
is empty. This is illustrated in Figure 18. (Also, if t = 1/3, then this intersection
consists of just the centroid. This motivates the rest of the solution.)
L1
1/3
1/6
L
1/3
L2
FIGURE 17.
130 The William Lowell Putnam Mathematical Competition
BS (CA,t) BS (AB,t)
BS (BC,t)
B C
FIGURE 18.
S∩ K BS (K, t) may be empty for t < 1/3.
Recall
that the centroid of a measurable region S in R2 is the unique point P such
−→
that Q∈S P Q dA = 0. Equivalently, the coordinates
of the centroid (x, y) are given
by x = S x dA/ S 1 dA, and y = S y dA/ S 1 dA. If S is convex, then the centroid
lies within S.
We now show that the intersection of the problem is nonempty for t ≥ 1/3 for any
S, by showing that each strip BS (K, t) contains the centroid of S. By symmetry, it
suffices to show that the centroid of S is at most 2/3 of the distance from L1 to L2 .
Think of L1 as the upper support line. (See Figure 19.) Let Pi be a point of contact
of Li with S, for i = 1, 2. For a variable point Q to the left of P2 on L2 (possibly
←→
Q = P2 ), let A be the intersection of S with the open half-plane to the left of QR1 , and
let B be the part of (possibly degenerate) 4QP1 P2 lying outside S. As Q moves to a
nearby point Q , Area(A) and Area(B) each change by at most Area(4QQ P1 ), which
can be made arbitrarily small by choosing Q close to Q; hence Area(A) and Area(B)
vary continuously as functions of Q. The difference δ(Q) = Area(A) − Area(B) is also
a continuous function of Q. At Q = P2 , Area(A) ≥ 0 and Area(B) = 0, so δ(P2 ) ≥ 0.
But as Q tends to infinity along L1 , Area(A) is bounded by Area(S) and Area(B)
grows without bound, so δ(Q) < 0 for some Q. By the Intermediate Value Theorem,
there is some position of Q for which δ(Q) = 0, i.e., for which Area(A) = Area(B).
Fix such a Q.
P1
L1
A
A A¢
B
L2
Q P2
FIGURE 19.
Solutions: The Fifty-First Competition (1990) 131
L1
✧ ❧
✧ ❈ ❧
✧ ❈
✧ ❧
✧ ❈ ❧
❅ ❈ ❧
❅ ❈ #✁
#✁
❅ ❈ #
❜ ❅ ❈ # ✁
❆❜ ❅ ❈ # ✁
❆P❜❜ ❅ ❈ # ✁
PP❜ #
P❜
P❅ ❜ ❈ # ✘✘✘✁
P❜ P❈#
❅ ✘✘✘
L2
P
FIGURE 20.
Partially covering S by triangles.
132 The William Lowell Putnam Mathematical Competition
Then f is the uniform limit of fn on [0, 1], and fn is smooth. Finally, fn is also concave-
down, because the convolution can be viewed as a weighted average of translates of
f.
Remark (Eric Wepsic). Alternatively, one can prove (3) for all concave-down
continuous functions by discretizing (2). For n ≥ 1, define
n
i 1 i 1
An = − f , and
i=1
n 3 n n
n
f (1) i f ((i + 1)/n) − 2f (i/n) + f ((i − 1)/n) 1
Bn = + g ,
6 i=1
n 1/n2 n
where g(t) = t3 /6 − t2 /6. (These are supposed to be approximations to the two ends
of (2). The ratio
f ((i + 1)/n) − 2f (i/n) + f ((i − 1)/n)
1/n2
n
Bn = bin f (i/n)
i=1
with
n g n1 − g n0 + 0 , if i = 0
i+1 i
bin = n g n − 2g n + g i−1 , if 1 ≤ i ≤ n − 1
1 + n 0 − g n + g n−1 ,
n
6 n n if i = n.
Since g is infinitely differentiable, Taylor’s Theorem [Spv, Ch. 19, Theorem 4] centered
at x shows
1 1 g (x) 1
g x+ − 2g(x) + g x − = 2
+ O
n n n n3
and
1 g (x) 1
g x± − g(x) = ± +O
n n n2
134 The William Lowell Putnam Mathematical Competition
as n → ∞, where the constants implied by the O’s are uniform for x ∈ [0, 1]. Thus
1
g (0) + O n , if i = 0
bin = g (i/n) + O n12 , if 1 ≤ i ≤ n − 1
1 − g (1) + O 1 ,
n
6 n if 1 ≤ i ≤ n − 1
1
O ,
i n 1 1 1
if i = 0
n − 3 n + O n2 , if 1 ≤ i ≤ n − 1
=
O 1 ,
if 1 ≤ i ≤ n − 1.
n
where again the implied constants are uniform. Except for the O’s, these are the same
as the coefficients of f (i/n) in An . Thus, if M = sup{ |f (t)| : t ∈ [0, 1] }, then
4n−1 5
An − Bn = O(1/n)M + O(1/n2 )M + O(1/n)M = O(1/n).
i=1
(6, 2)
FIGURE 21.
The point (1, 1) rotates around (2, 0) to (3, 1), then around (5, 0) to (6, 2), then
around (7, 0) to (9, 1), then around (10, 0) to (11, 1). (See Figure 21.) The area
of concern consists of four 1 × 1 right triangles
√ of area 1/2, four 1 × 2 triangles of
area 1,√two quarter circles of area (π/4)( 2)2 = π/2, and two quarter circles of area
(π/4)( 5)2 = 5π/4, for a total area of 7π/2 + 6.
Answer. No.
Solution. We have
(A2 + B2 )(A − B) = A3 − B3 − A2 B + B2 A = 0,
Answer. The real polynomials with the required property are exactly those that are
of degree 2 with 2 distinct real zeros.
Solution.
All degree 2 polynomials with 2 distinct real zeros work. If p(x) = ax2 + bx + c has
two real zeros r1 < r2 (i.e., b2 − 4ac > 0), then
so p (r) = 0.
Approach 2 is the following: let q(x) = (x − r1 ) · · · (x − rn−2 ) so
Rolle’s Theorem (see remark below) implies that all the zeros of q (x) lie between r1
and rn−2 . Hence (rn−1 + rn )/2 is not a zero of q (x), so p(x) does not satisfy the
hypotheses of the problem.
Remark. Rolle’s Theorem is the following:
Solutions: The Fifty-Second Competition (1991) 137
Rolle’s Theorem. Let [a, b] be a closed interval in R. Let f (t) be a function that
is continuous on [a, b] and differentiable on (a, b), and suppose that f (a) = f (b). Then
there exists c ∈ (a, b) such that f (c) = 0.
In particular, if f (t) ∈ R[t] is a polynomial of degree n with n distinct real zeros,
then the real zeros of f (t) are contained in the interval spanned by the zeros of f (t).
The previous sentence has a generalization to complex polynomials, known as Lucas’
Theorem, or sometimes as the Gauss-Lucas Theorem:
Lucas’ Theorem. If p(z) ∈ C[z] is a polynomial of degree at least 1, then the zeros
of p (z) are contained in the convex hull of the set of zeros of p(z).
See [Mar] for this and many related results, as well as the following open question:
Let p(z) ∈ C[z] be a polynomial whose complex zeros all lie in the disc
|z| ≤ 1, and let z1 be any one of the zeros. Must p (z) have a zero in the
disc |z − z1 | ≤ 1?
B. Sendov conjectured in 1962 that the answer is yes, but in the literature it is
sometimes called the “Ilyeff Conjecture,” because of a misattribution. The statement
has been proved for deg p ≤ 8 [BX].
Related question. Let n > 2, and let p(x) ∈ R[x] be a polynomial of degree n
with n distinct real zeros r1 < · · · < rn . Rolle’s Theorem implies that p (x) has n − 1
distinct real zeros, interlaced between the zeros of p(x). Prove that the largest real
zero of p (x) is closer to rn than to rn−1 , and that the smallest real zero of p (x) is
closer to r1 than to r2 .
See [An] for related ideas.
√ √
Solution 2. If u, v ≥ 0, then u2 + v 2 ≤ u2 + 2uv + v 2 = u + v. Taking u = x2
and v = y − y 2 we obtain
y y
2
x4 + (y − y 2 )2 dx ≤ x + y − y 2 dx
0 0
2
= y − y3
2
3
1
≤ ,
3
with
2equality
everywhere if y = 1: the last inequality uses the positivity of
d
dy y − 2 3
3 y = 2y(1 − y) on (0, 1). Thus the maximum value is 1/3.
B1. (192, 6, 2, 0, 6, 0, 0, 0, 0, 5, 0, 2)
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?
Answer. This sequence is eventually constant if and only if A is a perfect square.
Setting y = 0 yields
Thus
2f (x)f (x) + 2g(x)g (x) = 0,
and therefore
f (x)2 + g(x)2 = C
implies C = C 2 . But C = 0, so C = 1.
Solution 2. Define h : R → C by h(x) = f (x) + ig(x). Then h is differentiable,
and h (0) = bi for some b ∈ R. The two given functional equations imply h(x + y) =
h(x)h(y). Differentiating with respect to y and substituting y = 0 yields h (x) =
h(x)h (0) = bi · h(x), so h(x) = Cebix for some C ∈ C. From h(0 + 0) = h(0)h(0) we
obtain C = C 2 . If C = 0, then h would be identically zero, and f and g would be
constant, contradiction. Thus C = 1. Finally, for any x ∈ R,
f (x)2 + g(x)2 = |h(x)|2 = |ebix |2 = 1.
Remark. It follows that f (x) = cos(bx) and g(x) = sin(bx) for some nonzero b ∈ R.
Solutions: The Fifty-Second Competition (1991) 143
Remark. Solution 1 is very close to what one gets if one writes out Solution 2 in
terms of real and imaginary parts.
Remark. Suppose we change the problem by dropping the assumption that f
and g are differentiable, and assume only that f and g are continuous, and that
f (0) exists and is zero. Then we could still conclude f (x)2 + g(x)2 = 1 by following
Solution 2, because it is true that any continuous function h : R → C satisfying
h(x + y) = h(x)h(y) is either identically zero, or of the form h(x) = ebx for some
b ∈ C. This is a consequence of the following lemma, sometimes attributed to Cauchy.
Lemma. Suppose f : R → R is a continuous function such that
f (x + y) = f (x) + f (y). (1)
Then f (x) = cx for some c ∈ R.
Proof. By substituting x = y = 0 into (1), we find f (0) = 0. Let c = f (1). It is not
hard to show that f (x) = cx for rational x (by using (1) repeatedly). Since f (x) − cx
is a continuous function that vanishes on a dense set (the rationals), it must be 0.
Reinterpretation. Solution 2 can be understood in a more sophisticated context.
If h is not identically zero, h : R → C∗ is a continuous homomorphism between real
Lie groups, so by [War, Theorem 3.38], it is a homomorphism of Lie groups. (In
other words, it is automatically analytic.) Since homomorphisms of Lie groups are
determined by their induced Lie algebra homomorphisms [War, Theorem 3.16], h must
be identically zero, or of the form h(x) = ebx for some b ∈ C.
must vanish at (e2πi/4 , e2πi/7 ). But if 4 does not divide m and 7 does not divide
n, then f (e2πi/4 , e2πi/7 ) is nonzero and hence it is impossible to dissect the m × n
rectangle in the specified way.
This argument is related to a beautiful proof [Wag, Proof 1] of the following
remarkable fact.
Theorem 2. If a rectangle is tiled by rectangles each of which has at least one
integer side, then the tiled rectangle has at least one integer side.
Remark. Theorem 1 also comes up in other advanced contexts. For example, it
corresponds to the fact that two measures of the “nonsmoothness” of the complex
singularity given by y p = xq in C2 are the same [ACGH, p. 60].
p p+j
p
Solution 1. The sum j=0 j j is the coefficient of xp in
p p
p p
(1 + x)p+j = (1 + x)j (1 + x)p
j=0
j j=0
j
p
= (1 + x) + 1 (1 + x)p
= (2 + x)p (1 + x)p ,
≡ 1 + 2p (mod p2 ).
Solution 2. Modulo p, the sets {1, 2, . . . , p − 1} and {1−1 , 2−1 , . . . , (p − 1)−1 } are
the same (where the inverses are modulo p). Thus
2p p+1 p+2 p + (p − 1) 2p
= · ··· ·
p 1 2 p−1 p
≡ (1−1 p + 1)(2−1 p + 1) · · · ((p − 1)−1 p + 1) · 2
≡ 2(1p + 1)(2p + 1) · · · ((p − 1)p + 1)
44p−1 5 5
≡2 k p+1
k=1
≡2 (mod p2 ).
Although 1−1 , . . . , (p − 1)−1 are only defined modulo p, they appear in the equations
above multiplied by p, so the terms make sense modulo p2 .
p p−1
p p+j p p+1p+2 p+j 2p
=1+ ··· +
j=0
j j j=1
j 1 2 j p
p−1
p
≡1+ (1−1 p + 1)(2−1 p + 1) · · · (j −1 p + 1) + 2
j=1
j
p−1
p
≡1+ +2 (since p | pj for 1 ≤ j ≤ p − 1)
j=1
j
p
p
≡ +1
j=0
j
≡ 2p + 1 (mod p2 ).
2p
Remark. Here is another way to prove p ≡ 2 (mod p2 ) for odd primes p. We
have
2p (p + 1)(p + 2) · · · (p + p − 1)
=2 (1)
p 1 · 2 · · · (p − 1)
and
+
(p−1)/2
(x + 1)(x + 2) · · · (x + p − 1) = (x + j)(x + p − j)
j=1
+
(p−1)/2
= (x2 + px + j(p − j))
j=1
and divide up the terms into those with i divisible by p and those with i not divisible
by p. This gives
n−1 n−1
n p+ n p+ p−1
+ pn + pj + i
2p p + pj
= .
pn j=1
pj j=1 i=1
pj + i
2pn−1
The term in the first parentheses is precisely pn−1 . Therefore
2pn
+
n−1
p+ p−1
pn pn
2pn−1 = 1+
pj + i
pn−1 j=1 i=1
pn−1 p−1
1 1
≡1+p n
+ p2n (mod p3n ).
pj + i (pj + i)(pj + i )
j=1 i=1 pj+i=pj +i
The last sum is divisible by pn . Thus the assertions follow from the congruence
pn−1 p−1
1
≡0 (mod p2n ),
j=1 i=1
pj + i
where pm is the largest power of p dividing p3 nk(n − k) nk . The same congruence
holds for p = 3, but with p3 replaced by 32 . (In other words, one loses a factor of 3.)
{ x2 : x ∈ Zp } ∩ { y 2 + 1 : y ∈ Zp }?
for any k ∈ Z.
In this solution only, if P is a statement, let [P ] be 1 if P is true, and 0 if P is false.
Let F2p denote the set of squares in Fp , including 0. The problem asks us to compute
p−1
N= [a ∈ F2p ] · [a − 1 ∈ F2p ].
a=0
= S(1).
Also,
p−1 p−1 p−1
a a−k
S(k) = = 0,
a=0
p p
k=0 k=0
150 The William Lowell Putnam Mathematical Competition
where the sum is taken over all @-tuples (t1 , . . . , t! ) with the ti in Fp summing
to 1. Jacobi sums are related to Gauss sums, which are sums of the form ga (χ) =
p−1
t=0 χ(t)ζ
at
where χ is a multiplicative character on Fp , ζ = e2πi/p , and a ∈ Z. See
Chapters 6 and 8 of [IR] for more details. See also [Lan2, Chapter IV,§3] for more
general Gauss sums, over Z/nZ for n not necessarily prime, and over finite fields not
necessarily of prime order. Theorem 5 in Chapter 8 of [IR] gives the formula for the
number of solutions to (2) in terms of Jacobi sums.
Remark (the Weil Conjectures). The formula just mentioned led Weil [Weil2] to
formulate his famous conjectures (now proven) about the number of points on varieties
over finite fields. He proved the conjectures himself in the case of curves [Weil1]. Their
proof for arbitrary algebraic varieties uses ideas of Grothendieck and Deligne, among
others. For a survey, see [Har, Appendix C]. See Proof 3 of the stronger result following
1998B6 for one application of the conjectures.
Since this equation is homogeneous in {a, b}, we can divide by b and set r = a/b,
yielding
rx v − rx v −1 ≤ rv x − rv −x + v 1−x − v −1+x .
At this point, some inspiration is necessary. Notice that the terms involving x are
of the form r±x or v ±x . This suggests the substitution v = r±1 ; since v, r ≥ 1 we
substitute v = r. Then after this substitution, the inequality becomes 0 ≥ 0, i.e.,
equality holds for all x! This strongly suggests that c = ln r, and that a good strategy
would be to check that the inequality only “gets better” as |u| decreases from c, and
“gets worse” as |u| increases from c.
This intuition then leads directly to the following argument.
of u is decreasing for u > 0. For this, it suffices to show that for each α ∈ (0, 1), the
function
sinh αu
f (u) =
sinh u
is decreasing for u > 0, since F (u) is a constant plus a sum of positive multiples of
two such functions f . Differentiating with respect to u yields
which for u > 0 is negative if and only if the value of the function
is negative. The negativity of g(u) for u > 0 follows from g(0) = 0 and the negativity
of
α α
g (u) = − ,
cosh u cosh2 αu
2
which in turn follows since cosh is increasing on R+ . Thus F (u) is decreasing for
u > 0.
If a > b then F (u) is zero at u = ln(a/b). If a = b then limu→0+ F (u) = 0 by
L’Hôpital’s Rule [Spv, Ch. 11, Theorem 9]. Since F (u) is decreasing for u > 0, in both
cases we have F (u) ≥ 0 for 0 < u ≤ ln(a/b) and F (u) < 0 for u > ln(a/b), as desired.
x(ln(a sinh u)) + (1 − x)(ln(b sinh u)) ≤ ln(a sinh ux + b sinh u(1 − x)),
which, if we define
f (x) = a sinh ux + b sinh u(1 − x),
can be written as
x ln f (1) + (1 − x) ln f (0) ≤ ln f (x).
This will hold if u is such that ln f (x) is concave for x ∈ (0, 1), and will fail if ln f (x)
is strictly convex on (0, 1).
Solutions: The Fifty-Second Competition (1991) 153
We compute
d f
ln f =
dx f
d2 f f − (f )2
ln f =
dx2 f2
f = au cosh ux − bu cosh u(1 − x)
f = au2 sinh ux + bu2 sinh u(1 − x)
f f − (f )2 = (a2 + b2 )u2 (sinh2 ux − cosh2 ux)
+ 2abu2 sinh ux sinh u(1 − x) + cosh ux cosh u(1 − x)
= (a2 + b2 )u2 (−1) + 2abu2 cosh ux + u(1 − x)
= u2 (−a2 − b2 + 2ab cosh u)
d2
so dx2 ln f has constant sign for x ∈ (0, 1), and the following are equivalent:
d2
ln f ≤ 0 for x ∈ (0, 1)
dx2
−a2 − b2 + 2ab cosh u ≤ 0
−a2 − b2 + abeu + abe−u ≤ 0
−(a − eu b)(a − e−u b) ≤ 0
−(a − eu b) ≤ 0 (since u > 0 and a ≥ b > 0)
u ≤ ln(a/b).
Solution. Let g(x) = 1/(1 + x2 ) and h(x) = f (x) − g(x). The value of g (k) (0) is
∞
k! times the coefficient of xk in the Taylor series 1/(1 + x2 ) = m=0 (−1)m x2m , and
the value of h(k) (0) is zero by the lemma below (which arguably is the main content
of this problem). Thus
,
(−1)k/2 k! if k is even;
(k) (k)
f (0) = g (0) + h (0) =(k)
0 if k is odd.
h(x) = h(0) + h (0)x + · · · + h(n−1) (0)xn−1 /(n − 1)! + h(n) (θn )xn /n!.
156 The William Lowell Putnam Mathematical Competition
Remark. The formula (1) holds under the weaker assumption that h(k) (0) exists.
To prove this, apply L’Hôpital’s Rule k − 1 times, and then write the resulting
expression as a combination of limits of the form
h(k−1) (jC) − h(k−1) (0)
lim ,
%→0 jC
each of which equals h(k) (0), by definition.
Remark. Note that h(x) need not be the zero function! An infinitely differentiable
function need not be represented by its Taylor series at a point, i.e., it need not be
analytic. For example, consider
, 2
e−1/x sin(π/x) for x = 0,
h(x) =
0 for x = 0.
It is infinitely differentiable for all x, and all of its derivatives are 0 at x = 0. (It
satisfies the hypotheses of the lemma!)
contradicting the fact that c(k, m) is even for each k in the block. Thus no such pair
(k1 , k2 ) exists.
On the other hand, since 2m ≥ 2n+1 , there does exist k in the block such that
k ≡ 2s (mod 2n+1 ). The smallest element of the block must be at least k − 2n+1 + 1,
or else we could take k1 = k − 2n+1 and k2 = k1 + 2s . The largest element must be at
most k + 2s − 1, or else we could take k1 = k and k2 = k1 + 2s . Thus the block has
length at most
2n+1 + 2s − 1 < 2n+1 + 2s+2 − 2s+1 − 1 ≤ 2n+2 − 2s+1 − 1 = 2m − 1,
which is a contradiction.
Related question. Show that if two adjacent blocks are identical, then the length
of each is a power of 2. Show that any power of 2 is achievable.
Remark. This sequence is sometimes called the Thue-Morse sequence; see [AS] for
examples of its ubiquity in mathematics, including its use by Machgielis Euwe (chess
world champion 1935–37) to show that infinite games of chess may occur despite the
so-called “German rule” which states that a draw occurs if the same sequence of moves
occurs three times in succession.
Related question. Another fact discussed in [AS] is the following (see there for
further references). The result of Christol mentioned in the remark following 1989A6
∞
implies that the generating function F (x) = n=0 an xn considered as a power series
with coefficients in F2 , is algebraic over the field F2 (x) of rational functions with
coefficients in F2 . We leave it to the reader to verify that
(x + 1)3 F (x)2 + (x + 1)2 F (x) + x = 0.
On the other hand, if the coefficients of F (x) are considered to be rational, then
one can show that F (x) is transcendental over Q(x), and even that F (1/2) is a
transcendental number.
Related questions. The Thue-Morse sequence has a self-similarity property: if one
replaces each “0” with “0, 1”, and each “1” with “1,0”, one recovers the original
sequence. The “extraction of terms with even indices” in Solution 1 is just reversing
this self-similarity.
Here are a few more problems and results relating to “arithmetic self-similarity”.
(a) Show that the sequence s(0), s(1), s(2), . . . , defined by s(3m) = 0, s(3m + 1) =
s(m), s(3m+2) = 1, also has the property that there are not “three identical blocks in
a row”. This problem is given in [Hal, p. 156], along with a discussion of its motivation
in chess.
(b) 1993A6.
(c) Problem 3 on the 1988 International Mathematical Olympiad [IMO88, p. 37] is:
A function f is defined on the positive integers by
f (1) = 1, f (3) = 3, f (2n) = f (n),
f (4n + 1) = 2f (2n + 1) − f (n), f (4n + 3) = 3f (2n + 1) − 2f (n),
for all positive integers n. Determine the number of positive integers n, less
than or equal to 1988, for which f (n) = n.
Solutions: The Fifty-Third Competition (1992) 159
(d) Also, [YY, p. 12] has a series of similar problems. For example, this Putnam
problem answers the question Yaglom and Yaglom pose in Problem 124(b). The
subsequent problem is harder:
Show that there exist arbitrarily long sequences consisting of the digits 0, 1,
2, 3, such that no digit or sequence of digits occurs twice in succession. Show
that there are solutions in which the digit 0 does not occur; thus three digits
is the minimum we need to construct sequences of the desired type.
For a link to a discrete version of dynamical systems, [YY] suggests [MH].
Let P1 , P2 , P3 , P4 be the four random points on the sphere. We may suppose that
the choice of each Pi is made in two steps: first a random point Qi is chosen, then a
random sign Ci ∈ {−1, 1} is chosen and we set Pi = Ci Qi .
The probability that Q3 is in the linear subspace spanned by Q1 and Q2 is zero.
Similar statements hold for any three of the Qi , so we may assume that every three of
the Qi are linearly independent. The probability that Q4 is in the plane through Q1 ,
Q2 , Q3 is zero, so we may assume that Q1 Q2 Q3 Q4 is a nondegenerate tetrahedron
TQ . We may also assume that for any choices of the Ci , the tetrahedron TP with the
Pi as vertices is nondegenerate.
The linear map LQ : R4 → R3 sending (w1 , w2 , w3 , w4 ) to wi Qi is surjective, so
ker LQ is 1-dimensional, generated by some (w1 , w2 , w3 , w4 ). Since every three Qi are
linearly independent, every wi is nonzero.
We claim that 0 lies in the interior of TQ if and only if all the wi have the same sign.
If 0 lies in the interior of TQ , then 0 is a convex combination of the vertices in which
4
each occurs with nonzero coefficient; i.e., 0 = i=1 ri Qi for some r1 , r2 , r3 , r4 > 0
with sum 1. Then (w1 , w2 , w3 , w4 ) is a multiple of (r1 , r2 , r3 , r4 ), so the wi have the
same sign. Conversely if the wi have the same sign, then w1 + w2 + w3 + w4 = 0
4 1
and 0 = i=1 ri Qi where (r1 , r2 , r3 , r4 ) = w1 +w2 +w 3 +w4
(w1 , w2 , w3 , w4 ) is such that
r1 , r2 , r3 , r4 > 0 sum to 1, so 0 lies in the interior of TQ .
Fix Q1 , Q2 , Q3 , Q4 and (w1 , w2 , w3 , w4 ). Then (C1 w1 , C2 w2 , C3 w3 , C4 w4 ) is a generator
of ker LP , where LP is defined using the Pi instead of the Qi . The numbers C1 w1 ,
C2 w2 , C3 w3 , C4 w4 have the same sign (all plus or all minus) for exactly 2 of the 24 = 16
choices of (C1 , C2 , C3 , C4 ). Thus, conditioned on a choice of the Qi , the probability
that TP contains the origin in its interior is 2/16 = 1/8. This is the same for any
(Q1 , . . . , Q4 ), so the overall probability that 0 lies inside TP also is 1/8.
Remark. As noted in [HoS], the same argument proves the following generalization.
160 The William Lowell Putnam Mathematical Competition
Remark. Here is a bizarre related fact: if five points are chosen at random from a
ball in R3 , the probability that one of them is contained in the tetrahedron generated
by the other four is 9/143 [So].
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.)
Solution. Write (1 + x + x2 + x3 )n as (1 + x2 )n (1 + x)n . The coefficient
n of xk
2j
gets contributions from the x term in the first factor (with coefficient j ) times the
n
xk−2j term in the second factor (with coefficient k−2j ).
Remark. This solution can also be stated in the language of generating functions:
Q(n, k)xk = (1 + x + x2 + x3 )n
k≥0
= (1 + x2 )n (1 + x)n
n 2j n i
= x x
j i
j≥0 i≥0
2j+i n n
= x
j i
j≥0 i≥0
n n
= xk .
j k − 2j
k≥0 j≥0
(–1, 1) (1, 1)
FIGURE 22.
The region of convergence.
Note that (x, y), (−x, y), (x, −y), and (−x, −y) produce the same sequence after the
first step, so will restrict attention to the first quadrant (x, y ≥ 0), and use symmetry
to deal with the other three.
Fix y; we will determine for which x (x, y) is in the region. Let f (w) = (w2 + y 2 )/2,
so an (x, y) = f n (x). If the limit exists and is L, then f (L) = L, so L = 1 ± 1 − y 2
(call these values L+ and L− ). It will be useful to observe that
x, f (x), f (f (x)), . . .
converges to L− .
Solutions: The Fifty-Third Competition (1992) 163
Remark (Noam Elkies). Although the proposer of this problem presumably had
polynomials with real or complex coefficients in mind, the same solution works for
"
polynomials over a field of characteristic greater #than 1992. When the characteristic
d1992 p(x)
is less than 1992, one can show that dx 1992 x −x is always zero, so the problem does
3
Solution 1. Subtract the first row from each of the other rows, to get
3 1 1 1 ··· 1
−2 3 0 0 · · · 0
−2 0 4 0 · · · 0
Dn = det −2 0 0 5
· · · 0 . (1)
.. .. .. .. .. .
. . . . . ..
−2 0 0 0 · · · n
Then for 2 ≤ i ≤ n − 1, add 2/(i + 1) times the ith column to the first column to
obtain
3 + 23 + 24 + · · · + n2 1 1 1 ··· 1
··· 0
0 3 0 0
0 0 4 0 ··· 0
Dn = det
0 0 0 5 ···
0 .
.. .. .. .. .. ..
. . . . . .
0 0 0 0 ··· n
The resulting matrix is upper triangular, so the determinant is the product of the
diagonal elements, which is
1 1
n! 1 + + · · · + .
2 n
Solutions: The Fifty-Third Competition (1992) 165
To prove this recursion, subtract the (n − 1)st column from the nth column, and then
expand along the nth column.
If all the ai are nonzero, we can write the polynomial Dn (a1 , . . . , an−1 ) in the form
1 1 1
Dn (a1 , . . . , an−1 ) = a1 a2 · · · an−1 1 + + + ··· + .
a1 a2 an−1
This problem is the special case ai = i + 1.
Remark. This formula can also be used for a generalization of Problem 1993B5;
see page 188.
Solution 4. The following result is Problem 7 of Part VII of [PS], and appeared
as Problem 1978A2 [PutnamII, p. 31].
Let a, b, p1 , p2 , . . . , pn be real numbers with a = b. Define
Then
p1 a a a ··· a a
b p ··· a
2 a a a
b b p ··· a
3 a a
det b b b p 4 ··· a a = bf (a) − af (b) . (3)
.. .. .. .. .. .. ..
b−a
. . . . . . .
b b b b ··· pn−1 a
b b b b ··· b pn
166 The William Lowell Putnam Mathematical Competition
yE (1 + CBE )BE = 0,
E∈M
where at least one term does not disappear and at least one term does disappear. As
before, the matrices BE run over M modulo sign. So we have a relation with fewer
terms, as desired.
Remark. This proof did not need (i) in an essential way. The only modification to
the proof needed to avoid using (i), is that instead of arranging for yI to be nonzero,
we might have y−I nonzero instead.
In fact, if M is nonempty, (i) follows from (ii), (iii), and (iv), as we now show.
Choose A ∈ M. Then ±A2 ∈ M, so ±I ∈ M by the first half of Solution 1. But
−I ∈ M contradicts (iv).
Remark. The result holds not only for real matrices, but also for matrices with
entries in any field k: if the characteristic of k is not 2, the proof proceeds as before;
if the characteristic is 2, then (ii) implies that M is empty.
Remark. An argument similar to that in the latter half of the solution proves
the following result of field theory (“independence of characters”): if L is a finite
extension of a field K, then the automorphisms of L over K are linearly independent
in the K-vector space of K-linear maps L → L [Ar, Theorem 12].
Solution 2. We prove the result more generally for complex matrices, by induction
on n.
If n = 1, then the elements of M commute so (iv) cannot be satisfied unless
M = {I}. Suppose that n > 1 and that the result holds for sets of complex matrices
of smaller dimension.
We may assume |M| > 1, so by (iv), there exist C, D ∈ M with CD = −DC. Fix
such C, D. As in Solution 1, C 2 = ±I, so the eigenvalues of C are ±λ where λ = 1
or i. Furthermore, Cn = Vλ ⊕ V−λ , where Vλ , V−λ are the eigenspaces corresponding
to λ and −λ (i.e., the nullspaces of (C − λI), (C + λI)) respectively. (Here we follow
the convention that the matrices are acting on Cn by right-multiplication.) Observe
that if X ∈ M then
Solution 3. Again we prove the result more generally for complex matrices. We
will use the following facts about the set S of irreducible complex representations of
a finite group G up to equivalence:
1. The number of conjugacy classes of G is |S|. [Se2, Theorem 7]
2. The number of one-dimensional representations in S is |G/G |, where G is the
commutator subgroup of G. (This is a consequence of the previous fact applied
to G/G , since all one-dimensional representations must be trivial on G .)
3. The sum of the squares of the dimensions of the representations in S equals
|G|. [Se2, Corollary 2]
As in Solution 1, we have A2 = ±I for any A ∈ M. Thus any finite subset
{A1 , . . . , Ak } ⊆ M generates a finite group G0 , whose elements are of the form
Remark. If we knew in advance that M were finite, the proof would be cleaner:
we could let G be the group { ±A : A ∈ M }.
Group theory interlude. Here we collect some facts from group theory that will be
used in the next remark to classify all possible M. First recall some definitions, from
pages 4, 8, and 183 of [Gor]. Let Z denote the center of a group G. If p is a prime,
then G is called a p-group if G is finite of order a power of p. An elementary abelian
p-group is a finite abelian group killed by p, hence isomorphic to (Z/pZ)k for some
integer k ≥ 0. A special p-group is a p-group G such that either G is elementary
abelian, or {1} G = Z G with Z and G/Z elementary abelian. Finally an
extraspecial p-group is a nonabelian special p-group G with |Z| = p.
There is a relatively simple classification of extraspecial p-groups [Gor, p. 204]. We
reproduce the classification for p = 2 here. First one has the dihedral group D of order
8 and the quaternion group Q of order 8. Identify the center of each of these with
{±1}. For integers a, b ≥ 0 not both zero, we let Ga,b denote the quotient of Da × Qb
by H ⊂ {±1}a+b , where H is the kernel of the multiplication map {±1}a+b → {±1}.
(This quotient is called a central product.) A group G is an extraspecial 2-group if
and only if G ∼ = Ga,b for some a, b as above. Moreover, Ga,b ∼ = Ga ,b if and only
if a + b = a + b and b ≡ b (mod 2). For convenience, we also define G0,0 = Z/2,
Remark. We are now ready to classify all possible M. The argument of Solution 3
shows that if M satisfies (i), (ii), (iii), (iv), then G = { ±A : A ∈ M } is a finite group
such that
(1) the center Z has order 2 and contains the commutator subgroup G ; and
(2) there is a faithful representation ρ : G → GLn (R) identifying Z with {±I}.
170 The William Lowell Putnam Mathematical Competition
Conversely, given a group G with ρ : G → GLn (R) satisfying (1) and (2), any set M
of coset representatives for {±I} in ρ(G) with I ∈ M satisfies (i), (ii), (iii), (iv).
Suppose that G and ρ satisfy (1) and (2). The argument at the beginning of
Solution 1 shows that every element of G/Z has order dividing 2; hence inversion on
G/Z is a homomorphism, and G/Z is an elementary abelian 2-group. Thus G is an
extraspecial 2-group or G ∼ = Z/2Z. (In particular |M| = |G|/2 is always a power of
4.) Since ρ is nontrivial on Z, η must occur in ρ. Conversely, if G = Ga,b for some
a, b ≥ 0, and ρ : Ga,b → Mn (R) is a real representation containing η , then G and ρ
satisfy (1) and (2), and hence we obtain all possibilities for M by choosing a set of
coset representatives for {±I} in ρ(G) with I ∈ M, for such G and ρ.
Remark. We can also determine all situations in the original problem in which
equality holds, i.e., in which M is a set of n2 matrices in Mn (R) satisfying (i), (ii),
(iii), (iv). In this case, G ∼
= Ga,b for some a ≥ 0 and b ∈ {0, 1}, |G| = 2n2 = 22a+2b+1 ,
and ρ is n-dimensional. Then dim η = 2a+b = n, and dim η equals n or 2n according
as b = 0 or b = 1. But ρ contains η , so ρ ∼ = η and b = 0. It follows that equality
is possible if and only if n = 2a for some a ≥ 0, and in that case M is uniquely
determined up to a change of signs of its elements not equal to I and up to an overall
conjugation.
Similarly, if we relax the conditions of the problem to allow M to contain complex
matrices, then the equality cases arise from n = 2a , G ∼ = Ga,0 or G ∼ = Ga−1,1 (the
∼
latter being possible only if a ≥ 1), and ρ = η.
Solutions: The Fifty-Fourth Competition (1993) 171
(b, c)
y=c
3
y = 2x – 3x
FIGURE 23.
Solution. Let (b, c) denote the rightmost intersection point. (See Figure 23.) We
wish to find c such that b
(2x − 3x3 ) − c dx = 0.
0
a unique positive solution, namely b = 2/3. Thus c = 4/9. To validate the solution,
we check that (2/3, 4/9) is rightmost among the intersection points of y = 4/9 and
y = 2x − 3x√ : the zeros of 2x − 3x − 4/9 = (2/3 − x)(3x + 2x − 2/3) other than 2/3
3 3 2
Prove there exists a real number a such that xn+1 = axn −xn−1 for all n ≥ 1.
Solution 1. Since the terms are nonzero, we can define an = (xn+1 + xn−1 )/xn
for n ≥ 1. It suffices to show a1 = a2 = · · · . But x2n+1 −xn xn+2 = 1 = x2n −xn−1 xn+1 ,
† The figure is omitted here, since it is almost identical to Figure 23 used in the solution.
172 The William Lowell Putnam Mathematical Competition
so
so x3 = ax2 − x1 .
By essentially the same algebra (and a simple induction), xn+1 = axn − xn−1 for
all n ≥ 1.
yn = Arn + Bsn ,
where A and B are constants, and r and s are the roots of the characteristic equation
t2 − at + 1 = 0. Then rs = 1, and (r − s)2 = a2 − 4 by the quadratic formula or by
the identity (r − s)2 = (r + s)2 − 4rs. Now
yn = (A + Bn)(±1)n .
Then
yn2 − yn+1 yn−1 = B 2 ,
which is independent of n. Hence as before, yn2 − yn+1 yn−1 = y12 − y2 y0 = 1 for all n,
so yn = xn for all n as well.
Solutions: The Fifty-Fourth Competition (1993) 173
g : { T ∈ Pn : T ⊇ S } → {2, 3, . . . , m}
current one, so the total number of xi ’s used so far is at most 19 − 1 = 18, and at
least one xi remains. Similarly, if t > 0 and a revisit has not yet occurred, then one
yj has been used after visiting each positive position except the current one, so the
total number of yj ’s used so far is at most 93 − 1 = 92, and at least one yj remains.
Since there are only finitely many xi ’s and yj ’s to be used, the algorithm must
eventually terminate with a revisit. The steps between the two visits of the same
position constitute a sum of some xi ’s equal to a sum of some yj ’s.
Our next solution is similar to Solution 1, but we dispense with the algorithmic
interpretation.
Solution 2. For the sake of generality, replace 19 and 93 in the problem statement
k !
by m and n respectively. Define Xk = i=1 xi and Y! = j=1 yj . Without loss of
generality, assume Xm ≥ Yn . For 1 ≤ @ ≤ n, define f (@) by
so 0 ≤ f (@) ≤ m. Let g(@) = Y! −Xf (!) . If g(@) = 0 for some @, we are done. Otherwise,
is a rational number.
176 The William Lowell Putnam Mathematical Competition
which is rational.
Solution 2. Set
t 2 1/(1−t) 2
x2 − x x2 − x
f (t) = dx + dx
−100 x3 − 3x + 1 1
101
x3 − 3x + 1
1−1/t 2
x2 − x
+ dx
101
100
x3 − 3x + 1
which is rational.
Remark. Both solutions reached the formula (1) in the middle, so we could
construct two more solutions by matching the first half of Solution 1 with the second
half of Solution 2, or vice versa.
11131110
Remark. The actual value of the sum of the three integrals is .
107634259
Related question. Let k be a positive integer, and suppose f (x) ∈ Q[x] has degree
at most 3k − 2. Then
−10 111 11
f (x) f (x) 10 f (x)
dx + dx + dx (1)
−100 (x − 3x + 1) (x − 3x + 1) 101 (x − 3x + 1)k
3 k 1 3 k 3
101 100
is rational.
Proof. We will use the theory of differentials on the projective line P1 . Let
τ (x) = 1 − 1/x. Then τ , as an automorphism of P1 , permutes the three zeros of
p(x) = x3 − 3x + 1 cyclically, since a calculation shows p(1 − 1/x) = −x−3 p(x). In
particular, τ 3 is the identity, since an automorphism of P1 is determined its action on
three distinct points, or by direct calculation.
f (x)
k dx on P . Because deg f ≤ 3k − 2, the
1
Let ω be the differential (x3 −3x+1)
substitution x = 1/t, dx = −t−2 dt shows that ω has no pole at ∞, so ω is regular on
all of P1 except possibly at the zeros of x3 − 3x + 1. −10
The substitutions used in Solution 1 transform (1) into −100 η where η = ω + τ ∗ ω +
(τ 2 )∗ ω. Then η is regular outside the zeros of x3 − 3x + 1. Since τ ∗ η = η, the residues
of η at the three zeros are equal, but the sum of the residues of any differential is
zero, so all the residues are zero. Hence η = dg for some rational function g on P1
having poles at most at the zeros of x3 − 3x + 1. Adding a constant to g, we may
assume g(0) = 0. We want to show that g has rational coefficients. Write g in lowest
terms, with monic denominator. Any automorphism σ of C over Q applied to the
coefficients of g results in another rational function g1 with dg1 = η and g1 (0) = 0.
Then d(g − g1 ) = 0, so g − g1 is constant, and evaluating
−10 at 0 shows that g = g1 . This
holds for all σ, so g ∈ Q(x). Finally, (1) equals −100 dg = g(−10) − g(−100), which
is rational.
of algebraic numbers are transcendental [FN, Corollary 2.2]. (Recall that a complex
number is algebraic if it is the zero of some nonzero polynomial with rational
coefficients, and transcendental otherwise.)
Remark. We can explain why for the polynomial p(x) = x3 − 3x + 1 there was a
fractional linear transformation with rational coefficients permuting its zeros cyclically.
An automorphism of P1 is uniquely determined by its action on any three distinct
points, so given any cubic polynomial p(x) ∈ Q[x] with distinct zeros, there is a unique
fractional linear transformation τ ∈ L(x) permuting the zeros, where L is the splitting
field of p(x). If σ ∈ Gal(L/Q), then σ acts on τ , and the action of στ on the three zeros
is obtained by conjugating the action of τ by the permutation of the zeros given by σ.
In particular, στ = τ for all σ ∈ Gal(L/Q) if and only if the Gal(L/Q) is contained in
the cyclic subgroup of order 3 of the permutations of the three zeros. Hence τ ∈ Q(x)
if and only if the discriminant of p(x) is a square. In the problem, the discriminant of
p(x) = x3 − 3x + 1 is 81.
Remark. This action of the group of order three on the projective line appeared
in Problem 1971B2 [PutnamII, p. 15]:
Let F (x) be a real valued function defined for all real x except for x = 0 and
x = 1 and satisfying the functional equation F (x) + F ((x − 1)/x) = 1 + x.
Find all functions F (x) satisfying these conditions.
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, . . .
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.)
Motivation. Assuming the result, we derive the value of r. Fix a large integer m.
The result implies that the mth 2 in the sequence occurs at the nth term, where
n ≈ rm. Interleaved among these m 2’s are n − m 3’s. By the self-generation
property of the sequence, these 2’s and 3’s describe an initial segment with n 2’s
separated by blocks containing a total of 2m + 3(n − m) 3’s. But the length of
this segment should also approximate r times the number of 2’s in the segment, so
n + 2m + 3(n − m) ≈ rn. Substituting n ≈ rm, dividing by m, and taking the limit√as
m → ∞ yields r + 2 + 3(r − 1) = r · r, so r2 − 4r + 1 = 0. Clearly r ≥ 1, so r = 2 + 3.
Note that 3 < r < 4.
√
Solution. Let r = 2 + 3. The sequence is uniquely determined by the
self-generation property and its first few terms. Therefore it suffices to show that
the sequence a0 , a1 , a2 , . . . has the self-generation property when we define an = 2 if
n = rm for some m, and an = 3 otherwise. (Note that the first term is a0 .)
Solutions: The Fifty-Fourth Competition (1993) 179
where
f (1) < f (2) < · · · < f (n) < · · · ,
(c, d ) (a + c, b + d )
(a, b)
FIGURE 24.
A proof without words of Lemma 1.
Solution 1. By Lemma 1,
m 2m + 1 m+1
< < .
1993 3987 1994
We will show that 3987 is best possible. If
1992 k 1993
< < (1)
1993 n 1994
then
1 n−k 1
> > ,
1993 n 1994
so
n
1993 < < 1994.
n−k
Clearly n − k = 1, so n − k ≥ 2. Thus n > 1993(n − k) ≥ 3986, and n ≥ 3987.
Solution 2. Subtracting everything in the desired inequality from 1, and using
the change of variables M = 1993 − m, K = n − k, the problem becomes: determine
the smallest positive integer n such that for every integer M with 1993 > M > 0,
there exists an integer K for which
M K M
> > , or equivalently, 1993K < nM < 1994K.
1993 n 1994
For M = 1, K cannot be 1 and hence is at least 2, so n > 1993 · 2 = 3986. Thus
n ≥ 3987. On the other hand n = 3987 works, since then for each M , K = 2M
satisfies the inequalities.
Solution 3 (Naoki Sato).
Lemma 2. Let a, b, c, d, p, and q be positive integers such that a/b < p/q < c/d,
and bc − ad = 1. Then p ≥ a + c and q ≥ b + d.
Proof. Since bp − aq > 0, bp − aq ≥ 1. Also, cq − dp > 0, so cq − dp ≥ 1. Hence
d(bp − aq) + b(cq − dp) ≥ b + d, which simplifies to (bc − ad)q ≥ b + d. But bc − ad = 1,
so q ≥ b + d. The proof of p ≥ a + c is similar.
Now
1992 k 1993
< <
1993 n 1994
for some k, and 1993·1993−1992·1994 = 1, so n ≥ 1993+1994 = 3987. And n = 3987
works, by Lemma 1.
182 The William Lowell Putnam Mathematical Competition
Remark. Looking at (1) was key. What clues suggest that it would be helpful to
look at large m?
Remark. This problem and Lemma 2 especially are related to the beautiful topic
of Farey series; see [Hon1, Essay 5].
Solution. Player B can always win, because B can always guarantee that A will
not win on the next move: B holds one more card than A, and each of A’s cards
causes at most one of B’s cards to be a fatal play. Hence B has at least one safe play.
Player B wins on the last move if not earlier, since the sum of the numbers on all the
cards is n(2n + 1).
Remark. David Savitt gives the following ‘alternate solution’: “I maintain that A,
playing optimally, will decline to participate!”
Solution. The probability that x/y is exactly half an odd integer is 0, so we may
safely ignore this possibility.
The closest integer to xy is even if and only if 0 < xy < 12 or 4n−1 2 < xy < 4n+12 for
some integer n ≥ 1. The former occurs inside the triangle with vertices (0, 0), (0, 1),
( 12 , 1), whose area is 14 . The latter occurs inside the triangle (0, 0), (1, 4n−1
2 2
), (1, 4n+1 ),
whose area is 4n−1 − 4n+1 . These regions are shown in Figure 25.
1 1
(1/2, 1)
(1, 2/3)
(1, 2/5)
(1, 2/7)
(1, 2/9)
…
FIGURE 25.
The interchange of integral and summation in the penultimate step is justified by the
Monotone Convergence Theorem [Ru, p. 319], since each integrand x4k − x4k+2 is
nonnegative on [0, 1].
Remark. This gives an interesting connection between π and number theory (and
gives an “experimental” way to estimate π). Here are more links. In fact, 6/π 2 is both
the probability that a pair of positive integers are relatively prime, and the probability
that a positive integer is squarefree (where these probabilities are appropriately defined
as limits). More generally, for any k ≥ 2, the probability that a set of k positive
integers has greatest common divisor 1, and the probability that a positive integer is
kth-power-free, is 1/ζ(k), where
1 1 1
ζ(k) = + k + k + ···
1k 2 3
is the Riemann zeta function. (See [NZM, Theorem 8.25] for a proof in the case n = 2;
the general case is similar.) It can be shown that ζ(2n) is a rational multiple of π 2n
184 The William Lowell Putnam Mathematical Competition
All of the following solutions involve finding a contradiction modulo some power
of 2. The first solution is long, but uses little more than coordinate geometry.
Solution 1. For real numbers x and y, and for a positive integer n, let “x ≡ y
(mod n)” mean that x − y is an integer divisible by n. Choose a coordinate system in
which the four points are (0, 0), (a, 0), (r, s), (x, y). Here a is an odd integer, and we
may assume a > 0. The square of an odd integer is congruent to 1 modulo 8, so if all
the pairwise distances are odd integers, we have
r2 + s2 ≡ 1 (mod 8)
(r − a) + s ≡ 1
2 2
(mod 8)
x +y ≡1
2 2
(mod 8)
(x − a) + y ≡ 1
2 2
(mod 8)
(x − r) + (y − s) ≡ 1
2 2
(mod 8).
Subtracting the first two yields 2ar ≡ a2 (mod 8). Thus r is a rational number whose
denominator is a multiple of 2 and a divisor of 2a. The same is true of x. Therefore
we can multiply all coordinates by the odd integer a, to reduce to the case where the
denominators of r and x are both 2. Then the congruence 2ar ≡ a2 (mod 8) between
integers implies r ≡ a/2 (mod 4). If r = a/2 + 4b, then
r2 = a2 /4 + 4ab + 16b2 ≡ a2 /4 (mod 4),
so the first congruence implies
s2 ≡ 1 − r2 ≡ 1 − a2 /4 (mod 4).
Similarly x ≡ a/2 (mod 4) and y 2 ≡ 1 − a2 /4 (mod 4). Also
x − r ≡ a/2 − a/2 ≡ 0 (mod 4),
so (x − r)2 ∈ 16Z, and the last of the five congruences yields
(y − s)2 ≡ 1 − (x − r)2 ≡ 1 (mod 8).
We will derive a contradiction from the congruences s2 ≡ y 2 ≡ 1 − a2 /4 (mod 4)
and (y − s)2 ≡ 1 (mod 8) obtained above. First,
(y + s)2 ≡ 2y 2 + 2s2 − (y − s)2
≡ 2(1 − a2 /4) + 2(1 − a2 /4) − 1
≡ 3 − a2
≡2 (mod 4).
Multiplying this integer congruence by (y − s)2 ≡ 1 (mod 8) yields (y 2 − s2 )2 ≡ 2
(mod 4). But y 2 and s2 are rational by the beginning of this paragraph, so y 2 − s2 is
a rational number with square congruent to 2 modulo 4. This is impossible.
186 The William Lowell Putnam Mathematical Competition
Solution 2.
Lemma. If r = cos α, s = cos β, and t = cos(α+β), then 1−r2 −s2 −t2 +2rst = 0.
Proof. We have
Suppose that O, A, B, C are four points in the plane such that a = OA, b = OB,
c = OC, x = BC, y = CA, z = AB are all odd integers. Using the Law of Cosines,
let
a2 + b2 − z 2
r = cos ∠AOB =
2ab
b2 + c2 − x2
s = cos ∠BOC =
2bc
c2 + a2 − y 2
t = cos ∠AOC = .
2ca
But ∠AOB + ∠BOC = ∠AOC as directed angles, so the lemma implies 1 − r2 − s2 −
t2 + 2rst = 0. Substituting the values of r, s, t, and multiplying by 4a2 b2 c2 yields
a contradiction.
Solution 3 (Manjul Bhargava). Suppose -v1 , -v2 , -v3 are vectors in 3-space. Then
the volume V of the parallelepiped spanned by the vectors is given by |-v1 · (-v2 ×-v3 )| =
| det M |, where M = (-v1-v2-v3 ) is the 3 × 3 matrix with entries given by the vectors -v1 ,
-v2 , -v3 . Since det M = det M T ,
-v1 · -v1 -v1 · -v2 -v1 · -v3
V 2 = M · M T = det -v2 · -v1 -v2 · -v2 -v2 · -v3 . (1)
-v3 · -v1 -v3 · -v2 -v3 · -v3
The volume of the tetrahedron spanned by the vectors is V /6. If the edges of the
tetrahedron are a = |-v1 |, b = |-v2 |, c = |-v3 |, x = |-v2 − -v3 |, y = |-v3 − -v1 |, z = |-v1 − -v2 |,
then by the Law of Cosines, written as
Suppose now that there were 4 points as described in the problem. Locate one point
at the origin, and let -v1 , -v2 , -v3 be the vectors from the origin to the other three; they
are coplanar, so V = 0. Since squares of odd integers are congruent to 1 modulo 8,
2 1 1
8V 2 ≡ det 1 2 1 ≡ 4 (mod 8),
1 1 2
Solution 4. Suppose as before there were 4 such points; define -v1 , -v2 , -v3 as in
the previous solution. Then -vi · -vi ≡ 1 (mod 8), and from (2), 2-vi · -vj ≡ 1 (mod 8) for
i = j as well.
No three of the points can be collinear. Hence -v3 = x-v1 + y-v2 for some scalars x
and y. Then
(by the two-dimensional version of (3)) so the first two equations in (4) have a unique
rational solution for x, y, say x = X/D, y = Y /D, where X, Y , and D are integers.
We may assume gcd(X, Y, D) = 1. Then multiplying (4) through by D we have
D ≡ 2X + Y (mod 8)
D ≡ X + 2Y (mod 8)
2D ≡ X + Y (mod 8).
Adding the first two congruences and subtracting the third gives 2X+2Y ≡ 0 (mod 8),
so, by the third congruence, D is even. But then the first two congruences force X
and Y to be even, giving a contradiction.
188 The William Lowell Putnam Mathematical Competition
y y1
y = x/2 y = 3x1 /2
x x1
FIGURE 26.
192 The William Lowell Putnam Mathematical Competition
the region S bounded by y = mx, the y-axis, and x2 /9 + y 2 = 1 into the region S
bounded by y1 = 3mx1 , the y1 -axis, and the circle. Since all areas are multiplied by
the same (nonzero) factor under the linear transformation, R and S have the same
area if and only if R and S have the same area. However, we can see by symmetry
about the line y1 = x1 that this happens if and only if 3m = 2/3, that is, m = 2/9.
Solution 2 (Noam Elkies). Apply the linear transformation (x, y) → (3y, x/3).
This preserves area, and the ellipse x2 /9 + y 2 = 1. It switches the x and y axes, and
takes y = x/2 to the desired line, x/3 = (3y/2), i.e. y = (2/9)x. Thus m = 2/9.
Remark. There are, of course, less enlightened solutions. Setting up the integrals
for the two areas yields the equation
3/√13 " # 3/√1+9m2 " #
9 − 9y 2 − 2y dy = 1 − x2 /9 − mx dx.
0 0
At this point, one might guess that a substitution y = cx will transform one integral
into the other, if c and m satisfy
3 3
√ = c√ , 3c = 1, 2c2 = m,
13 1 + 9m2
and in fact, c = 1/3 and m = 2/9 work. If this shortcut is overlooked, then as a last
resort one could use trigonometric substitution to evaluate both sides: this yields
3 3 3 1
Arcsin √ = Arcsin √ .
2 13 2 1 + 9m2
Solving yields m = 2/9.
Solution. Suppose that it is possible to √ color the points of the triangle with four
colors so that any two points at least 2 − 2 apart receive different colors. Suppose
the vertices √
of the triangle are A =
√ (0, 0), B = (1, 0), C = (0, 1). Define √ also
√ the
points D =√( 2 − 1, 0)√ and E = (0, 2 − 1) on the two sides, and F = (2 − 2, 2 − 1)
and G = ( 2 − 1, 2 − 2) on the diagonal; see Figure 27. Note that
√
BD = BF = CE = CG = DE = DG = EF = 2 − 2.
The color of B must be different from the colors of the other named points. The same
holds for C. Thus the vertices of the pentagram AGDEF must each be painted one
of the two remaining colors. Then two adjacent vertices
√ of the pentagram must have
the same color. But they are separated by at least 2 − 2, so this is a contradiction.
Solutions: The Fifty-Fifth Competition (1994) 193
E F
A D B
FIGURE 27.
√
Remark. The 2 − 2 in the problem is best possible. If we give triangles ADE,
BDF , CEG, and quadrilateral DEGF each their own color, coloring √ common edges
arbitrarily, then no two points at distance strictly greater than 2− 2 receive the same
color.
Related questions. There are many problems of this sort. Other typical examples
are Problems 1954M2 and 1960M2 [PutnamI, pp. 41, 58]:
Consider any five points P1 , P2 , P3 , P4 , P5 in the interior of a square S of
side-length 1. Denote by dij the distance between√the points √ Pi and Pj . Prove
that at least one of the distances dij is less than 2/2. Can 2/2 be replaced
by a smaller number in this statement?
Show that if three points
√ are √
inside a closed square of unit side, then some
pair of them are within 6 − 2 units apart.
Problem 1988A4 also is similar.
Solution. A square matrix M with integer entries has an inverse with integer
entries if and only if det M = ±1: if N is such an inverse, (det M )(det N ) =
det(M N ) = 1 so det M = ±1; conversely, if det M = ±1, then ±M is an inverse
with integer entries, where M is the classical adjoint of M . Let f (x) = det(A + xB).
Then f (x) is a polynomial of degree at most 2, such that f (x) = ±1 for x = 0, 1, 2,
3, and 4. Thus by the Pigeonhole Principle f takes one of these values three or more
times. But the only polynomials of degree at most 2 that take the same value three
times are constant polynomials. In particular, det(A + 5B) = ±1, so A + 5B has an
inverse with integer entries.
194 The William Lowell Putnam Mathematical Competition
with i1 < i2 < · · · < i1994 . Show that every nonempty interval (a, b) contains
a nonempty subinterval (c, d) that does not intersect S.
sn = rf (n,1) + rf (n,2) + · · · + rf (n,1994) with f (n, 1) < f (n, 2) < · · · < f (n, 1994).
The sequence (rf (n,1) )n≥0 has a monotonically nonincreasing subsequence (since
(rn )n≥0 is a positive sequence converging to 0). Thus we may replace (sn )n≥0 by a
subsequence for which (rf (n,1) )n≥0 is monotonically nonincreasing. In a similar fash-
ion, we pass to subsequences so that, successively, each of (rf (n,2) )n≥0 , (rf (n,3) )n≥0 ,
. . . , (rf (n,1994) )n≥0 may be assumed to be monotonically nonincreasing. The resulting
(sn )n≥0 is monotonically nonincreasing.
Remark. A totally ordered set T is well-ordered if and only if every nonempty
subset has a least element. This condition is equivalent to the condition that every
sequence in T contain a nondecreasing subsequence. Hence −S is well-ordered under
the ordering induced from the reals. Solution 2 can be interpreted as proving that
Solutions: The Fifty-Fifth Competition (1994) 195
a finite sum of well-ordered subsets of the reals is well-ordered. See the remark on
Zorn’s Lemma in 1989B4 for more on well orderings.
preserve A.
Proof 1 of Lemma (inductive). The lemma is true for n = 1, so assume it it is true
for all n < k (for some k > 1), and false for n = k. Then by the Pigeonhole Principle,
there are e1 , . . . , ek−1 ∈ {0, 1} such that both
e e
f1e1 ◦ f2e2 ◦ · · · ◦ fk−1
k−1
and f1e1 ◦ f2e2 ◦ · · · ◦ fk−1
k−1
◦ fk
Proof 2 of Lemma (noninductive). Let k be the largest integer such that fk does
not map A to itself, and suppose that more than 2n−1 of the functions Fn map A to
itself. By the Pigeonhole Principle, there are
m2 ≥ N − 250 ≥ (m − 1)2 + 1.
Subtraction shows that these imply
28m + 196 ≤ 500 ≤ 32m + 222,
which implies m = 9 or 10.
If m = 9, the two conditions 232 ≤ N + 250 ≤ 242 − 1, 92 ≥ N − 250 ≥ 82 + 1 are
equivalent to 315 ≤ N ≤ 325. If m = 10, the two conditions 242 ≤ N + 250 ≤ 252 − 1,
102 ≥ N − 250 ≥ 92 + 1 are equivalent to 332 ≤ N ≤ 350.
a<0 a≥0
FIGURE 28.
Graphs of y = x4 + ax2 for a < 0 and a ≥ 0.
has four distinct real solutions α1 , α2 , α3 , α4 . If we can find four distinct real numbers
such that
α1 + α2 + α3 + α4 = −9 (1)
α1 α2 + α1 α3 + α1 α4 + α2 α3 + α2 α4 + α3 α4 = c, (2)
then we can choose m and b appropriately so that q(x) has these four zeros (by the
34
expansion of i=1 (x − αi )).
Then from
we get c < 243/8. Conversely, we must show that if c < 243/8, then we can find
distinct real α1 , α2 , α3 , α4 satisfying (1) and (2). This is indeed possible; try
(α1 , α2 , α3 , α4 ) = (9/4 − µ, 9/4 + µ, 9/4 − ν, 9/4 + ν) where µ and ν are distinct
positive numbers. Then (1) is automatically satisfied, and we can choose µ and ν so
that the right side of (3), which is 8(µ2 + ν 2 ), is any desired positive number.
198 The William Lowell Putnam Mathematical Competition
Remark. The previous two solutions highlight two ways of constructing a line for
given c. Other possible tools to do this include Rolle’s Theorem, the Mean Value
Theorem [Spv, Ch. 11, Theorem 4], Descartes’ Rule of Signs, and more. Also, another
quick way to see that c < 243/8 is necessary is to consider the discriminant of the
quadratic P (x).
Related question. A related problem is 1977A1 [PutnamII, p. 29]:
Consider all lines which meet the graph of
y = 2x4 + 7x3 + 3x − 5
in four distinct points, say (xi , yi ), i = 1, 2, 3, 4. Show that
x1 + x2 + x3 + x4
4
is independent of the line and find its value.
n
1 1 a b
that = for some a, b ∈ Z depending on n. Taking determinants
2 1 2b a
2
1 1 3 2
shows a2 − 2b2 = (−1)n . But = , so
2 1 4 3
n 2
3 2 1 0 a b 1 0
− = −
4 3 0 1 2b a 0 1
2
a + 2b − 1
2
2ab
= .
4ab a2 + 2b2 − 1
If n is odd then a2 − 2b2 = −1, so a2 + 2b2 − 1 = 2a2 and all entries are divisible by
a. If n is even a2 − 2b2 = 1, so a2 + 2b2 − 1 = 4b2 and all entries are divisible by b.
Both a and b increase as n → ∞ (by the same argument as in Solution 1), so we are
done.
This is clear for k = 0 and, for the inductive step, using A2 − 6A + I = 0 (the
characteristic equation), we have
In either case, the entries of An − I have a common factor that goes to ∞ since
limn→∞ rn = ∞.
Solution √4. The entries of√ An are each of the form α1 λn1 + α2 λn2 , where
λ1 = 3 + 2 2 and λ2 = 3 − 2 2 are the eigenvalues of A. This follows from
diagonalization (as suggested by our hint), or from the theory of linear recursive
relations and the Cayley-Hamilton Theorem: the latter yields A2 − 6A + I = 0,
so An+2 − 6An+1 + An = 0 for all n, and each entry of An satisfies the recursion
xn+2 − 6xn+1 + xn = 0. Using the entries for n = 1, 2, we derive
n n n n
λ1 +λ2 λ1 −λ2
√
An = λn −λn
2 2 2
λn n .
1√ 2 1 +λ2
2 2
200 The William Lowell Putnam Mathematical Competition
√ √
Since λi = µ2i where µ1 = 1 + 2 and µ2 = 1 − 2, we see
n
λ1 + λn2 λn − λn
dn = gcd − 1, 1 √ 2
2 2 2
n
(µ1 − µ2 ) (µ1 − µn2 )(µn1 + µn2 )
n 2 n
= gcd , √
2 2 2
n n
(µ1 − µ2 )n
(µ1 − µn2 ) (µn1 + µn2 )
= √ gcd √ ,
2 2 2 2
√
since (µn1 −µn2 )/ 2 and (µn1 +µn2 )/2 are (rational) integers. Since |µ1 | > 1 and |µ2 | < 1,
we conclude limn→∞ (µn1 − µn2 ) = ∞. Hence limn→∞ dn = ∞.
Solution 5. The characteristic polynomial of A is x2 − 6x + 1, so A has distinct
√ λ 0
eigenvalues λ, λ−1 , where λ = 3+2 2. Hence A = CDC −1 where D = and
√ 0 λ−1
C is an invertible matrix with entries√in Q( 2). Choose an integer k ≥ 1 such that
the entries of kC and kC−1 are in Z[ 2]. Then k (A − I) = (kC)(D − I)(kC )
2 n n −1
1 0 √
and Dn − I = (λn − 1) so λn − 1 divides k 2 dn in Z[ 2]. Taking norms,
0 λ−n
we find that the (rational) integer (λn − 1)(λ−n − 1) divides k 4 d2n . But |λ| > 1, so
|(λn − 1)(λ−n − 1)| → ∞ as n → ∞. Hence limn→∞ dn = ∞.
Remark.
Each solution generalizes to establish the same result for integral matrices
a b
A= of determinant 1 and | trace(A)| > 1 (the latter to guarantee rn → ∞
c d
where rn = trace(A)rn−1 − rn−2 ).
Solution 1. We will show that α satisfies the conditions of the problem if and
only if
1/n
1 n2 − n + 1
1− ≤α< ,
n2 n2
and then show that this interval is nonempty.
We have fαk (n2 ) = n2 − k for k = 1, . . . , n if and only if α(n2 − k + 1) = n2 − k
for k = 1, . . . , n, which holds if and only if
n2 − k
≤α<1 for k = 1, . . . , n.
n2 −k+1
Since
n2 − k 1
=1− 2
n2 −k+1 n −k+1
decreases with k, these hold if and only if 1 − n12 ≤ α < 1. We assume this from now
on.
Next we consider the conditions fαk (n2 ) = n2 − k for k = 1, . . . , n. Since fαk (n2 ) is
an integer less than αk n2 , we have fαk (n2 ) ≤ fαk (n2 ). We have already arranged that
fαk (n2 ) = n2 − k, so fαk (n2 ) = n2 − k if and only if αk n2 < n2 − k + 1. Moreover, if
the latter holds for k = n, then it holds for k = 1, . . . , n by reverse induction, since
multiplying αk n2 < n2 − k + 1 by
n2 1 1 n2 − (k − 1) + 1
α−1 ≤ = 1 + ≤ 1 + ≤
n2 − 1 n2 − 1 n2 − k + 1 n2 − k + 1
yields the inductive step. Hence all the conditions hold if and only if
2 1/n
1 n −n+1
1− 2 ≤α < .
n n2
It remains to show that this interval is nonempty, or equivalently, that
n
1 1 1
1− 2 < 1 − + 2. (1)
n n n
First we will prove
n 2
(1 − x)n ≤ 1 − nx + x for 0 ≤ x ≤ 1. (2)
2
The two sides are equal at x = 0, so it suffices to show that their derivatives satisfy
Again the two sides are equal at x = 0, so, differentiating again, it suffices to show
Remark. Inequality (2) is a special case of the fact that for real a > b > 0 and
integers 0 < k < n, the partial binomial expansion
n n−1 k n
a −
n
a b + · · · + (−1) an−k bk (3)
1 k
is greater than or less than (a − b)n , according to whether k is even or odd. It can
be proved by the same argument used to prove (2). This is sometimes called the
Inclusion-Exclusion Inequality, because if a, b are sizes of sets A B ∅, then (3)
is the overestimate or underestimate for #(A − B) obtained by terminating the
n
The following lemma states that 2 is a primitive root modulo the prime 101.
Lemma. 2a ≡ 1 (mod 101) if and only if a is divisible by 100.
Proof. We need to show that the order m of the image of 2 in the group (Z/101Z)∗
is 100. Since the group has order 100, m divides 100. If m were a proper divisor of
100, then m would divide either 100/2 = 50 or 100/5 = 20, so either 250 or 220 would
be 1 modulo 101. But we compute
210 = 1024 ≡ 14 (mod 101)
220 ≡ 142 ≡ −6 (mod 101)
240 ≡ (−6)2 ≡ 36 (mod 101)
2 50
≡ 36 · 14 ≡ −1 (mod 101).
Corollary 1. If a and b are nonnegative integers such that 2a ≡ 2b (mod 101),
then a ≡ b (mod 100).
Proof. Without loss of generality, assume a ≥ b. If 101 divides 2a −2b = 2b (2a−b −1),
then 2a−b ≡ 1 (mod 101), so a − b ≡ 0 (mod 100) by the lemma.
or equivalently
0 ≡ (2a − 2c )(2a − 2d ) (mod 101).
(That such a factorization exists could have been guessed from the desired conclusion
that a = c or a = d.) Hence 2a ≡ 2c (mod 101) or 2a ≡ 2d (mod 101). By the
corollary above, a is congruent to c or d modulo 100. Then by (1), b is congruent to
the other. But 0 ≤ a, b, c, d ≤ 99, so these congruences are equalities.
Remark. A more conceptual way to get from (2) and (3) to the conclusion that 2a ,
2 are congruent to 2c , 2d in some order, modulo 101, is to observe that (x−2a )(x−2b )
b
and (x − 2c )(x − 2d ) are equal as elements of the polynomial ring F101 [x] over the finite
field F101 . Then take the multiset of zeros of each.
204 The William Lowell Putnam Mathematical Competition
converge?
Answer. The integral converges if and only if a = b.
√
Solution. Using 1 + t = 1 + t/2 + O(t2 ) repeatedly, we obtain
%2
$√
√ a
x + a − x = x1/4 1+ −1
x
2
a
=x 1/4
+ O(x−2 )
2x
2
a −1/4
= x 1 + O(x−1 )
2
% 2
$ √
√ b
x− x−b=x 1/4
1− 1−
x
2
b
= x1/4 + O(x−2 )
2 2x
b −1/4
= x 1 + O(x−1 ) .
2
∞
Thus the original integrand is a/2 − b/2 x−1/4 + O(x−5/4 ). Since b x−5/4 dx
∞
converges, the original
∞ −1/4integral converges if and only if b a/2 − b/2 x−1/4 dx
converges. But b x dx diverges, so the original integral converges if and only if
a = b.
Remark. See 1988A3 for a similar argument.
Solutions: The Fifty-Sixth Competition (1995) 205
Remark. In the case a = b, one can show the integral converges by a “telescoping”
argument. Write
d $ $
√ √ √ √
x+a− x− x − x − a dx
c
$√ $√
d √ d−a √
= x + a − x dx − x+a− x dx
c c−a
$√ $√
d √ c−a √
= x + a − x dx − x + a − x dx.
d−a c
As d → ∞ for fixed c, the second term is constant, while the first term tends to 0. (It
is an integral over an interval of fixed length, and the integrand tends to 0 uniformly.)
This suggests choosing m such that Sm is maximal, and cutting between m and
m + 1. Indeed, if we do so, then
k(n − 1) k
Sm+k − Sm + ≤k− ,
n n
but the left side is an integer, so we can replace the right side by k − 1.
Remark. In fact, this argument shows that the location of the cut is unique,
assuming that the orientation of the necklace is fixed. Namely, for any other choice
of m, we would have Sm+k − Sm + k(n−1) n ≥ k(n−1)
n for some k, but the left side is
an integer, so we may replace the right side by k. (This implies in particular that the
maximal Sm is unique up to replacing m by m + in, but this was already evident: the
Sj have distinct fractional parts, so no two are equal.)
For a more visual reinterpretation, plot the points (i, z1 + · · · + zi ) for i ≥ 1. The
set of these points is mapped into itself by translation by (n, n − 1), and the upper
support line of slope (n − 1)/n of this set passes through (m, z1 + · · · + zm ), where m
is as chosen above.
for some constants aij > 0. Suppose that for all i, xi (t) → 0 as t → ∞. Are
the functions x1 , x2 , . . . , xn necessarily linearly dependent?
Answer. Yes, the functions must be linearly dependent.
Solution. If (v1 , . . . , vn ) is a (complex) eigenvector of the matrix (aij ) with
(complex) eigenvalue λ, then the function y = v1 x1 +· · ·+vn xn satisfies the differential
equation
dy
= vi ai,j xj = λvj xj = λy.
dt i,j j
show that 4f (0, 0, 0, n) ≤ f (0, 0, 0, n + 1) for some n ≥ 1995. Suppose this were not
the case; then we would have f (0, 0, 0, n) = O(4n ) as n → ∞. On the other hand,
f (0, 0, 0, 6m) is at least the number of 3 × 6m matrices such that each permutation
of 1, 2, 3 appears
in exactly
m columns. The latter number
equals6mthe multinomial
6m 6m
coefficient m,m,m,m,m,m , so we would have m,m,m,m,m,m = O(4 ). This rate of
growth contradicts the fact that
6(m+1)
m+1,m+1,m+1,m+1,m+1,m+1
lim 6m
m→∞
m,m,m,m,m,m
(6m + 6)(6m + 5)(6m + 4)(6m + 3)(6m + 2)(6m + 1)
= lim
m→∞ (m + 1)(m + 1)(m + 1)(m + 1)(m + 1)(m + 1)
= 66 .
A related fact is that the random walk is recurrent: the expected number of returns
∞
to the origin is infinite, or equivalently, n=1 f (x, y, z, n)/6n diverges. This is not
true of the corresponding random walk on a lattice of three (or more) dimensions.
Let θ = x/a in the second integral and write 1 as sin2 θ + cos2 θ; the result is
2π 2π $
2
2 2 2
a sin θ + b cos θ dθ = a2 sin2 θ + (a2 + c2 ) cos2 θ dθ.
0 0
Since the left side is increasing as a function of b, we have equality if and only if
b2 = a2 + c2 .
Solution 2. As in Solution 1, it suffices to find the relation between a, b, c that
makes the length of one period of the sine curve equal to the perimeter of the ellipse.
We will show that b2 = a2 + c2 . By scaling a, b, c, we may assume a = 1.
In the strip 0 ≤ θ ≤ 2π in the (θ, z)-plane, graph one period S of the curve
z = c sin θ. Curl the strip and glue its left and right edges to form the cylinder
210 The William Lowell Putnam Mathematical Competition
x2 + y 2 = 1 in (x, y, z)-space so that a point (θ, z) on the strip maps to (cos θ, sin θ, z)
on the cylinder. Then S is mapped to the curve E described parametrically by
(x, y, z) = (cos θ, sin θ, c sin θ) for 0 ≤ θ ≤ 2π, and S and E have the same length.
The parameterization is of the form (cos θ)-v + (sin θ)w - where -v = (1, 0, 0) and
w- = (0, 1, c) are orthogonal
√ vectors, so E is an ellipse with semi-axes of lengths
|-v | = 1 and |w| 2
- = 1 + c . (Alternatively, this can be seen geometrically, since E is
the intersection of the plane z = cy with the cylinder.) Thus when b2 = 1 + c2 , the
length of S equals the perimeter of the ellipse with semi-axes of lengths 1 and b.
On the other hand, the length of S is an increasing function of |c|. (If this is not
clear geometrically, consider the arc length formula from calculus.) Hence for fixed b,
the only values of c for which the length of S equals the perimeter of the ellipse with
semi-axes of lengths 1 and b are those for which b2 = 1 + c2 .
Remark. Noam Elkies points out that it is not obvious that the condition
b2 = a2 + c2 is sufficient for the rolling to be physically possible: it is conceivable
that the ellipse could be too fat to touch the bottom of the sine curve. We show that
the rolling is in fact physically possible if b2 = a2 + c2 , for an appropriately chosen
starting point, by showing that the radius of curvature of the ellipse at any point is
always less than that of the sine curve at the corresponding point.
The radius of curvature of the curve y = c sin(x/a) at (x, y) is
(See [Ap2, pp. 538–539] for the basic properties of the radius of curvature.) If we
start with the points θ = 0 of the ellipse and x = 0 of the sine curve in contact, the
parameters will be related by the equation θ = x/a. Since ac| sin(x/a)| ≤ ac < ab,
the radius of curvature of the sine curve will always be larger than that of the ellipse
at the corresponding point, so the rolling will be physically possible.
Remark. The result of the previous calculation can also be explained by the
geometry of Solution 2. Since we obtain the ellipse by rolling up one period of the
sine curve, it suffices to prove the following geometrically believable claim: Rolling
up a curve does not increase the radius of curvature at any point. Here “rolling up a
curve” means taking the image of a smooth curve in the (θ, z)-plane under the map
(θ, z) !→ (cos θ, sin θ, z).
To prove the claim, parameterize the smooth curve by (θ(t), z(t)) so that the speed
for all t is 1. The radius of curvature is 1/|-a|, where -a is the acceleration [Ap2, p. 538].
Hence it remains to show that the magnitude of the acceleration is not decreased by
rolling up.
-
Let -a(t) and A(t) be the accelerations of the original and rolled-up curves, respec-
tively. For the original curve, the velocity is (θ , z ) and the acceleration is -a = (θ , z ),
so the magnitude of the acceleration is |-a| = (θ )2 + (z )2 .
Solutions: The Fifty-Sixth Competition (1995) 211
For the image curve, the velocity is (−θ sin θ, θ cos θ, z ). The speed is (θ )2 + (z )2
= 1. (We expect this, since “rolling up” is an isometric embedding: it does not involve
stretching the paper.) The acceleration is
- = (−θ sin θ − (θ )2 cos θ, θ cos θ − (θ )2 sin θ, z ),
A
so
- 2 = (θ )2 + (z )2 + (θ )4 = |-a|2 + (θ )4 ≥ |-a|2 ,
|A|
as desired. Equality holds precisely when the original curve is moving only in the
z-direction (i.e., when the curve has a vertical tangent vector); this never happens for
the sine curve.
√
a+b c
Express your answer in the form d , where a, b, c, d are integers.
√
Answer. The expression equals (3 + 5)/2.
212 The William Lowell Putnam Mathematical Competition
Solution. The infinite continued fraction is defined as the limit L of the sequence
defined by x0 = 2207 and xn+1 = 2207 − 1/xn ; the limit exists because the sequence
is decreasing (by a short induction). Also, L must satisfy L = 2207 − 1/L. Moreover,
xi > 1 for all i by induction, so L ≥ 1. Let r = L1/8 , so r8 + r18 = 2207. Then
2
4 1 1
r + 4 = 2207 + 2 = 472 , so r4 + 4 = 47;
r r
2
2 1 1
r + 2 = 49, so r2 + 2 = 7; and
r r
2
1 1
r+ = 9, so r + = 3.
r r
√ √
Thus r2 − 3r + 1 = 0, so r = 3± 5
2 . But r = L1/8 ≥ 1, so r = 3+ 5
2 .
Remark. This question deals with the asymptotic behavior of the dynamical system
given by x0 = 2207, xn+1 = 2207 − 1/xn . See 1992B3 for another dynamical system.
Stronger result. Let Ln denote the nth Lucas number: that is, L0 = 2, L1 = 1,
and Ln+2 = Ln+1 + Ln for n ≥ 0. Then it can be shown [Wo] that for any n > 0,
% √
1 3 + 5
2n −
n L = .
L2n − L −···
1
2n
2
move to a state labelled 2nd, and for each state labelled 2nd, arrows to all states that
can be reached in one move. If all paths eventually lead to the state in which there
are no heaps left and the second player is to move, then the first player has a winning
strategy. Figure 29 shows a state diagram for a smaller instance of the problem: it
gives a winning strategy for the first player in the game with heaps of size 3, 3, and 5.
(3, 3, 5 : 1st)
(3, 3, 4 : 2nd)
o PPP
ooooo PPP
PPP
oo PPP
wooo '
(3, 4 : 1st) (2, 3, 4 : 1st) (3, 3, 3 : 1st)
(2, 2, 4 : 2nd) (3, 3 : 2nd)
o
ooooo
oo
wooo
(2, 4 : 1st) (2, 2, 3 : 1st) (2, 3 : 1st)
PPP
PPP
PPP
PPP
'
(4 : 2nd) (2, 2 : 2nd)
x
(3 : 1st) (2 : 1st)
OOO nn
OOO
OOO nnnnn
OO' nn
wnnn
(∅ : 2nd)
FIGURE 29.
An example of a state diagram.
Remark. In the language of game theory, this game is normal (the last player to
move wins) and impartial (the options in any given position are the same for both
players). The classic example of such a game is Nim: the game starts with some piles
of sticks, and each player in turn can remove any number of sticks from a single pile.
It has long been known that one can determine who wins in a given Nim position by
adding the sizes of the piles in base 2 without carries: the position is a second player
win if the sum is zero. The point is that every position with nonzero sum has a move
to a zero position, but every zero position has moves only to nonzero positions. So
from a nonzero position, the first player can arrange to move only to zero positions;
when the game ends, it must do so after a move by the first player.
214 The William Lowell Putnam Mathematical Competition
The main result of Sprague-Grundy theory [BCG, Volume 1, Ch. 3, p. 58] is that
every normal impartial game works the same way! Explicitly, to each position one
assigns a “nim-value” which is the smallest nonnegative integer not assigned to any
position reachable from the given position in one move. In particular, the final position
has value 0, and a position is a second player win if and only if it has value 0. The
result then is that the value of a disjunction of two positions (in which a player may
move in one position or the other) is obtained by adding the values of the positions
in base 2 without carries.
In the original problem, piles of size 0, 2, 3, 4, 5, 6 have values 0, 1, 2, 0, 1, 0, so
the initial position has value 2 ⊕ 0 ⊕ 1 ⊕ 0 = 3, and the winning first move creates a
position of value 1 ⊕ 0 ⊕ 1 ⊕ 0 = 0, as expected.
Weyl’s Equidistribution Theorem, which can be proved in the same way as the one-
dimensional case in [Kör, Theorem 3.1 ].
Reinterpretation. The multidimensional version of Weyl’s Equidistribution The-
orem can be deduced from the following fact: every continuous function on the n-
dimensional unit cube can be uniformly approximated by finite linear combinations
of characters. (A character is a continuous group homomorphism from Rn /Zk to C∗ ;
each such homomorphism is
(x1 , . . . , xk ) !→ exp(2πi(a1 x1 + · · · + ak xk ))
for some a1 , . . . , ak ∈ Z.) The approximation assertion follows from basic properties of
Fourier series, which are ubiquitous in physics and engineering as well as mathematics.
See [Kör, Theorem 3.1 ] for the proof in the k = 1 case, and [DMc, Section 1.10] for
the general case.
Related question. Problem 1979A5 [PutnamII, p. 33] is related:
Denote by [x] the greatest integer less than or equal to x and by S(x) the
sequence [x], [2x], [3x], . . . . Prove that there are distinct real solutions α and
β of the equation x3 − 10x2 + 29x − 25 = 0 such that infinitely many positive
integers appear both in S(α) and S(β).
Remark. If α and β are irrational and 1/α+1/β = 1, then S(α) and S(β) partition
the positive integers (Beatty’s Theorem). See 1993A6 for another instance of this fact,
and the solution to that problem for further discussion.
Solutions: The Fifty-Seventh Competition (1996) 217
there is a unique pair (x, y) with x = λy > y > 0 and x2 + y 2 = 1. For this pair, we
have 1 = x2 + y 2 = (λ2 + 1)y 2 = (2λ + 2)y 2 , so
x(x + y) = (λ2 + λ)y 2
λ2 + λ
=
2λ + 2
λ
=
2 √
1+ 2
= .
2
√ √
At the endpoints (1, 0) and
√ ( 2/2, 2/2) of the closure of the arc, we have x(x+y) = 1,
so the maximum is (1 + 2)/2.
218 The William Lowell Putnam Mathematical Competition
if any students choose more or fewer than 3 courses, we get strict inequality and a
contradiction.
Remark. A consequence of the previous observation is that the example given
above is unique if we assume no two students choose the same set of courses. On the
other hand, there exist other counterexamples to the assertion of the problem in which
more than one student selects the same set of courses. Here is an elegant construction
attributed to Robin Chapman. Take an icosahedron, and label its vertices with the
names of the 6 courses so that two vertices have the same label if and only if they
are antipodal. For each of the 20 faces of the icosahedron, have one student select the
three courses labelling the vertices of the face; then antipodal faces give rise to the
same set of courses. Concretely, if the courses are A, B, C, D, E, F , the sets could be
ABC, ACD, ADE, AEF , AF B, BCE, CDF , DEB, EF C, F BD.
Literature note. The study of problems such as this one, asking for combinatorial
structures not containing certain substructures, is known as Ramsey theory. See [Gr1]
for an introduction.
Any prime p > 3 is of one of the forms 6r + 1 or 6s + 5. In the former case, k = 4r and
p−k/2 = 4r +1 = k +1. In the latter case, k = 4s+3 and p−k/2 = 4s+4 = k +1.
In either case, we conclude that
k p−1 p/2 p/2
1 p 1 1 1
≡ ≡ + ≡ 0 (mod p),
n=1
p n n=1
n n=1
n n=1
p−n
which completes the proof.
Related question. Compare with Problem 1 of the 1979 International Mathematical
Olympiad [IMO79–85, p. 2]:
Let m and n be positive integers such that
m 1 1 1 1
= 1 − + − ··· − + .
n 2 3 1318 1319
Prove that m is divisible by 1979.
f (x) = f (−x), then it satisfies the functional equation for all x. So we will consider
only x ≥ 0 hereafter.
Case 1: 0 ≤ c ≤ 1/4. In this case, the zeros a, b of x2 − x + c are real and satisfy
0 ≤ a ≤ b. We will show that f (x) = f (a) for all x ≥ 0. First suppose 0 ≤ x < a.
Define x0 = x and xn+1 = x2n + c for n ≥ 0. Then we have xn < xn+1 < a for all n,
by induction: if xn < a, then on one hand xn+1 − xn = x2n − xn + c > 0, and on the
other hand xn+1 = x2n + c < a2 + c = a. We conclude that xn converges to a limit
L not exceeding a, which must satisfy L2 + c = L. Since the only real roots of this
equation are a and b, we have L = a. Now since f (xn ) = f (x) for all n and xn → a,
we have f (x) = f (a) by continuity.
If a < x < b, we argue similarly. Define xn as above; then we have a < xn+1 < xn
for all n, by induction: if xn < b, then on one hand xn+1 − xn = x2n − xn + c < 0, and
on the other hand xn+1 = x2n + c > a2 + c = a. So again f (x) = f (a) for a < x < b.
By continuity, f (b) = f (a).
√
Finally, suppose x > b. Now define x0 = x and xn+1 = xn − c for n ≥ 0. Then
we have b < xn+1 < xn for all n,√by induction: on one hand, x2n+1 + c = xn < x2n + c,
and on the other√hand xn+1 > b − c = b. Thus xn converges to a limit L not less
than b, and L = L − c, so L = b. So analogously, f (x) = f (b) = f (a).
We conclude that f (x) = f (a) is constant.
Case 2: c > 1/4. In this case, x2 + c > x for all x. Let g be any continuous function
on [0, c] with g(0) = g(c). Then g extends to a continuous functionf by setting
√ √
f (x) = g(x) for x < c, f (x) = g( x − c) for c ≤ x < c2 + c, f (x) = g( x − c − c)
for c2 + c ≤ x < (c2 + c)2 + c, and so on. Conversely, any f satisfying the functional
equation is determined by its values on [0, c] and satisfies f (0) = f (c), and so arises
in this fashion.
Stronger result. More generally, let p be a polynomial not equal to x or to c − x
for any c ∈ R. One can imitate the above solution to classify continuous functions
f : R → R such that f (x) = f (p(x)) for all x ∈ R. The classification hinges on
whether p has any fixed points.
Case 1: p(x) has a fixed point. In this case, we show that f must be constant.
We first reduce to the case where p has positive leading coefficient. If this is not the
case and p has odd degree, we work instead with p(p(x)); if p has even degree, then
g(x) = f (−x) satisfies g(x) = g(−p(−x)), so we work instead with −p(−x).
Let r be the largest fixed point of p; then p(x) − x does not change sign for x > r,
and it tends to +∞ as x → +∞, so it is positive for all x > r. In particular, p maps
[r, ∞) onto itself. For any x > r, define the sequence {xn } by setting x0 = x and
xn+1 is the smallest element of [r, ∞) such that p(xn+1 ) = xn . The sequence {xn } is
decreasing, so it converges to a limit L ≥ r, and L = lim xn = lim p(xn+1 ) = p(L).
Thus L = p(L), which can only occur if L = r. Since f (xn ) = f (x0 ) for all n and
xn → r, we have f (x0 ) = f (r). Consequently, f is constant on [r, ∞).
Suppose, in order to obtain a contradiction, that f is not constant on all of R. Let
also constant on p−1 ([T, ∞)); if p(T ) > T , this set also includes T − C for small C,
contradiction. Thus p(T ) = T .
Since p has finitely many fixed points, either p(T − C) > T − C for small C, or
p(T − C) < T − C for small C. In the former case, the sequence with x0 = T − C and
xn+1 = p(xn ) converges to T , so f (x0 ) = f (T ). In the latter case, the sequence with
x0 = T − C and xn+1 the largest element of (xn , T ) with q(xn+1 ) = xn converges to
T , so g(x0 ) = T . In either case, g is constant on a larger interval than [T, ∞), a
contradiction.
Case 2: p has no fixed point. In this case, p must have even degree, so as in Case
1, we may assume p has positive leading coefficient, which implies that p(x) > x for
all x ∈ R. There exists a0 ∈ R such that p is strictly increasing on [a0 , ∞), since any
a0 larger than all zeros of p has this property. For n ≥ 0, set an+1 = p(an ), so {an }
is an increasing sequence. It cannot have a limit, since that limit would have to be a
fixed point of p, so an → ∞ as n → ∞.
We claim f is determined by its values on [a0 , a1 ]. Indeed, these values determine
f on [a1 , a2 ], on [a2 , a3 ], and so on, and the union of these intervals is [a0 , ∞).
Furthermore, for any x ∈ R, if we set x0 = x and xn+1 = p(xn ), then the sequence
{xn } is increasing and unbounded, so some xn lies in [a0 , ∞), and f (xn ) = f (x) is
determined by the values of f on [a0 , a1 ].
Conversely, let g(x) be any continuous function on [a0 , a1 ] with g(a0 ) = g(a1 ); we
claim there exists a continuous f : R → R with f (x) = f (p(x)) whose restriction to
[a0 , a1 ] is g. For x ∈ R, again set x0 = x and xn+1 = p(xn ). If n is large enough, there
exists t ∈ [a0 , a1 ) such that xn = pk (t) for some integer k, and this t is independent
of n. Hence we may set f (x) = f (t).
It remains to show that f is continuous. We can define a continuous inverse p−1 of
p mapping [a1 , ∞) to [a0 , ∞), and f is given on [a0 , a1 ] by f (x) = g(x), on [a1 , a2 ] by
f (x) = g(p−1 (x)), on [a2 , a3 ] by f (x) = g(p−2 (x)), and so on. Thus f is continuous
on each of the intervals [an , an+1 ], and hence on their union [a0 , ∞). For x arbitrary,
we can find a neighborhood of x and an integer k such that pk maps the neighborhood
into [a0 , ∞), and writing f (t) = f (pk (t)) for t in the neighborhood, we see that f is
also continuous there.
We conclude that the continuous functions f satisfying f (x) = f (p(x)) correspond
uniquely to the continuous functions g on [a0 , a1 ] such that g(a0 ) = g(a1 ). Otherwise
put, the quotient of R by the map p is isomorphic to the interval [a0 , a1 ] with the
endpoints identified.
Remark. The ideas in this problem come from the theory of dynamical systems.
For a problem involving a related dynamical system, see 1992B3.
Solution 1. Let fn denote the number of minimal selfish subsets of {1, . . . , n}.
We have f1 = 1 and f2 = 2. For n > 2, the number of minimal selfish subsets of
{1, . . . , n} not containing n is equal to fn−1 . On the other hand, for any minimal
selfish set containing n, by removing n from the set and subtracting 1 from each
remaining element, we obtain a minimal selfish subset of {1, . . . , n − 2}. (Note that
1 could not have been an element of the set because {1} is itself selfish.) Conversely,
any minimal selfish subset of {1, . . . , n − 2} gives rise to a minimal selfish subset of
{1, . . . , n} containing n by the inverse procedure. Hence the number of minimal selfish
subsets of {1, . . . , n} containing n is fn−2 . Thus we obtain
fn = fn−1 + fn−2 ,
Solution 2. A set is minimal selfish if and only if its smallest member is equal
to its cardinality. (If a selfish set contains a member smaller than its cardinality, it
contains a subset of that cardinality which is also selfish.) Thus we can compute the
number Sn of minimal selfish subsets of {1, . . . , n} by summing, over each cardinality
k, the number of subsets of {k + 1, . . . , n} of size k − 1 (since each
of these, plus {k},
is minimal selfish, and vice versa). In other words, Sn = k n−k k−1 . We directly verify
that S1 = S2 = 1, and that
n−k n−1−k
Sn−1 + Sn = +
k−1 k−1
k
k
n−k n−k
= +
k−1 k−2
k
k
n+1−k
=
k−1
k
= Sn+1 .
1
1 1
1 2 1 1
1 3 3 1 1
1 4 6 4 1 2
3
1 5 10 10 5 1 5
8
FIGURE 30.
Fibonacci in Pascal.
224 The William Lowell Putnam Mathematical Competition
Solution 1. By estimating the area under the graph of ln x using upper and lower
rectangles of width 2 (see Figure 31), we obtain
2n−1 2n+1
ln x dx < 2(ln(3) + · · · + ln(2n − 1)) < ln x dx.
1 3
Since ln x dx = x ln x − x + C, exponentiating and taking square roots yields the
middle two inequalities in
2n−1
2n − 1 2 2n−1
< (2n − 1) 2 e−n+1
e
≤ 1 · 3 · · · (2n − 1)
−n+1
2n+1
2
2n+1 e 2n + 1
≤ (2n + 1) 2 3/2
< ,
3 e
and the inequalities at the ends follow from 1 < e < 3.
x
1 3 5 7 … 2n – 1 2n + 1
FIGURE 31.
Estimating ln x dx.
Solution 2. We use induction on n. The n = 1 case follows from 1 < e < 3. For
the inductive step, we need to prove
2n+1 2n+1
2
2n+3 2n+3
2
e
2n−1 2n−1 < 2n + 1 < e 2n+1 ,
2 2n+1 2
e e
which is equivalent to
2n−1
2
2n+3
2
2n + 1 2n + 3
<e< .
2n − 1 2n + 1
Solutions: The Fifty-Seventh Competition (1996) 225
The left side is equal to (1 + u)1/u for u = 2/(2n − 1), and the right side is equal to
(1 + u)1/u+1 for u = 2/(2n + 1), so it suffices to prove the inequalities
(1 + u)1/u < e < (1 + u)1/u+1 for u > 0.
Apply ln and rearrange to rewrite this as
u
< ln(1 + u) < u,
1+u
which follows by integrating
1 1
< <1
(1 + t)2 1+t
from t = 0 to t = u.
Related question. Use the method of Solution 1 to prove that
e(n/e)n < n! < en(n/e)n .
(This is a weak version of Stirling’s approximation. The standard form of Stirling’s
approximation is stated in the following remark.)
Remark. Better estimates for n! can be obtained using the Euler-Maclaurin
summation formula [At, Section 5.4]: For any fixed k > 0,
b
B2i " (2i−1) #
b k
f (a) + f (b)
f (j) = f (t) dt + + f (b) − f (2i−1) (a) + Rk (a, b),
j=a a 2 i=1
(2i)!
where the Bernoulli numbers B2i are given by the power series
∞
x B2i 2i
= −x/2 + x ,
ex − 1 i=1
(2i)!
(see [HW, Section 17.2]) and the error term Rk (a, b) is given by
b
−1
Rk (a, b) = B2k+2 (t − t)f (2k+2) (t) dt.
(2k + 2)! a
(See 1993B3 for another appearance of Bernoulli numbers.) Specifically, this formula
can be used to obtain Stirling’s approximation to n! [Ap2, Theorem 15.19],
√ " n #n
n! ∼ 2πn ,
e
where the tilde indicates that the ratio of the two sides tends to 1 as n → ∞. See
Solution 1 to 1995A6 for an application of Stirling’s approximation.
The Euler-Maclaurin formula has additional applications in numerical analysis, as
well as in combinatorics; see the remark following 1996B3 for an example.
Answer. The maximum is (2n3 + 3n2 − 11n + 18)/6, and the unique arrangement
(up to rotation and reflection) achieving the maximum is
. . . , n − 4, n − 2, n, n − 1, n − 3, . . . .
Solution 1. Since there are finitely many arrangements, at least one is optimal.
In an optimal arrangement, if a, b, c, d occur around the circle in that order, with a
adjacent to b, c adjacent to d and a > d, then b > c. Otherwise, reversing the segment
from b to c would increase the sum by (a − d)(c − b).
This implies first that in an optimal arrangement, n is adjacent to n − 1, or else
we could reverse the segment from n − 1 to either neighbor of n. Likewise, n must be
adjacent to n − 2, or else we could reverse the segment from n − 2 to the neighbor of
n other than n − 1.
Now n − 1 is adjacent to n but not to n − 2; we must have that n − 1 is also adjacent
to n − 3, or else we could reverse the segment from n − 3 to the neighbor of n − 1 other
than n. Likewise n − 2 must be adjacent to n − 4, and so on.
In this arrangement, the value of the function is
n(n − 1) + n(n − 2) + (n − 1)(n − 3) + · · · + 4 · 2 + 3 · 1 + 2 · 1.
n
Using the fact that k=1 k 2 = n(n + 1)(2n + 1)/6, we can rewrite the sum as
n−2 n−2
n(n − 1) + 2 + k(k + 2) = n2 − n + 2 + (k + 1)2 − 1
k=1 k=1
(n − 1)n(2n − 1)
=n −n+2+
2
− 1 − (n − 2)
6
2n3 + 3n2 − 11n + 18
= .
6
Solution 2. We prove that the given arrangement is optimal by induction on
n. Suppose that the analogous arrangement of n − 1 numbers is optimal. Given
any arrangement of n − 1 numbers, inserting n between a and b changes the sum
by na + nb − ab = n2 − (n − a)(n − b) ≤ n2 − 2. Thus the maximum sum for n
numbers is at most n2 − 2 plus the maximum sum for n − 1 numbers, and this value is
achieved by inserting n between n − 1 and n − 2 in the optimal arrangement of n − 1
numbers. Thus the result is the optimal arrangement of n numbers; since the only
possible arrangement for n = 3 has value 6 + 3 + 2 = 11, the value for n numbers is
n(n + 1)(2n + 1)
11 + (42 − 2) + · · · + (n2 − 2) = 11 + − 2(n − 3) − (12 + 22 + 32 )
6
2n3 + 3n2 − 11n + 18
= .
6
Related question. Can you determine the arrangement that minimizes the function?
Hint: the minimum value is (n3 + 3n2 + 5n − 6)/6 for n even and (n3 + 3n2 + 5n − 3)/6
for n odd.
n 2
Remark. The fact that k=1 k = n(n + 1)(2n + 1)/6, used above, can be
generalized as follows: for any polynomial P (x) of degree m, there exists a polynomial
n
Q(x) of degree m + 1 such that k=1 P (k) = Q(n) for all positive integers n. This
Solutions: The Fifty-Seventh Competition (1996) 227
follows from the Euler-Maclaurin summation formula (see the remark in 1996B2),
which can also be used to compute Q from P .
0 k=0 (2k+1)!
sin x y cos x
= .
0 sin x
x y
Thus if sin x = 1, then cos x = 0 and sin is the identity matrix. In other
0 x
words, sin A cannot equal a matrix whose eigenvalues are 1 but which is not the
identity matrix.
x y x 0
Remark. The computation of sin can be simplified by taking A =
0 x 0 x
0 y
and B = in the identity
0 0
sin(A + B) = sin A cos B + cos A sin B,
which holds when A and B commute.
228 The William Lowell Putnam Mathematical Competition
∞
Solution 2. Put cos A = n=0 (−1)n A2n /n!. The identity sin2 x + cos2 x = 1
implies the identity
4∞ 52 4 ∞ 52
(−1)n 2n+1 (−1)n 2n
x + x =1
n=0
(2n + 1)! n=0
(2n)!
string of length n + 2 ends in XO and has last doubled letter O, the remainder must
end in OO, or end in XO and have last doubled letter O. Thus zn+2 = xn + zn as
well. Putting this together,
Then g(θ) is always positive, because the origin lies in the interior of the convex hull
of the points (ai , bi ). Let c > 0 be the minimum value of g(θ) on the interval [0, 2π];
then
f (-v ) ≥ max{e(ai ,bi )·:v } ≥ ec|:v|
i
for all -v . In particular, f is greater than ecr outside of a circle of radius r. Choose
r > 0 such that ecr > f ((0, 0)). Then the infimum of f on the entire plane equals
its infimum within the disc of radius r centered at the origin. Since the closed disc is
compact, the infimum of f there is the value of f at some point, which is the desired
global minimum.
Solution 2. We retain the notation of the first solution. To prove that ∇f
vanishes somewhere, it suffices to exhibit a simple closed contour over which ∇f has
a nonzero winding number. In fact, any sufficiently large counterclockwise circle has
this property. As in the first solution, there exists c such that maxi {(ai , bi ) · -v } ≥ c|-v |,
so
n
-v · ∇f (-v ) = e(ai ,bi )·:v ((ai , bi ) · -v )
i=1
≥ c|-v |ec|:v| + (n − 1) inf xex
x
= c|-v |ec|:v| − (n − 1)/e,
Thus if -v runs over a large enough circle, we will have -v · ∇f (-v ) > 0 everywhere on
the circle, implying that the vector field ∇f (-v ) has the same winding number as -v on
the circle, namely 1. (In particular, the number of solutions -v to ∇f (-v ) = 0, counted
with multiplicity, is odd.)
Remark. The notion of winding number also occurs in complex analysis, for
instance in the proof of Rouché’s Theorem, which is stated in Solution 3 to 1989A3.
Remark. More generally, the following useful fact is true [Fu, p. 83]:
Let u1 , . . . , ur be points in Rn , not contained in any affine hyperplane, and
let K be their convex hull. Let ε1 , . . . , εr be any positive real numbers, and
define H : Rn → Rn by
r
1
H(x) = εk e(uk ,x) uk ,
f (x)
k=1
where f (x) = ε1 e + · · · + εr e
(u1 ,x)
, and (·, ·) is the usual inner product
(ur ,x)
H O
F 11 M
Solution 1 (Dave Rusin). (See Figure 32.) Introduce coordinates for which
Since B and C are both equidistant from M and O, the perpendicular bisector of BC
is the y-axis. Since BC contains F , we have B = (−x, −5) and C = (x, −5) for some
x. Also, A = (−11, y) for some y.
The altitude through B passes through H, so its slope is 5/(x − 11). It is
perpendicular to the line AC, whose slope is −(y + 5)/(x + 11), so these two slopes
have product −1. That is, 5(y + 5) = (x − 11)(x + 11).
A
◗◗
◗
◗
◗
◗
◗
◗
◗
◗
◗
◗
◗
H O ◗
◗
◗
◗
◗
◗
◗
◗
◗
B F M C
FIGURE 32.
Solutions: The Fifty-Eighth Competition (1997) 233
Remark. For more on the Euler line and related topics, see [CG, Section 1.7].
Solution 3. Introduce a coordinate system with origin at O, and for a point
- denote the vector from O to X. Then H
X, let X - = A -+B - +C - (see remark
-
below) and M - -
√ = (B + C)/2 √ = (H − A)/2; we now compute AH = 2OM = 10,
- -
OC = OA = AH 2 + OH 2 = 221, and
√ √
BC = 2M C = 2 OC 2 − OM 2 = 2 221 − 25 = 28.
out, and the second player passes two pennies and drops out. Then the third player
passes one penny and keeps two, the fourth player passes two pennies and drops out,
the fifth player passes one penny and keeps two, and so on. The net result is that
n−1
2 players remain, each of whom has two pennies except for the player to move
next, who has 3 or 4 pennies.
Trying some small examples suggests the following induction argument. Suppose
that for some k ≥ 2, the game reaches a point where:
• Except for the player to move, each player has k pennies;
• The player to move has at least k pennies, and it is his turn to pass one penny.
We will show by induction that the game terminates if and only if the number of
players remaining is a power of 2. If the number of players is odd, then two complete
rounds leaves the situation unchanged (here we need k ≥ 2), so the game terminates
only if there is one player left to begin with. If the number of players is even, then
after k complete rounds, the player who made the first move and every second player
thereafter will have gained k pennies, and the other players will all have lost their k
pennies. Thus we are in a situation of the same form with half as many players, and
by induction the latter terminates with one player if and only if the number of players
is a power of 2.
Returning to the original game, we see that if the player to move is to pass one
penny, we are in the desired situation. If the player to move is to pass two pennies,
after that move we end up in the desired situation. Thus the game terminates if and
only if n−1
2 is a power of 2, that is, if and only if n = 2 + 1 or n = 2 + 2 for some
m m
m.
√
Answer. The value of the integral is e.
2
Solution 1. The series on the left is the Taylor series of xe−x /2 . Since the terms
of the second sum are nonnegative, we may interchange the sum and integral by the
Monotone Convergence Theorem [Ru, p. 319], so the expression becomes
∞ ∞
2 x2n
xe−x /2 2n dx.
n=0 0
2 (n!)2
By integration by parts,
∞ " # ∞
∞
2 2 2
x2n xe−x /2 dx = −x2n e−x /2 + 2nx2n−1 e−x /2
dx
0 0 0
Solutions: The Fifty-Eighth Competition (1997) 235
since both integrals converge absolutely, and (for n ≥ 1) the first expression evaluates
to 0 at both endpoints. Thus by induction,
∞
2
x2n+1 e−x /2 dx = 2 × 4 × · · · × 2n.
0
Remark. One can also first make the substitution u = x2 /2, in which case the
integral becomes
∞ ∞
1
n (n!)2
un e−u du.
n=0
2 0
∞ n −u
The reader may recognize 0 u e du as the integral defining the gamma function
Γ(n + 1) = n!.
the series converges absolutely for all x ∈ C, by the Ratio Test. Applying the operator
d
x dx twice to J0 (x) yields −x2 J0 (x), so J0 (x) satisfies the differential equation
x2 y + xy + x2 y = 0. (1)
To justify certain calculations in the rest of the proof, we need some bounds on J0
2
and its derivatives. For any t ∈ C and β > 0, we have J0 (tx)/eβx → 0 as x → +∞:
this holds because for any C > 0, all but finitely many terms in the expansion of J0 (tx)
2
are bounded in absolute by C times the corresponding term in eβx ; those finitely many
2
terms also are negligible compared to eβx as x → ∞. A similar argument shows that
2 2
J0 (tx)/eβx → 0 and J0 (tx)/eβx → 0 as x → +∞, uniformly for t in any bounded
subset of C.
For t ∈ C, define
∞
2
F (t) = xe−x /2 J0 (tx) dx. (2)
0
The previous paragraph shows that the integral converges and justifies the claim that
integration by parts yields
∞
2
e−x /2 J0 (tx) dx = t−1 (F (t) − 1) (3)
0
for t = 0. The rest of this paragraph justifies the claim that differentiating (3) with
respect to t yields
∞
2
xe−x /2 J0 (tx) dx = −t−2 (F (t) − 1) + t−1 F (t). (4)
0
236 The William Lowell Putnam Mathematical Competition
2
The nontrivial statement here is that if g(x, t) is the integrand e−x /2
J0 (tx) on the
left of (3), then ∞
d ∞ ∂g
g(x, t) dx = dx.
dt 0 0 ∂t
By definition of the derivative, the left side at t = t0 equals
∞ ∞ ∞
0
g(x, t) dx − 0 g(x, t0 ) dx g(x, t) − g(x, t0 )
lim = lim dx, (5)
t→t0 t − t0 t→t0 0 t − t0
so to obtain the right side, what we need is to interchange the limit and the integral on
the right of (5). The interchange is justified by theDominated Convergence Theorem
∞
[Ru, p. 321], provided that there exists G(x) with 0 G(x) dx < ∞ such that
g(x, t) − g(x, t0 )
≤ G(x)
t − t0
for all t in a punctured neighborhood of t0 and for all x ≥ 0. For fixed x, the difference
0)
quotient g(x,t)−g(x,t
t−t0 is the average value of ∂g/∂t over the interval [t0 , t], so we need
only prove ∂g/∂t ≤ G(x). The limits in the previous paragraph show
∂g 2 2
= x2 e−x /2 J0 (tx) ≤ C(t)e−x /4 ,
∂t
where C(t) is uniformly bounded in a neighborhood of t0 . Hence we may take
2
G(x) = Ce−x /4 for some C > 0 depending on t0 to complete the justification.
By (1), (2), (3), and (4),
∞ ∞
−2 −1 −1 −x2 /2 2
−t (F (t) − 1) + t F (t) = −t e J0 (tx) dx − xe−x /2 J0 (tx) dx
0 0
= −t−2 (F (t) − 1) − F (t).
Therefore F (t) = −tF (t). Separating variables and integrating, we get F (t) =
2
Ce−t /2 . Here
∞ ∞
−x2 /2 2
C = F (0) = xe J0 (0) dx = xe−x /2 dx = 1,
0 0
2
so F (t) = e−t /2
. The integral of the problem is
∞
−x2 /2 x2 x4 √
xe 1 + 2 + 2 2 + · · · dx = F (i) = e.
0 2 2 · 4
Remark. The above solution can ∞be reinterpreted in terms of the Laplace transform,
which takes f (x) to (Lf )(s) = 0 e−sx f (x) dx. See Chapter 6 of [BD] for further
applications of this technique.
Remark. The function J0 (x) is an example of a Bessel function. See [O, Section 2.9]
for the definitions and properties of these commonly occurring functions.
Remark. The trick of differentiating an integral with respect to an auxiliary
parameter was a favorite of 1939 Putnam Fellow (and Nobel Laureate in physics)
Richard Feynman, according to [Fe, p. 72]. A systematic treatment of the method can
be found in [AZ].
Solutions: The Fifty-Eighth Competition (1997) 237
φ(g)φ(e)φ(g −1 ) = φ(e)φ(g)φ(g −1 ),
and cancelling φ(g −1 ) shows that φ(g) commutes with φ(e) for all g. The hypothesis
also implies
Since φ(e) commutes with anything in the image of φ, φ(e)−1 does too, so we deduce
Solution 1. Since we are only looking for the parity of the number of solutions, we
may discard solutions in pairs. For example, any solution with a1 = a2 may be paired
with the solution obtained from this one by interchanging a1 and a2 . The solutions
left unpaired are those with a1 = a2 , so the parity of N10 equals the parity of the
number of solutions with a1 = a2 .
Similarly, we may restrict attention to solutions with a3 = a4 , a5 = a6 , a7 = a8 ,
a9 = a10 . Such solutions must satisfy the equation
(This sum counts each multiple of p up to n once, each multiple of p2 a second time,
and so on.) Hence the exponent of p in aa1 1+···+a
,...,an
n
is
∞ . / . / . /
a 1 + · · · + an a1 an
− i − ··· − ,
i=1
pi p pi
and the summand is precisely the number of carries into the pi column when a1 , . . . , an
are added in base p.
In particular, p1 ,p102 ,... is even unless p1 = 10 or {p1 , p2 } = {2, 8}. Up to
rearrangement, there is one solution of the former shape, namely (10, . . . , 10), and
four of the latter shape. Hence N10 is odd.
Reinterpretation. The symmetric group S10 on ten symbols acts on the set of
ordered tuples. The number of elements in the orbit of a given tuple is 10!/|G|, where
|G| is the order of the stabilizer G of the tuple. This orbit size is odd if and only
if G contains a 2-Sylow subgroup. All 2-Sylow subgroups are conjugate, and one
2-Sylow subgroup contains the product of a disjoint 8-cycle and 2-cycle, so all 2-Sylow
subgroups must contain such a product. But G is a product of symmetric groups, so G
contains a 2-Sylow subgroup if and only if G contains a subgroup isomorphic to S8 ×S2 .
As seen above there are five solutions stabilized by S8 × S2 , up to rearrangement.
p(t) = xk+1 tk .
k≥0
p (t) c − (n − 1)t A B
(ln p(t)) = = = + (2)
p(t) 1 − t2 1+t 1−t
for some A and B depending on c and n. This implies that the only linear factors
of the polynomial p(t) over C are 1 − t and 1 + t. (See the discussion of logarithmic
differentiation in 1991A3.) Moreover, p(0) = 1, so
The recursion holds for k = −1 as well, if we define y−1 = 0. Let xk = yk + yk−1 for
k ≥ 0. Then for k ≥ 0,
so {xk } satisfies the recursion for n + 1 and c + 1. Taking k = n in the y recursion (3)
shows that yn+1 = 0 implies yn+2 = 0, so xn+2 = yn+2 + yn+1 = 0. Thus {xk } is a
solution sequence for n + 1 and c + 1. Hence adding 1 to each value of c for n gives a
possible value of c for n + 1, so the inductive hypothesis implies that
−(n − 2), −(n − 4), . . . , n − 4, n − 2, n
are possible values of c for n + 1. If {xk } is the sequence for c = n, then {(−1)k−1 xk }
is a solution sequence for c = −n, so
−n, −(n − 2), −(n − 4), . . . , n − 4, n − 2, n
are n + 1 possible values of c for n + 1. By the first sentence of this solution, there
cannot be any others.
k−1 , k ≥ 0, is a solution for n
Finally, the inductive hypothesis implies that yk = n−1
n−1
and c = n − 1 (we interpret −1 as 0), so
n−1 n−1 n
xk = yk + yk−1 = + = for k ≥ 1,
k−1 k−2 k−1
gives the solution for n + 1 and c = n. This completes the inductive step.
Remark. Both of the previous solutions can be used to show that the sequences
for which xn+1 = 0 are the sequences of coefficients of t(1 + t)j (1 − t)n−1−j for some
j ∈ {0, 1, . . . , n − 1}.
and ρ is any other eigenvalue, then |λk | > |ρk | by the simpler form of the theorem, so
|λ| > |ρ|.
There is also a formulation of the theorem that applies directly to matrices like
the one occurring in Solution 4, in which An may not have positive entries for any
n. Let A be a matrix with nonnegative entries. Let G be the directed graph with
vertices {1, . . . , n} and with an edge from i to j if and only if Aij > 0. Call A
irreducible if G is strongly connected (see 1990B4 for the definition). In this case, A
has a unique eigenvector with positive entries, whose eigenvalue has multiplicity one
and has absolute value greater than or equal to that of any other eigenvalue. This
can be deduced by applying the version in the previous paragraph to A + CI for each
C > 0.
In fact, the matrix in Solution 4 shows that “greater than or equal to” cannot be
replaced by “strictly greater than” in this final version: the matrix A there has 1 − n
as an eigenvalue in addition to the eigenvalue n − 1 of the positive eigenvector.
Related question. The following is an example of a problem that can be solved
by an appropriate application of the Perron-Frobenius Theorem. (We are grateful to
Mira Bernstein for passing it on to us.) It can also be solved by other means.
The Seven Dwarfs are sitting around the breakfast table; Snow White has just
poured them some milk. Before they drink, they perform a little ritual. First,
Dwarf #1 distributes all the milk in his mug equally among his brothers’ mugs
(leaving none for himself). Then Dwarf #2 does the same, then Dwarf #3,
#4, etc., finishing with Dwarf # 7. At the end of the process, the amount of
milk in each dwarf’s mug is the same as at the beginning! If the total amount
of milk is 42 ounces, how much milk did each of them originally have?
See 1995A5 for another application of the Perron-Frobenius Theorem, and see
1993B4 for an application of a continuous analogue of the theorem. For more
on matrices with nonnegative entries, including the Perron-Frobenius Theorem and
related results, see [HJ, Chapter 8].
Therefore
3n−1 "
m#
4n−1 " # 6n−1 " m#
2n−1
m m
Sn = + 1− + −1 + 2− .
m=1
6n m=2n 3n m=3n
3n m=4n
6n
Solutions: The Fifty-Eighth Competition (1997) 243
m
2n 3n 4n 6n
FIGURE 33.
m m
Graph of y = min 6n
, 3n
.
Each of the four sums is an arithmetic progression, which can be evaluated as the
number of terms times the average of the first and last terms. This yields
2n n+1 n−1 2n + 1
Sn = (2n − 1) +n +n + 2n = n.
12n 6n 6n 12n
{1, 2, 3, 4, 20, 21, 22, 23, 24, 100, 101, 102, 103, 104, 120, 121, 122, 123, 124}.
To complete the proof, we must check that Hn is not divisible by 5 for any of the ten
integers n just added to S. Suppose n = 100 + j with j = 0, . . . , 4. Applying (1) twice
gives Hn = S100+j + 15 S20 + 25
1
H4 . We know 15 S20 is divisible by 5, and H4 = 25/12,
so it suffices to show that S100+j + 1/12 is not divisible by 5. For j = 0, . . . , 4,
j
1 1 1 1
S100+j + = S100 + Hj + + − .
12 12 i=1
100 + i i
Here S100 is a sum of expressions of the form (2), hence divisible by 5, and 100+i 1
− 1i =
−100
i(100+i) is divisible by 5, but one can check (for j = 0, . . . , 4 individually) that Hj +1/12
is not divisible by 5. Thus S100+j is not divisible by 5, and neither is H100+j . By a
similar argument, if n = 120 + j with j = 0, . . . , 4, then Hn is not divisible by 5.
Thus the algorithm terminates, and the list of integers n such that Hn is 5-integral
is as given in the answer above.
Reinterpretation. Arguments of this sort are often more easily expressed in terms of
the p-adic valuation on the rational numbers, for p a prime. Given r ∈ Q nonzero, let
vp (r) be the largest integer m (positive, negative or zero) such that p−m r is p-integral.
Then the problem is to determine when v5 (Hn ) ≥ 0, and the first step is to note that
this is equivalent to v5 (H n/5 ) ≥ 1. The rest of the solution amounts to computing
some low order terms in the base 5 expansions of 1/m for some small m.
Remark. The fact that (2) is divisible by 25 for j = 4 is a special case of the fact
that for a prime p > 3 and an integer x,
1 1 1
+ + ··· + ≡0 (mod p2 ).
px + 1 px + 2 px + (p − 1)
The case x = 0 is known as Wolstenholme’s Theorem, which arises in a different
context in 1991B4. To prove the general case, first combine opposite terms in the sum
to rewrite it as
(p−1)/2
1
(2px + p) .
i=1
(px + i)(px + (p − i))
0≤ (−1)i ak−i,i ≤ 1.
i=0
i
Solution 1. Let sk = i (−1) ak−i,i be the given sum. (Note that ak−i,i is
nonzero precisely for i = 0, . . . , 3 .) Since
2k
we have
= xj (1 − x + x2 )j (since aj,i z i = (1 + z + z 2 )j )
j i
1
= (geometric series)
1 − x + x2 − x3
1+x
=
1 − x4
= (1 + x) + (x4 + x5 ) + (x8 + x9 ) + · · · ,
so 0 ≤ sk ≤ 1 for all k ≥ 0.
Remark. If one does not notice that
1 1+x
= ,
1 − x + x2 − x3 1 − x4
one can instead use partial fractions to recover its coefficients.
Solutions: The Fifty-Eighth Competition (1997) 247
is eventually constant.
See 1985A4 for a similar problem and for the properties of φ(n).
Remark. For n ≥ 1, let f (n) be the smallest integer k ≥ 0 such that xk ≡ xk+1 ≡
xk+2 ≡ · · · (mod n). The above solution shows that f (n) ≤ n − 1, but the actual
value of f (n) is much smaller.
We now prove f (n) ≤ log2 n by strong induction on n. The base case n = 1
is trivial. If n = 2a for some a ≥ 1, then 2a divides xa , xa+1 , . . . (since xa−1 ≥ a
was proved in the solution above), so f (n) ≤ a. If n = 2a b for some a ≥ 1 and odd
b > 1, then f (n) ≤ max{f (2a ), f (b)}, so we apply the inductive hypothesis at 2a and
b. Finally, if n > 1 is odd, write φ(n) = 2c d with d odd, and observe that
since c ≤ log2 φ(n) < log2 n and d ≤ φ(n)/2 < n/2. This completes the inductive
step.
When n is a power of 3, the bound just proved is best possible up to a constant
factor: we now show that f (3m ) = m + 1 for m ≥ 1 by induction on m. First,
xk+1 ≡ (−1)xk = 1 (mod 3), if and only if k ≥ 1, so f (3) = 2. Now suppose
m > 1. Since the image of 2 generates the cyclic group (Z/3m Z)∗ (i.e., 2 is a primitive
root of 3m [NZM, Theorem 2.40]), we have xk ≡ xk+1 ≡ · · · (mod 3m ) if and only
248 The William Lowell Putnam Mathematical Competition
if xk−1 ≡ xk ≡ · · · (mod 2 · 3m−1 ), but all the xk except x0 are even, so this is
equivalent to xk−1 ≡ xk ≡ · · · (mod 3m−1 ) if k ≥ 2. Hence f (3m ) = f (3m−1 ) + 1, so
f (3m ) = m + 1 by induction.
It is not true in general that f (n) is bounded below by a constant multiple of ln n,
because there are some values of n, such as large powers of 2, for which f (n) is much,
much less than ln n. We can at least say that f (n) → ∞ as n → ∞, though: we have
xf (n)+1 ≥ xf (n)+1 − xf (n) ≥ n, since n divides xf (n)+1 − xf (n) .
❙
❙
❙
❙ 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.)
Answer. The minimum diameter is 25/13.
Solution. (See Figure 34.) Place the triangle on the cartesian plane so that its
vertices are A = (4, 0), B = (0, 0), C = (0, 3). The five points A, B, C, D = (27/13, 0),
E = (20/13, 24/13) lie at distance at least 25/13 apart from each other (note that
AD = DE = EC = 25/13). By the Pigeonhole Principle, any dissection of the
triangle into four parts has a part containing at least two of these points, and hence
has diameter at least 25/13.
C
E
✑
✑
✑ H
G ✭✭✭✑I
L ✂
L ✂
L ✂
L ✂
L ✂
B F D A
FIGURE 34.
Solutions: The Fifty-Eighth Competition (1997) 249
On the other hand, we now construct a dissection into four parts in which each part
has diameter 25/13. Let H = (32/13, 15/13), so that AH = 25/13. Next, construct a
point I inside quadrilateral BDEC so that BI, CI, DI, EI, HI have length less than
25/13. For example, we may take I = (7/13, 15/13) such that DECI and ADIH are
parallelograms. Take F = (1, 0) on AB so that EF = 25/13, and take G = (0, 14/13)
on BC so that CG = 25/13.
Our parts are the triangle ADH, the pentagon DHEIF , the quadrilateral CEIG,
and the quadrilateral BF IG. Verifying that each has diameter 25/13 entails checking
that the distance between any two vertices of a polygon is at most 25/13. For starters,
AD = AH = CE = CG = CI = DE = DI = EF = HI = 25/13.
Next, we see without any calculations that
BF, BG < F G F I, F D < DI DH < F H GI < CI.
Finally, we compute the remaining distances:
274 500 225
BI 2 = , EG2 = , EH 2 = ,
169 169 169
260 365 586
EI 2 = , F G2 = , F H2 = .
169 169 169
Remark. Once the “skeleton” is in place, some variations in the placements of the
points are possible.
250 The William Lowell Putnam Mathematical Competition
A
❙
❙
❙
❙
F ❙
D ❙E
❙
❙
❙
❙
❙
B G C
FIGURE 35.
Let s be the side length√of the cube. Segment DE is a diagonal of the top of
the cube, so its length is s √ 2. From the similar triangles ADE √ ∼ ABC, we have
DE
BC = AF
AG , or equivalently s 2
2 = 3−s
3 . Solving for s, we get s = (9 2 − 6)/7.
F K
G
E H
O C D
FIGURE 36.
Solution. If at least one of f (a), f (a), f (a), or f (a) vanishes at some point a,
then we are done. Otherwise by the Intermediate Value Theorem, each of f (x), f (x),
f (x), and f (x) is either strictly positive or strictly negative on the real line, and we
only need to show that their product is positive for a single value of x. By replacing
f (x) by −f (x) if necessary, we may assume f (x) > 0; by replacing f (x) by f (−x) if
necessary, we may assume f (x) > 0. Notice that these substitutions do not change
the sign of f (x)f (x)f (x)f (x).
Now f (x) > 0 implies that f (x) is increasing. Thus for a > 0,
a
f (a) = f (0) + f (t) dt ≥ f (0) + af (0).
0
In particular, f (a) > 0 for large a. Similarly, since f (x) > 0, f (a) is positive for
large a. Therefore f (x)f (x)f (x)f (x) > 0 for sufficiently large x.
Reinterpretation. More succinctly, f cannot both be positive and strictly concave-
down everywhere, nor negative and strictly concave-up everywhere. So f (x)f (x)
must be positive for some range of x, as must be f (x)f (x) by the same reasoning
applied to f instead of f .
252 The William Lowell Putnam Mathematical Competition
By induction, we deduce that An+6 ≡ An (mod 11) for all n, and so An is divisible
by 11 if and only if n ≡ 1 (mod 6).
Remark. See 1988A5 for more on linear recursions and Fibonacci numbers.
Here, if D is the disc of radius r and center P , then 3D is the disc of radius
3r and center P .
Thus P ∈ 3Di .
Solutions: The Fifty-Ninth Competition (1998) 253
This lower bound can be achieved: set B (resp., C) to be the intersection between the
segment√DE and the x-axis (resp., the line x = y). Thus the minimum perimeter is
in fact 2a2 + 2b2 .
Remark. The reflection trick comes up in various geometric problems where the
sum of certain distances is to be minimized. For many applications of this principle,
see [CG, Sections 4.4–4.6] and [Pó, Section IX].
A
C
FIGURE 37.
The reflection trick: AB + BC + CA = DB + BC + CD ≥ DE.
Solutions: The Fifty-Ninth Competition (1998) 255
Remark. Our proof did not use the assumption that a triangle of minimum
perimeter exists. This assumption might be slightly useful in a “brute force” approach
using calculus to find the minimum of a two-variable function. Such an approach is
painful to execute, however.
{ (x, y, z) : x2 + y 2 + z 2 = 1, z ≥ z0 }
The desired surface area is the area of a hemisphere minus the surface areas of five
identical halves of spherical caps; these caps, up to isometry, correspond to z0 being
the distance from the center of the pentagon to any of its sides, i.e., z0 = cos π5 . Since
the area of a hemisphere is 2π (take z0 = 0 above), the desired area is
5" " π ## π
2π − 2π 1 − cos = 5π cos − 3π.
2 5 5
Remark. The surface area of a spherical cap can also be computed by noting that
the cap is the surface of revolution
√obtained by rotating part of the graph of y = f (x)
around the x-axis, where f (x) = 1 − x2 . This gives
1 1
2
2πy dx + dy = 2 2πf (x) 1 + f (x)2 dx
x=z0 z0
2
1 x2
= 2π 1 − x2 1+ dx
z0 1 − x2
2
1 1
= 2π 1− x2 dx
z0 1 − x2
= 2π(1 − z0 ).
Notice an amazing consequence of the formula: the area of a slice of a unit sphere
depends only on the width of the slice, and not on its position on the sphere! This
was known already to Archimedes, and forms the basis of the Lambert equal-area
cylindrical projection and the Gall-Peters equal-area projection used in some maps.
256 The William Lowell Putnam Mathematical Competition
This fact can be used to give a beautiful solution to the following problem [She]:
Consider a disk of diameter d drawn on a plane and a number of very long
white paper strips of different widths. Show that the disk can be covered by
the strips if and only if the sum of the widths is at least d.
m n
Answer. We have S(m, n) = 0 if and only if gcd(m,n) and gcd(m,n) are not both odd.
Solution. For convenience, define fm,n (i) = + mi ni ,
so that the given sum is
mn−1 fm,n (i)
S(m, n) = i=0 (−1) . If m and n are both odd, then S(m, n) is the sum of
an odd number of ±1’s, and thus cannot be zero. If m and n are of opposite parity,
. / . / . / . /
i i mn − 1 − i mn − 1 − i
fm,n (i) + fm,n (mn − 1 − i) = + + +
m n m n
= (n − 1) + (m − 1),
since ac + b − c+1
a = b − 1 for all integers a, b, c with a > 0. Thus the terms of
S(m, n) cancel in pairs and so the sum is zero.
Now suppose that m = dk and n = dl for some d. For i = 0, . . . , d − 1, we have
dj+i
dk = k and dl = l , so fm,n (dj + i) = fk,l (j). Hence
j dj+i j
dkl−1
S(dk, dl) = d (−1)fk,l (j)
j=0
kl−1
=d (−1)fk,l (j) + (−1)fk,l (j+kl) + · · · + (−1)fk,l (j+(d−1)kl)
j=0
kl−1 d−1
=d (−1)fk,l (j) (−1)i(k+l)
j=0 i=0
Thus we have S(dk, dl) = d2 S(k, l) if k + l is even; this equality also holds if k + l
is odd, since then S(k, l) = 0. Thus S(dk, dl) vanishes if and only if S(k, l) vanishes.
Piecing together the various cases gives the desired result.
Remark. There are many equivalent ways to state the answer. Here are some other
possibilities, mostly from student papers:
• The highest powers of 2 dividing m and n are different.
• There exist integers a, b, k ≥ 0 such that m = 2k a, n = 2k b, and a and b have
opposite parity.
Solutions: The Fifty-Ninth Competition (1998) 257
• lcm(m, n) is an even integer times m, or an even integer times n, but not both.
• Exactly one of m
gcd(m,n) and n
gcd(m,n) is even.
• m+n
gcd(m,n) is odd.
• mn
gcd(m,n)2 is even.
lcm(m,n)
• gcd(m,n) is even.
• When expressed in lowest terms, m/n has even numerator or even denominator.
• The 2-adic valuation of m/n is nonzero. (See the remark following 1997B3 for a
definition of the p-adic valuation for any prime p.)
Remark. If S(m, n) is nonzero, it equals gcd(m, n)2 . To show this, we use the
equation S(dk, dl) = S(k, l) from the above solution to reduce to the case where m, n
are coprime and odd. In this case,
fm,n (i) ≡ mi/m + ni/n ≡ i − mi/m + i − ni/n (mod 2).
Now i − mi/m is the remainder upon dividing i by m. By the Chinese Remainder
Theorem, the pairs (i − mi/m, i − ni/n) run through all pairs (j, k) of integers
with 0 ≤ j ≤ m − 1, 0 ≤ k ≤ n − 1 exactly once. Hence
m−1 n−1
S(m, n) = (−1)j (−1)k = 1.
j=0 k=0
Now
(101999 − 7)2 < 103998 − 102000 < (101999 − 4)2 ,
so
101999 − 7 √ 101999 − 4
< 101000 N < .
3 3
Hence
√
33 . . . 31 < 101000 N < 33 . . . 32,
If 4b−a2 > 0, or 4b−a2 = 0 and c > 0, then for m sufficiently large, (4b−a2 )m2 +c > 0,
and
|(4b − a2 )m2 + c| < 2(8m3 + am) − 1,
so n3 + an2 + bn + c lies between (8m3 + am)2 and (8m3 + am + 1)2 and is hence not a
perfect square. Similarly, if 4b−a2 < 0, or 4b−a2 = 0 and c < 0, then n3 +an2 +bn+c
lies between (8m3 + am − 1)2 and (8m3 + am)2 for sufficiently large m.
Solution 3. We will use the theory of height functions on elliptic curves (see
Chapter 8 of [Sil] for this theory). Suppose first that P (n) = n3 + an2 + bn + c is not
squarefree as a polynomial in Q[n]. Then by Gauss’s Lemma (see the remark below),
P (n) factors as (n − d)2 (n − e) for some d, e ∈ Z. Choose a positive integer n = d
such that n − e is not a square. Then P (n) is not a square.
Now suppose instead that P (n) is squarefree. Then y 2 = P (x) is an elliptic curve
E over Q. Let N (B) be the number of rational numbers x = u/v in lowest terms with
|u|, |v| ≤ B such that P (x) is the square of a rational number. The theory of height
functions implies that N (B) = O((ln B)r/2 ) as B → ∞, where r is the rank of E(Q).
In particular, if B is a sufficiently large integer, then N (B) < B, so not all integers 1,
2, . . . , B can be x-values making P (x) a square.
Solutions: The Fifty-Ninth Competition (1998) 259
observed by Newton; hence the term Newton-Puiseux series is also sometimes used.
The statements in this paragraph are false when k is an algebraically closed field of
characteristic p > 0, but see [Ke] for an analogue.
n+1
(x − a1 ) · · · (x − ai ) · · · (x − an+1 )
f (x) = bi ,
i=1 (ai − a1 ) · · · (ai − ai ) · · · (ai − an+1 )
where 9· indicates that the corresponding term is omitted from the product. (It is easy
to check that this f (x) is a polynomial of degree less than or equal to n such that
f (ai ) = bi for all i.) As an immediate consequence, if ai , bi ∈ Q, then f (x) has rational
coefficients.
One application of Lagrange interpolation is the lemma below, used in Proof 1
above. For further applications, see [Lar1, Section 4.3].
Lemma. If n0 ∈ Z, and g(n) is a function defined on integers n ≥ n0 such that
(∆k g)(n) = 0 for all n ≥ n0 , then there is a polynomial G(x) of degree at most k − 1
such that g(n) = G(n) for all n ≥ n0 .
Proof of Lemma. First, if h(x) is a polynomial of degree m ≥ 1, then (∆h)(x) is a
polynomial of degree m − 1. It follows that (∆k h)(n) = 0 for all k > m.
Use Lagrange interpolation to find the polynomial G(x) of degree at most k − 1
such that G(n) = g(n) for n = n0 , n0 + 1, . . . , n0 + k − 1. Let H(n) = G(n) − g(n) for
integers n ≥ n0 . Then (∆k G)(n) = 0 by the previous paragraph, and (∆k g)(n) = 0
for integers n ≥ n0 is given, so (∆k H)(n) = 0 for integers n ≥ n0 .
It remains to prove that if H is a function such that (∆k H)(n) = 0 for integers
n ≥ n0 and H(n0 ) = H(n0 + 1) = · · · = H(n0 + k − 1) = 0, then H(n) = 0 for all
n ≥ n0 . We use induction on k. The case k = 0 is trivial, since ∆0 H is just H. For
k ≥ 1, applying the inductive hypothesis to ∆H, which satisfies the assumptions with
k − 1 instead of k, shows that (∆H)(n) = 0 for integers n ≥ n0 . But H(n0 ) = 0 too,
so induction on n proves H(n) = 0 for all integers n ≥ n0 .
Proof 2. We may reduce to the case that P has no repeated factors by dividing by
squares of factors, so that the discriminant D of P is nonzero. We construct a prime
p not dividing D and an integer n such that p divides P (n). Pick an integer m such
that P (m) = 0, and for each prime pi dividing D, let ei be the exponent to which
3 ei +1
pi divides P (m). As n varies over integers congruent to m modulo pi , P (n)
assumes arbitrarily large values (since P is nonconstant), and none of these values is
divisible by piei +1 , since P (m) is not. Thus there exist arbitrarily large integers n for
which P (n) is divisible by a prime p not dividing D.
Solutions: The Fifty-Ninth Competition (1998) 261
Remark. The end of the argument is related to Hensel’s Lemma; a similar idea
arises in 1986B3.
Proof 3. We show that for any sufficiently large prime p, there exist arbitrarily
large integers n such that P (n) is not a square modulo p. Again we reduce to the case
where P is squarefree and nonconstant, say of degree d. Then the discriminant ∆ of
P is a nonzero integer; let p be any odd prime not dividing ∆. Suppose that P (n)
is a square modulo p for all sufficiently large n. Then for each x in the field Fp of p
elements, the equation y 2 = P (x) has two solutions y, unless x is a zero of P modulo
p in which case there is only one solution y. The number of zeros of P modulo p is
at most d, so y 2 = P (x) has at least 2p − d solutions (x, y) ∈ Fp × Fp . On the other
hand, the Weil Conjectures (see the end of 1991B5) for the curve y 2 = P (x) imply
√
that the number of solutions is at most p + c p, where the constant c depends only
on d. This yields a contradiction for sufficiently large p.
Remark. A fourth proof of the stronger result can be given using the Thue-Siegel
Theorem [HiS, Theorem D.8.3], which asserts that if P is a polynomial of degree at
least 3 with no repeated factors, then P (n) is a perfect square for only finitely many
integers n. For an effective bound on the size of such n, see Section 4.3 of [Bak2].
(The Thue-Siegel Theorem can fail if P has degree 2. For example, 2n2 + 1 is a square
for infinitely many integers n. See Solution 2 to 2000A2.)
Related question. A similar problem is 1971A6 [PutnamII, p. 15]:
Let c be a real number such that nc is an integer for every positive integer n.
Show that c is a nonnegative integer.
262 The William Lowell Putnam Mathematical Competition
Answer. Take
3x + 3 5x 1
f (x) = , g(x) = , and h(x) = −x + .
2 2 2
Solution. Let
−1
if x < −1
F (x) = 3x + 2 if −1 ≤ x ≤ 0
−2x + 2 if x > 0.
Remark. Alternatively, based on Figure 38, one may guess that f, g, h are linear,
and that f changes sign at −1 and g changes sign at 0. We may assume that f and g
have positive leading coefficients. Then one has the linear equations
−1 = −f (x) + g(x) + h(x)
3x + 2 = f (x) + g(x) + h(x)
−2x + 2 = f (x) − g(x) + h(x)
from which one solves for f, g, h as given above.
In fact, both guesses can be justified, and we can prove that the solution is unique
up to the signs of f and g. Of the four polynomials ±f ± g + h, three must be equal
to −1, 3x + 2, −2x + 2 in some order. But of any three of these functions, two sum
to 2h, and the difference between some two is 2f or 2g. Thus f, g, h are each linear.
As for the sign changes, assume that the graphs of f and g have positive slope. The
Solutions: The Sixtieth Competition (1999) 263
y = 3x + 2
y = –2x + 2
y = –1
FIGURE 38.
Graph of F (x) (in bold)
slope of the graph of |f (x)| − |g(x)| + h(x) jumps up at the zero of f and jumps down
at the zero of g, so these points must be x = −1 and x = 0, respectively.
Here is another proof that k = 2 suffices. Factor p(x) = q(x)r(x), where q has
all real zeros and r has all nonreal zeros and r is monic. Each zero of q has even
multiplicity, since otherwise p would have a sign change at that zero. Also q has
positive leading coefficient, since p must. Thus q(x) has a square root s(x) with real
3k
coefficients. Now write r(x) = j=1 (x − aj )(x − aj ) (possible because r has zeros in
3k
complex conjugate pairs). Write j=1 (x − aj ) = t(x) + iu(x) with t and u having real
coefficients. Then for x real,
p(x) = q(x)r(x)
= s(x)2 (t(x) + iu(x)) (t(x) + iu(x))
= (s(x)t(x))2 + (s(x)u(x))2 .
Literature note. This problem appeared as [Lar1, Problem 4.2.21], and is credited
there to [MathS].
Remark. A polynomial in more than one variable with real coefficients taking
nonnegative values need not be a sum of squares. (The reader may check that
1 − x2 y 2 (1 − x2 − y 2 ) is a counterexample.) Hilbert’s Seventeenth Problem asked
whether such a polynomial can always be written as the sum of squares of rational
functions; this was answered affirmatively by E. Artin and O. Schreier. See [J,
Section 11.4] for a proof and for generalizations.
for some constants H, I. But a2n+2 has the same form, so a2n + a2n+1 and a2n+2 satisfy
the same second-order linear recursion. (See the remarks in 1988A5 for more on linear
recursions.) Hence we can prove a2n + a2n+1 = a2n+2 for all n ≥ 0 by checking it for
n = 0 and n = 1, which is easy.
Remark. From the recursion an+1 = 2an + an−1 , one can also find the recursion
satisfied by a2n+2 , then directly prove that a2n + a2n+1 satisfies the same recursion.
0 1
Solution 3 (Richard Stanley). Let A be the matrix . By induction,
1 2
the recursion an+1 = 2an + an−1 implies
an an+1
An+2 = .
an+1 an+2
The desired result follows from equating the top left entries in the matrix equality
An+2 An+2 = A2n+4 .
Related question. This sequence, translated by one, also appeared in the following
proposal by Bulgaria for the 1988 International Mathematical Olympiad [IMO88,
p. 62].
An integer sequence is defined by an = 2an−1 + an−2 (n > 1), a0 = 0, a1 = 1.
Prove that 2k divides an if and only if 2k divides n.
then
∞ ∞
n n+1
3A = = , (2)
n=1
3n−1 n=0
3n
Solution 1. Let P denote the set of polynomials of degree at most 1999. Identify
1999
P with R2000 by identifying i=0 ai xi with (a0 , a1 , . . . , a1999 ). Let S be the set of
1999
polynomials i=0 ai xi such that max{|ai |} = 1. Then S is a closed and bounded
subset of P ≈ R2000 , so S is compact. The function P × R → R mapping (p, x) to
|p(x)| is the absolute value of a polynomial in all 2001 coordinates,
1 so it is continuous.
Therefore the function g : P → R defined by g(p) = −1 |p(x)| dx is continuous, as
is its restriction to S. Similarly the function f : S → R defined by f (p) = |p(0)| is
continuous. Since g(p) = 0 for p ∈ S, the quotient f /g : S → R is continuous. By
the Extreme Value Theorem, there exists a constant C such that f (p)/g(p) ≤ C for
all p ∈ S. An arbitrary p ∈ P can be written as cq for some c ∈ R and q ∈ S; then
f (p) = |c|f (q) ≤ |c|Cg(q) = Cg(p), as desired.
Remark. The same method proves the standard result that any two norms on a
finite-dimensional vector space are equivalent [Hof, p. 249]. In fact, another way to
solve the problem would be to apply this result to the two norms
1
sup |p(x)| and |p(x)| dx
x∈[−1,1] −1
on P .
Solutions: The Sixtieth Competition (1999) 267
with C = 1/(δC1999 ). Taking C = 1/4000 yields the explicit value C = 21999 20002001 .
Related question. Can you improve the constant in Solution 2? (We do not know
what the smallest possible C is.)
These suffice because of Lagrange’s Theorem, which states that the order of an element
of a finite group G divides the order of G.
Let us prove (a). Matrices in GLn−1 (F2 ) can be constructed one row at a time: the
first row may be any nonzero vector, and then each successive row may be any vector
not in the span of the previous rows, which by construction are independent. Hence
the number of possibilities for the jth row, given the previous ones, is 2n−1 − 2j−1 .
Thus
+
n−1 +
n−1
#GLn−1 (F2 ) = (2n−1 − 2j−1 ) = 2(n−1)(n−2)/2 (2n−j − 1).
j=1 j=1
of V is
0 0 0 ··· 0 1
1 0 0 ··· 0 1
0 1 0 ··· 0 1
. .. ..
. .. .. . . ∈ GLn−1 (F2 ).
. . . . . .
0 0 0 ··· 0 1
0 0 0 ··· 1 1
This also equals the companion matrix of the polynomial
Solution. (See Figure 39.) The triangles BEF and BCA are similar. Since
AC = 1, we have EF = BE/BC. Also, since 4ACD is isosceles, ∠ACD =
∠ADC = π/2 − θ/2. We then compute ∠BCD = π/2 − ∠DCA = θ/2 and
∠BDE = π − ∠CDE − ∠CDA = π/2 − θ/2.
† The figure is omitted here, since it is contained in Figure 39 used in the solution.
Solutions: The Sixtieth Competition (1999) 269
q/2
E
q
q p/2 – q
A F D B
3q/2
E¢
FIGURE 39.
Solution. Suppose that P does not have n distinct zeros; then it has a zero
of multiplicity k ≥ 2, which we may assume without loss of generality is x = 0.
Differentiating P term by term shows that the highest power of x dividing P (x) is
xk−2 . But P (x) = Q(x)P (x), so x2 divides Q(x). Since Q is quadratic, Q(x) = Cx2
for some constant C. Comparing the leading coefficients of P (x) and Q(x)P (x) yields
1
C = n(n−1) .
n
Write P (x) = j=0 aj xj ; equating coefficients in P (x) = Cx2 P (x) implies that
aj = Cj(j − 1)aj for all j. Hence aj = 0 for j ≤ n − 1, and P (x) = an xn , which has
all identical zeros.
Remark. If Q has distinct zeros, then after replacing x by ax+b for suitable a, b ∈ C
we may assume that Q = c(1 − x2 ) for some c ∈ C. Then P (x) is a scalar multiple
of Rn−2 (x), where Rn (x) is the unique monic polynomial of degree n satisfying the
differential equation
d2
[(1 − x2 )Rn (x)] = −(n + 1)(n + 2)Rn (x).
dx2
for m = n. That is, the Rm (x) form a family of orthogonal polynomials with respect
to the measure (1 − x2 ) dx. (In other terminology, the Rm are eigenvectors of the
d2
operator f !→ dx 2 [(1 − x )f ]. This operator is self-adjoint with respect to the measure
2
(1 − x2 ) dx, so the eigenvectors are orthogonal with respect to that measure, because
eigenspaces corresponding to different eigenvalues are orthogonal.)
The solution above implies that Rn has distinct zeros. A result from the theory
of orthogonal polynomials implies that the zeros of Rn are real numbers in [−1, 1].
This can also be deduced by applying Lucas’ Theorem (1991A3) twice. Namely, if the
convex hull of the zeros of the polynomial P (x) = (1 − x2 )Rn (x) has a vertex z other
than ±1, then Lucas’ Theorem implies that z lies outside of the convex hull of the
zeros of P (because z is not a multiple zero of P ) and then implies that z lies outside
of the convex hull of the zeros of P (x) = Rn (x), a contradiction.
Noam Elkies points out that according to [GR], Rn (x) is a scalar multiple of the
nth Gegenbauer polynomial with parameter λ = 3/2, also called the nth ultraspherical
polynomial. Also, if we put Pn (x) = (1 − x2 )Rn (x), then Pn (x) is (a scalar multiple)
of the (n + 1)st Legendre polynomial.
Related question. Problem 6 from the final round of the 1978 Swedish Mathematical
Olympiad [SMO] is related:
Solutions: The Sixtieth Competition (1999) 271
The polynomials
P (x) = cxn + an−1 xn−1 + · · · + a1 x + a0
Q(x) = cxm + bm−1 xm−1 + · · · + b1 x + b0
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
✁ ❜ ❜
✁ ✟ ✟
✁ ✟✟ ✁ ✁
✁✟
❜✟ ✁ ❜ ❜
✁ ✁ ✟✟✟✁
✁ ✁ ✟ ✁
✁ ❜ ✟❜✟ ✁✟ ✁ ❜
✁ ✟✟ ✁ ✁ ✟
✁ ✟✟ ✁ ✁ ✟✟
✁❜✟ ✁ ❜ ✟ ❜✁ ✟
✁ ✟ ✟
✁ ✁ ✟
✁ ❜ ❜✁ ✟
✟
✁ ✟✟
✁✟✟
✁❜✟
FIGURE 40.
Points of the form a(1, 2) + b(1, 2), where a and b are nonnegative integers; two translates of
this semigroup are also indicated.
an integral linear combination of (1, 2) and (2, 1). (See Figure 40 for those points of
the form a(1, 2) + b(1, 2) where a and b are nonnegative integers.) In particular,
∞ ∞
S(x, y) + 1 = (1 + xy + x2 y 2 ) xa y 2a x2b y b
a=0 b=0
1 + xy + x2 y 2
=
(1 − xy 2 )(1 − x2 y)
and the desired limit is 3.
Stronger result. Let p/q and r/s be positive rational numbers with p/q < r/s, and
define T (x, y) = (m,n) xm y n , the sum taken over all pairs (m, n) of positive integers
with p/q ≤ m/n ≤ r/s. Then
the discriminant of the quadratic must be negative: f (0)2 − 2f (0)f (0) < 0.
Combining the conclusions of the last two paragraphs, we obtain
Solution 2. We prove that f (x) < (9/2)1/3 f (x) < 1.651f (x). Since f (x) is
bounded below (by 0) and increasing, it has an infimum m, and limx→−∞ f (x) = m.
Then f (x) tends to 0 as x → −∞ since it is positive and its integral from −∞ to 0
converges. Similarly f (x) and f (x) tend to 0 as x → −∞.
By Taylor’s Formula with remainder (or integration by parts), for any function g,
s
g(x) − g(x − s) = g (x − t) dt,
0
s
g(x) − g(x − s) = sg (x − s) + tg (x − t) dt, (2)
0
s
1 1 2
g(x) − g(x − s) = sg (x − s) + s2 g (x − s) + t g (x − t) dt, (3)
2 0 2
as long as the specified derivatives exist and are continuous. For g = f , as s → +∞
for fixed x, the left side of (2) is bounded above, the term sf (x − s) is nonnegative
and the integrand tf (x − t) is everywhere nonnegative; consequently, the integrand
tends to 0 as t → ∞. Thus in (2) with g = f , letting s tend to ∞ yields
∞
f (x) = tf (x − t) dt.
0
We cannot a priori take limits in any of the equations with g = f , but from (3) we
have
s
1 2 1
f (x) − t f (x − t) dt = f (x − s) + sf (x − s) + s2 f (x − s) ≥ 0
0 2 2
for all s, so
∞
1 2
f (x) ≥ t f (x − t) dt.
0 2
Thus for c ≥ 0, we have
∞
1 2
cf (x) − f (x) ≥ ct − t f (x − t) dt.
0 2
274 The William Lowell Putnam Mathematical Competition
Solution 3. We prove that f (x) < 21/6 f (x) < 1.123f (x). As in the
previous solution, f (x) → 0 as x → −∞ for i = 1, 2, 3. For similar reasons,
(i)
because the first term plus the third term is nonnegative and the second term is
positive. Consequently,
x
y = e – cg(x)
x
y=e
FIGURE 41.
The graph of y = h3 (x).
276 The William Lowell Putnam Mathematical Competition
h3 (x) ≥ H3 (x) everywhere (for δ sufficiently small), we also have f (i) (x) = hi (x) ≥
Hi (x) > 0 for i = 2, 1, 0. For x > δ, we have f (x) ≥ H0 (x) ≥ H3 (x) = f (x); for
0 < x < δ, we have f (x) ≥ f (0) = 1 ≥ h3 (x) = f (x), provided that δ is small enough
that H3 (δ) < 1. Thus we have f (x) ≤ f (x) for all x.
and
n
2
0= e2πij n
j=1
n
= cos2 jθ − sin2 jθ + 2i cos jθ sin jθ
j=1
= C · C − D · D + 2iC · D.
Therefore, C · C = D · D = n/2 and C · D = 0. We now compute
AC = CC T − DDT C = C(C · C) − D(D · C) = (n/2)C
AD = CC T − DDT D = C(C · D) − D(D · D) = −(n/2)D
and conclude that the two remaining eigenvalues of A are n/2 and −n/2.
To make this equal a given number B ∈ (0, A2 ), take r = (A2 − B)/(A2 + B).
2
Solution 2. As in Solution 1, we prove 0 < x < A2 , and it remains to show
2
2i
that each number in (0, A ) is a possible value of xi . There exists a series of positive
numbers xi with sum A. Then x0 /2, x0 /2, x1 /2, x1 /2, x2 /2, . . . also sums to A
but its squares sum to half the previous sum of squares. Iterating shows that the sum
of squares can be arbitrarily small.
Given any series xi of positive terms with sum A, form a weighted average of it
with the series A + 0 + 0 + · · · ; in other words, choose t ∈ (0, 1) and define a new series
of positive terms yi by setting y0 = tx0 + (1 − t)A and yi = txi for i ≥ 1. Then
yi = A, and
yi2 = t2 x2i + 2t(1 − t)x0 A + (1 − t)2 A2 .
As t runs from 0 to 1, the Intermediate Value Theorem shows that this quadratic
2 2
polynomial in t takes on all values strictly between xi and A2 . Since xi can be
2
2
made arbitarily small, any number in (0, A ) can occur as yi .
x4 − 1 = (x2 − 1)(x2 + 1)
and the identity
(a2 + b2 )(c2 + d2 ) = (ac − bd)2 + (ad + bc)2 (1)
(obtained by computing the norm of (a + bi)(c + di) in two ways). Hence by induction
n
on n, if x2 − 1 is the sum of two squares (for instance, if x = 3) then so is (x2 )2 − 1
for all nonnegative integers n.
Related question. Let S = { a2 + b2 : a, b ∈ Z }. Show that S does not contain four
consecutive integers. But show that S does contain a (nonconstant) 4-term arithmetic
progression.
Related question. Does S contain an arithmetic progression of length k for every
integer k ≥ 1? This is currently an unsolved problem! A positive answer would follow
from either of the following conjectures:
• Dickson’s Conjecture. Given linear polynomials a1 n + b1 , . . . , ak n + bk in n, with
ai , bi ∈ Z and ai > 0 for all i, such that no prime p divides (a1 n + b1 ) · · · (ak n + bk )
for all n ∈ Z, there exist infinitely many integers n ≥ 1 such that the values
a1 n+b1 , . . . , ak n+bk are simultaneously prime. (The hypothesis that p not divide
(a1 n + b1 ) · · · (ak n + bk ) is automatic if p > k and p gcd(a1 , b1 ) · · · gcd(ak , bk ), so
checking it for all p is a finite computation.)
The special case a1 = · · · = ak = 1 of Dickson’s Conjecture is the qualitative
form of the Hardy-Littlewood Prime k-tuple Conjecture, which itself is a gener-
alization of the Twin Prime Conjecture, which is the statement that there exist
infinitely many n ≥ 1 such that n and n + 2 are both prime. On the other hand,
Dickson’s Conjecture is a special case of “Hypothesis H” of Schinzel and Sierpiński,
in which the linear polynomials are replaced by distinct irreducible polynomials
f1 (n), . . . , fk (n) with positive leading coefficients. Moreover, for each of these
conjectures, there is a heuristic that predicts that the number of n less than or
equal to x satisfying the conclusion is (c + o(1))x/(ln x)k as x → ∞, where c is a
constant given by an explicit formula in terms of the k polynomials. (See 1988A3
for the definition of o(1).) The quantitative form of Hypothesis H is known as the
Bateman-Horn Conjecture. For more on all of these conjectures, see Chapter 6
of [Ri], especially pages 372, 391, and 409.
280 The William Lowell Putnam Mathematical Competition
• A conjecture of P. Erdős. If T is a set of positive integers such that n∈T 1/n
diverges, then T contains arbitrarily long finite arithmetic progressions. Erdős,
who frequently offered cash rewards for the solution to problems, offered his
highest-valued reward of $3000 for a proof or disproof of this statement. See [Gr1,
p. 24] or [Guy, p. 16].
Let us explain why either of the two conjectures above would imply that our set
S contains arithmetic progressions of arbitrary length. We will use the theorem
mentioned in 1991B5, that any prime congruent to 1 modulo 4 is in S.
Fix k ≥ 4, and let @i (n) = 4n + 1 + i(k!) for i = 1, 2, . . . , k. Let P (n) =
@1 (n)@2 (n) . . . @k (n). If p is prime and p ≤ k, then p does not divide P (0). If p is
prime and p > k, then for each i, the set { n ∈ Z : p | @i (n) } is a residue class
modulo p, so there remains at least one residue class modulo p consisting of n such
that p P (n). Hence Dickson’s Conjecture predicts that there are infinitely many n
such that @1 (n), . . . , @k (n) are simultaneously prime. Each of these k primes would
be congruent to 1 modulo 4, and hence would be in S.
Now we show that the conjecture of Erdős implies that S contains arithmetic
progressions of arbitrary length, and even better, that the subset T of primes congruent
to 1 mod 4 contains such progressions. It suffices to prove that p∈T 1/p diverges,
or equivalently that lims→1+ p∈T 1/ps = ∞. The proof of Dirichlet’s Theorem on
primes in arithmetic progressions gives a precise form of this, namely:
1 : 1 1
lim ln = .
s→1+ ps s−1 2
p∈T
1
Since lims→1+ ln s−1 = ∞, this implies lims→1+ p∈T 1/ps = ∞.
More generally, one says that a subset P of the set of prime numbers has Dirichlet
density α if
1 : 1
lim ln = α.
s→1+ ps s−1
p∈P
Dirichlet’s Theorem states that if a and m are relatively prime positive integers,
then the Dirichlet density of the set of primes congruent to a modulo m equals
1/φ(m), where φ(m) is the Euler φ-function defined in 1985A4. See Theorem 2 in
Chapter VI, §4 of [Se1] for details.
Solution. (See Figure 42.) We deduce from the area of P1 P3 P5 P7 that the radius
of the circle is 5/2. If s > t are the sides of the rectangle P2 P4 P6 P√8 , then s2 +t2 =√10
and st = 4, so (s + t)2 = 18 and (s − t)2 = 2. Therefore s + t = 3 2 and s − t = 2,
Solutions: The Sixty-First Competition (2000) 281
P3
P2 P4
P5
P1
P6
P7
FIGURE 42.
√ √ √
2 2 and t = 2. Without loss of generality, assume that P2 P4 = 2 2
yielding s = √
and P4 P6 = 2.
For notational ease, let [Q1 Q2 · · · Qn ] denote the area of the polygon Q1 Q2 · · · Qn .
By symmetry, the area of the octagon can be expressed as
[P2 P4 P6 P8 ] + 2[P2 P3 P4 ] + 2[P4 P5 P6 ].
√
Note that [P2 P3 P4 ] is 2 times the distance from P3 to P2 P4 , which
√ is maximized when
P3 lies on the midpoint of arc P2 P4 ; similarly, [P4 P5 P6 ] is 2/2 times the distance
from P5 to P4 P6 , which is maximized when P5 lies on the midpoint of arc P4 P6 . Thus
the area of the octagon is maximized when P3 is the midpoint of arc P2 P4 and P5
is the midpoint of arc P4 P6 (in which case P1 P3 P5 P7 is indeed a square). In this
case, the distance
√ from P3 to P2 P4 equals the radius
√ of the circle minus half of P4 P6 ,
√2 P3 P4 ] = 5 − 1. Similarly [P4 P5 P6 ] = 5/2 − 1, so the area of the octagon
so [P
is 3 5.
B B
cos x cos x
cos x2 dx = cos x2 (2x dx)
1 2x 1 4x2
B
cos x B −2 cos x − x sin x
= 2
sin x 2
− sin x2 dx.
4x 0 1 4x3
by the nearest odd integer multiple of π/2 tends to zero as B → ∞. Therefore (1)
∞
converges if and only if n=1 an converges, where
(n+ 12 )π π/2
cos u cos t
an = du = (−1) n
dt.
(n− 2 )π 2 u + 1/4
1
−π/2 2 t + nπ + 1/4
B + Bi
z = t (1 + i)
z = B + ti
z=t
0 B
FIGURE 43.
Since
2 2 2
±i(t+ti)
|ei(t+ti) | = e−2t ∓t
≤ e−t
for t ≥ 1, and
2
±i(B+ui)
|ei(B+ui) | = e−2Bu∓u ≤ e−u
once B ≥ 1, the two integrals on the right of (2) have finite limits as B → ∞, as
desired.
Remark. By extending the previous analysis, we can evaluate
∞
2
I(t) = (sin tx)eix dx
0
can be changed to the diagonal ray x = eiπ/4 y with y ranging from 0 to ∞, without
changing its value. More generally, this argument shows that for any t ∈ R,
∞
2
I(t) = sin(eiπ/4 ty)e−y eiπ/4 dy.
0
converges for any real t, by the Ratio Test. (We used the identity
∞
z n e−z dz = Γ(n + 1) = n!.)
0
Thus
∞ ∞ ∞
1 ei(2n+2)π/4 (−1)n t2n+1 n −z 1 (−1)n in+1 n! t2n+1
I(t) = z e dz =
2 n=0 (2n + 1)! 0 2 n=0 (2n + 1)!
∞
t (−1)m (2m)! t4m
Im(I(t)) = .
2 m=0 (4m + 1)!
Pairing the factor j in (2m)! with the factor 2j of (4m + 1)!, and dividing numerator
and denominator by 2m factors of 4, which we distribute among the odd factors of
(4m + 1)! in the denominator, we obtain
t 3 5 t4
Im(I(t)) = F
1 2 1; , ; − ,
2 4 4 64
where the generalized hypergeometric function is defined by
∞
(a1 )m · · · (ap )m z m
p Fq (a1 , . . . , ap ; b1 , . . . , bq ; z) = · ,
m=0
(b1 )m · · · (bq )m m!
If sin(bx) is replaced by cos(bx) in the above two integrals, then they can be evaluated
in terms of elementary functions:
∞ 2
1 π
cos(bx) sin(ax2 ) dx = cos(b2 /4a) − sin(b2 /4a)
0 2 2a
∞ 2
2 1 π
cos(bx) cos(ax ) dx = cos(b2 /4a) + sin(b2 /4a) .
0 2 2a
All of these integrals are originally due to Cauchy [Tal].
Remark. Oscillatory integrals like the one in this problem occur frequently in
analysis and mathematical physics. They can be bounded or evaluated by the methods
given here in some cases, and often can be estimated by a technique known as the
stationary phase approximation [CKP, Section 6.4]. This method was first used by
Stokes, to obtain an asymptotic representation for the function
∞
f (x) = cos x(ω 3 − ω) dω
0
valid for large positive real values of x.
C
A B
r
q q
FIGURE 44.
The point C on arc AB maximizing the height of ABC in Solution 1 to 2000A5.
Related question. Examine Solution 1 to prove that if the longest side of√4ABC
has length equal to (4r)1/3 , it is an isosceles right triangle with sides 1, 1, 2. (We
will prove a stronger result soon.)
Solution 2. We will prove the result with r1/3 replaced by (2r)1/3 , using:
Lemma. If a, b, c are the lengths of sides of a triangle with area K and circumradius
r, then K = abc/(4r).
Proof. Let A, B, C be the vertices opposite the sides of length a, b, c, respectively.
If we view BC as base, the height is b sin C, so K = 12 ab sin C. Now use the Extended
Law of Sines,
sin A sin B sin C 1
= = = ,
a b c 2r
to replace sin C by c/(2r).
Let a, b, c be the distances between the points. By the lemma, the area of the
triangle with the three points as vertices is abc/(4r). On the other hand, the area is
half an integer (see the first remark in 1990A3). Thus abc/(4r) ≥ 1/2, and
max{a, b, c} ≥ (abc)1/3 ≥ (2r)1/3 .
C
✑PPP
✑ PP b
a ✑ PP
✑ h PP
✑ a b PP
✑ A
B c
FIGURE 45.
Defining a and b , and constructing the parallelogram ACBD.
Figure 45). Since AB is the longest side of 4ABC, point C lies directly above the
segment AB, so a + b = c. By the Pythagorean Theorem,
%
1
a = a −h = a 1− 2 2
2 2 2
a c
1 1
=a 1−O =a−O
a2 c2 ac2
1
=a−O 3 ,
c
and similarly b = b − O(1/c3 ).
If we form a parallelogram ACBD as in Figure 45, then D also has integer
coordinates, so
If r is sufficiently large, then c ≥ (4r)1/3 is also large, so this contradicts 4ab > c2 .
For fixed c, the right-hand side is a monic quadratic in d2 so its maximum value for
d2 ∈ [1 − 4h2 , c2 ] is attained at an endpoint. In other words, the inequality remains
true either when d2 is replaced by 1−4h2 or when d2 is replaced by c2 . At d2 = 1−4h2 ,
the inequality becomes
c4 < (c2 + 2cd + 1)(c2 − 2cd + 1) = (c4 + 2c2 + 1) − 4c2 (1 − 4h2 ),
which, since h = 1/c, is equivalent to c2 < 17/2. At d2 = c2 , the inequality becomes
c4 < (4c2 + 4h2 )(4h2 ) = 16(1 + c−4 ),
which implies c4 < 17. Thus in either case, c2 < 17/2. But c2 is a sum of integer
squares, so c2 ∈ {1, 2, 4, 5, 8}. The only√lattice triangles
√ √ of area 1/2 with such a value
of c2 are those with side lengths 1, 1, 2 and 1, 2, 5.
Remark. The result just proved is nearly best possible. We now construct examples
with r → ∞ such that max{a, b, c} = 2r1/3 + O(r−1/3 ).
Let n be a large positive integer, and take the circle √passing through (0, 0),
(n, 1), (2n + 1, 2). Then the three sides of the triangle are n2 + 1, (n + 1)2 + 1,
2
(2n + 1) + 4, and K = 1/2, so the lemma of Solution 2 implies
1 2
r= (n + 1)(n2 + 2n + 2)(4n2 + 4n + 5).
2
Thus
1/6
2r1/3 = 2 (n2 + 1)(n2 + 2n + 2)(n2 + n + 5/4)
1/6
= 2n (1 + n−2 )(1 + 2n−1 + 2n−2 )(1 + n−1 + (5/4)n−2 )
5
= 2n + 1 + n−1 + O(n−2 ),
6
and similarly
max{a, b, c} = (2n + 1)2 + 4 = 2n + 1 + n−1 + O(n−2 ),
so
1 1
max{a, b, c} = 2r1/3 + n−1 + O(n−2 ) = 2r1/3 + r−1/3 + O(r−2/3 ).
6 6
A6. (1, 2, 2, 0, 0, 0, 0, 0, 3, 19, 57, 111)
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.
Solution 1. Recall that if f (x) is a polynomial with integer coefficients, then m−n
divides f (m) − f (n) for any integers m and n. In particular, if we put bn = an+1 − an ,
then bn divides bn+1 for all n. On the other hand, we are given that a0 = am = 0,
which implies that a1 = am+1 and so b0 = bn . If b0 = 0, then a0 = a1 = · · · = am and
we are done. Otherwise, |b0 | = |b1 | = |b2 | = · · · , so bn = ±b0 for all n.
Now b0 + · · · + bm−1 = am − a0 = 0, so half of the integers b0 , . . . , bm−1 are positive
and half are negative. In particular, there exists an integer 0 < k < m such that
Solutions: The Sixty-First Competition (2000) 289
bk−1 = −bk , which is to say, ak−1 = ak+1 . From this it follows that an = an+2 for all
n ≥ k − 1; in particular, for n = m, we have
0 = am = am+2 = f f (am ) = f f (a0 ) = a2 .
Solution. Consider the seven triples (r, s, t) with r, s, t ∈ {0, 1} not all zero. If
aj , bj , cj are not all even, then four of the sums raj + bsj + tcj with r, s, t ∈ {0, 1} are
even and four are odd. (For example, if aj is odd, then flipping r changes the sum
between even and odd, so half of the sums must be even and half odd.) Of course the
sum with r = s = t = 0 is even, so at least four of the seven triples with r, s, t not all
zero yield an odd sum. In other words, at least 4N of the quadruples (r, s, t, j) yield
odd sums. By the Pigeonhole Principle, there is a triple (r, s, t) for which at least
4N/7 of the sums are odd.
290 The William Lowell Putnam Mathematical Competition
† The proposers intended for Nk to count only the zeros in the interval [0, 1).
Solutions: The Sixty-First Competition (2000) 291
df k
Solution. We first show Nk ≤ 2N for all k ≥ 0. Write f (k) (t) for dtk
. If we use
the identity sin x = (eix − e−ix )/(2i) and set z = e2πit , then
N
1
f (k) (t) = (2πij)k aj (z j − z −j )
2i j=1
for any n ∈ Z. Taking x = cos θ in the functional equation shows that if f (cos 2θ) = 0
and cos θ = 0, then f (cos θ) = 0 as well. Therefore
" #
f cos 2−k (2π/3 + 2πn) = 0
for all k, n ∈ Z with k ≥ 0. The numbers 2−k (2π/3+2πn) are dense in R, so continuity
of f (cos x) yields f (cos r) = 0 for all r ∈ R. Thus f is zero on [−1, 1].
Remark. We started with f (−1/2) = 0 instead of f (1) = 0 to avoid complications
arising from the condition cos θ = 0 in the iteration.
Solution. We claim that all integers N of the form 2k , with k a positive integer
and N > max S0 , satisfy the desired condition.
It follows from the definition of Sn that
xj ≡ (1 + x) xj (mod 2).
j∈Sn j∈Sn−1
(When we write that two polynomials ai xi and bi xi in Z[x] are congruent modulo
2, we mean that ai ≡ bi (mod 2) for all i ≥ 0, or equivalently, that the two polynomials
are equal when considered in F2 [x]. Thus for instance, x2 ≡ x (mod 2) as polynomials,
even though m2 ≡ m (mod 2) holds for any particular integer m.) By induction on
n,
k
From the identity (x + y)2 ≡ x2 + y 2 (mod 2) and induction on n, we have (x + y)2 ≡
k k
x2 +y 2 (mod 2). (This also follows from Kummer’s Theorem, described in Solution 2
to 1997A5.) Hence if N = 2k for some k ≥ 1, then
xj ≡ (1 + xN ) xj .
j∈Sn j∈S0
Now |B| = 2n−k+1 , since we can choose ej for all j except 2, 22 , . . . , 2k−1 , and then
3
the condition j∈Ti ej = 1 determines eti in terms of the ej already chosen. To see
that there cannot be three points in B, any pair of which differ in two coordinates,
suppose that such points exist; then there exist coordinates l, m, n at each of which
two of the three points are the same and the third is different. At least two of l, m, n
must have the same parity; suppose l and m have the same parity. Then there exists
i ∈ {1, . . . , k − 1} such that Ti contains one of l and m but not the other. Hence at the
3
two points that only differ in coordinates l and m, the values of j∈Ti ei are different.
This contradicts the definition of B, which says that both values should equal 1.
Remark. The construction of patterns such as in the previous remark is known as
design theory. This topic is the subject of [BJL].