Solutions to Putnam Exam Problems for 1 Dec..

2001

A1) Consider a set S and a binary operation * on S ; that is, x*y is in S for each x and y
in S . Assuming that (x*y)*x = y for all x and y in S , prove that x*(y*x) = y for all x and
y in S .

Solution: The proof resembles the pattern-matching performed by Macro Preprocessors in

Compilers for Computer Programming Languages like C . Matched patterns are underscored:
x*(y*x) = ((y*x)*y)*(y*x) = ((y*x)*y)*(y*x) = y , as required.

A2) C1, C2, …, Cn are n coins. For each k , coin Ck is biased so that, when tossed, it falls
Heads with probability 1/(2k+1) . If all n coins are tossed, what is the probability that the
number of Heads will be odd? Express the answer explicitly as a rational function of n .

Solution: The probability is Pn := n/(2n+1) , as will be confirmed here by induction: Let

Hk := 1/(2k+1) and begin with P0 = 0 and P1 =H1 = 1/3 . For every n > 0 we find Pn by first
flipping the first n–1 coins, getting an odd number of Heads among n–1 coins with probability
Pn–1 , even with probability 1–Pn–1 , and then we flip coin Cn to get an odd number of Heads
among n coins with probability
Pn = Hn(1–Pn–1) + (1–Hn)Pn–1 = Hn + (1–2Hn)Pn–1 = ( 1 + (2n–1)Pn–1 )/(2n+1) .
From this recurrence and the induction hypothesis Pn–1 = (n–1)/(2n–1) follows Pn = n/(2n+1) as
was claimed. ( Where did the induction hypothesis come from? It was a guess generated by
running the recurrence for several steps to see whether a pattern presented itself.)

A3) For each integer m the polynomial Pm(x) := x4 – (2m+4)x2 + (m–2)2 . For what values
of m is Pm(x) the product of two nonconstant polynomials with integer coefficients?

Solution: Either m is a perfect square, or m/2 is a perfect square. To see why, observe first
that the factors of Pm are monic because Pm is monic; observe second that if Pm(x) has a linear
factor, say (x–k) , than (x+k) must be a factor too because Pm(–x) = Pm(x) ; and then (x2–k2)
must be a factor. In other words, Pm factors into monic quadratic factors if it factors at all.

Now two cases must be considered according to whether each quadratic factor shares the sign-
symmetry of Pm or not. In the first case, Pm(x) = (x2 – j)(x2 – k) for some integers j and k
(not necessarily positive for all we know now); matching coefficients makes j+k = 2m+4 and
jk = (m–2)2 , whence follows {j, k} = {2(1+√m/2)2, 2(1–√m/2)2} from which we infer that m/2
must be a squared integer. In the second case, when neither quadratic factor of Pm shares its
sign symmetry, replacing x by –x in the factorization of Pm(x) must swap its factors thus:
Pm(x) = (x2 + jx + k)(x2 – jx + k) for some integers j and k . Matching coefficients again makes
j2 – 2k = 2m+4 and k2 = (m–2)2 , whence follows k = +(m–2) (but not –(m–2) lest j2 = 8 )
and j = ±2√m , so m must be a squared integer. In both cases Pm factors as shown.

Prof. W. Kahan page 1/8 December 17, 2001 7:58 am

This document was created with FrameMaker 4 0 4

 Solutions to Putnam Exam Problems for 1 Dec.. 2001

A4) Triangle ABC has area 1 . Points E, F, G lie respectively on sides BC, CA, AB in such
a way that AE bisects BF at point R , and BF bisects CG at point S , and CG bisects AE
at point T . Find the area of triangle RST .
C

F
S
E
T R

Ao G
B

Solution: The area of RST is 2/(3+√5)2 = (7 – 3√5)/4 ≈ 0.072949… , gotten by brute force.
Move the origin to A and identify the other letters with column vectors from this origin to the
corresponding points. B and C shall be our basis vectors. For some positive scalars γ, φ, ξ, τ, σ
and ρ all less than 1 , the specifications of the problem put
G = γB , F = (1–φ)C , E = ξC + (1–ξ)B ,
R = (F+B)/2 = (1–ρ)E , S = (G+C)/2 = σB + (1–σ)F , T = E/2 = τC + (1–τ)G .
Here γ, φ and ξ must be chosen to satisfy the equations involving R, S and T , which are …
2R = (1–φ)C + B = 2(1–ρ)(ξC + (1–ξ)B) , whence 1–φ = 2(1–ρ)ξ and 1 = 2(1–ρ)(1–ξ) .
Eliminate ρ to obtain the equation ξ = (1–φ)/(2–φ) .
2S = γB + C = 2σB + 2(1–σ)(1–φ)C , whence γ = 2σ and 1 = 2(1–σ)(1–φ) .
Eliminate σ to obtain the equation φ = (1–γ)/(2–γ) .
2T = ξC + (1–ξ)B = 2τC + 2(1–τ)γB , whence ξ = 2τ and 1–ξ = 2(1–τ)γ .
Eliminate τ to obtain the equation γ = (1–ξ)/(2–ξ) .
Apparently γ = φ = ξ = 2/(3 + √5) = (3 – √5)/2 ≈ 0.382 , the root of ξ2 – 3ξ + 1 = 0 between 0
and 1 . Now the edge-vectors of the triangle RST turn out to be …
[R–T, S–T] = [B, C] ξ 2ξ – 1 /2 , whence
1 – 2ξ 1 – ξ

Area(RST) = Area(ABC)·det( ξ 2ξ – 1 )/4 = ξ2/2 after simplification.

1 – 2ξ 1 – ξ

A5) Prove that the equation xn+1 – (x+1)n = 2001 determines its positive integer solutions x
and n uniquely.

Solution: x = 13 and n = 2 satisfy the equation. To show that it has no other positive integer
solutions we accumulate constraints upon x and n as follows: First, xn+1 – (x+1)n ≡ 0 mod 3 ;
consequently x ≡ 1 mod 3 and n must be even since trying x ≡ 0 or x ≡ –1 or n odd leads to
contradictions. Of course x > 1 . Second, x divides xn+1 – (x+1)n + 1 = 2002 = 2·7·11·13 ;
consequently x must be one of 7, 13, 22, 91, 154, 286 or 2002. Moreover x ≡ –1 mod (x+1)

Prof. W. Kahan page 2/8 December 17, 2001 7:58 am

 Solutions to Putnam Exam Problems for 1 Dec.. 2001

and n+1 is odd, so 2002 ≡ 0 mod (x+1) , which means x+1 divides 2002 too. Of the seven
possibilities listed above for x , only x = 13 satisfies this last constraint. Then n = 2 works, as
a few minutes of arithmetic confirm. Can any other even n satisfy that given equation? Not if n
is very big, since 13n+1 – 14n < 0 for all sufficiently large n . A computer or programmable
calculator could save time otherwise dissipated in thought by testing values of n until they got
sufficiently large; but that is disallowed, so let us persist in our analysis. Suppose n = 2m+2
worked for some integer m > 0 ; this would mean 2001 = 133 – 142 = 132m+3 – 142m+2 ,
whence (142m – 1)142 = (132m – 1)133 . This last equation would require 133 to divide
142m – 1 = (1+13)2m – 1 = 2m·13 + m(2m–1)·132 + (…)·133 ,
whence 132 would have to divide m·(2 + (2m–1)·13) , and therefore m would have to be a
multiple of 169 . But when m ≥ 169 we must have n = 2m+2 ≥ 340 ; and then (with x = 13 )
2001 = xn+1 – (x+1)n = xn·(x – (1 + 1/x)n) ≤ xn·(13 – (1 + 1/13)340) < 0 .
It can’t happen.

A6) Can an arc of a parabola inside a circle of radius 1 have length greater than 4 ?
Solution: YES is the short answer. The long answer is tedious and will be only outlined. In the
(x,y)-plane where the circle’s equation is y2 = 1–x2 , the parabola in question has the equation
y2 = 4z2(1+x) for a very tiny constant z > 0 . The arc in question runs from x = –1 up to
x = T := 1 – 4z2 . Let us consider only the upper half of that arc, the half above the x-axis, since
the lower half is just the upper half’s reflection in the x-axis. We shall show that this half-arc’s
length L exceeds 2 for all z tiny enough. In fact, along this half-arc whereon y = 2z√1+x ,
L(z) = ∫–1T √(1 + (dy/dx)2) dx = ∫–1T √(1 + z2/(1+x)) dx at T = 1 – 4z2
= √(T+1)·√(T+1 + z2) + z2·ln( ( √(T+1) + √(T+1 + z2) )/z )
= √(2 – 4z2)·√(2 – 3z2) + z2·ln( ( √(2 – 4z2) + √(2 – 3z2) )/z ) .
L(z) > 2 for all z tiny enough because L(z) → 2 as z → 0+ and, differentiating,
L'(z)/z = 2·ln( ( √(2 – 4z2) + √(2 – 3z2) )/z ) – 8√((2 – 3z2)/(2 – 4z2)) → +∞ as z → 0+ .
-4
x 10
14

12

L(z) – 2 : 10

6
L(z) - 2

-2

-4

-6
0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09
Z

Prof. W. Kahan page 3/8 December 17, 2001 7:58 am

 Solutions to Putnam Exam Problems for 1 Dec.. 2001

L(z) need not be obtained explicitly to establish that L(0) = 2 and determine that L'(z)/z > 0 for all z tiny enough,
but the foregoing computations of L and L' require no cleverness and help to satisfy curiosity about how much the
half-arc length L(z) exceeds 2 and for which z . Numerical computation indicates that L(z) > 2 only while
0 < z < 0.08483287… , and max{L } is L(0.051546…) = 2.001335… . The short answer YES is barely true.

Alternate Solution: Due to Austin Shapiro, it does not require explicit evaluation of an integral
unfamiliar to many calculus students. Instead his solution reduces problem A6 to a familiar
divergent series. Instead of drawing a sufficiently narrow parabolic arc inside the unit circle, his
solution fixes the parabola and draws a circle sufficiently big to enclose an arc of that parabola
longer than twice the circle’s diameter. The equation of the fixed parabola P is y = x2 . The
equation of the circle Cn is x2 + (y–n)2 = n2 for a big positive integer n to be determined later.

Because Cn has diameter 2n and center at (x, y) = (0, n) , circle Cn and parabola P intersect
tangentially at (x, y) = (0, 0) , where their common tangent is the x-axis. Their two other
intersections are at (x, y) = (±√2n–1, 2n–1) . As x runs from –√2n–1 to +√2n–1 , the point
(x, y) = (x, x2) on the arc of P within Cn runs down from (–√2n–1, 2n–1) to (0, 0) and back
up to (+√2n–1, 2n–1) , staying within Cn because, just on that arc,
x2 + (y–n)2 – n2 = x2 + (x2–n)2 – n2 = –x2(2n–1 – x2) ≤ 0 .

Since P and Cn are each its own reflection in the y-axis, we can solve problem A6 by showing
that the length Ln of the half-arc of P within the right-hand D-shaped semicircle of Cn
exceeds its diameter 2n when n is big enough. Ln exceeds the sum of the lengths of secants
joining consecutive intersections of P with Ck for k = 0, 1, 2, …, n in turn; consequently
Ln – 2n ≥ √2 + ∑1≤k≤n–1 √( (√2k+1 – √2k–1)2 + ((2k+1) – (2k–1))2 ) – 2n .
To further reduce the right-hand side the inequality (√u – √v)/(u–v) = 1/(√u + √v) > 1/√2u + 2v ,
easily proved valid for all distinct positive u and v , is applied twice in succession to obtain
Ln – 2n > √2 + ∑1≤k≤n–1 √( (2/√8k)2 + (2)2 ) – 2n
= √2 – 2 + ∑1≤k≤n–1 (√( 1/(2k) + 4 ) – 2 )
> √2 – 2 + ∑1≤k≤n–1 (1/(2k))/√16 + 1/k > √2 – 2 + (∑1≤k≤n–1 1/k)/√68 .
The last (∑…) is the harmonic series and diverges as n → +∞ ; therefore Ln – 2n → +∞ so that
Ln – 2n > 0 for all sufficiently big n . (Actually any n ≥ 60 is sufficiently big.) End of proof.

====================

Prof. W. Kahan page 4/8 December 17, 2001 7:58 am

 Solutions to Putnam Exam Problems for 1 Dec.. 2001

B1) Let n be an even positive integer. Write the numbers 1, 2, …, n2 into the squares of an n-
by-n grid so that the k-th row, from left to right, is
(k–1)n + 1, (k–1)n + 2, …, (k–1)n + n .
Color the squares of the grid so that half of the squares in each row and in each column are red
and the other half are black. (A checkerboard coloring is one possibility.) Prove that, for any
such coloring, the sum of the numbers on the red squares equals the sum of the numbers on the
black squares.

Solution: Let N(k, j) := (k–1)n + j be the number written into column j of row k for 1 ≤ j ≤ n
and 1 ≤ k ≤ n . Set S(k,j) := +1 if red is the color in column j of row k ; set S(k, j) := –1 if the
color is black. ∑j S(k, j) = 0 for every k since each row has as many +1s as –1s ; similarly
∑k S(k, j) = 0 for every j . Problem B1 is solved by proving that ∑j ∑k S(k, j)·N(k, j) = 0 ;
∑j ∑k S(k, j)·N(k, j) = ∑j ∑k S(k, j)·((k–1)n + j) = ∑j ∑k S(k, j)·(k–1)n + ∑j ∑k S(k, j)· j
= ∑k (∑j S(k, j))·(k–1)n + ∑j (∑k S(k, j))· j = 0 + 0 as claimed.

B2) Find all pairs of real numbers (x, y) satisfying the system of equations
1/x + 1/(2y) = (x2 + 3y2)(3x2 + y2) and 1/x – 1/(2y) = 2(y4 – x4) .

Solution: Adding and subtracting the given equations and multiplying up transforms them into
2 = x·Q(x2, y2) and 1 = y·Q(y2, x2) wherein Q(x, y) := x2 + 10xy + 5y2 . Then we find
2±1 = x·Q(x2, y2) ± y·Q(y2, x2) = (x±y)5 , whence follows x+y = 5√3 and x–y = 1 .
Therefore the sole solution-pair (x, y) has x = (5√3 + 1)/2 and y = (5√3 – 1)/2 .
—————— ———————

B3) For any positive integer n let s(n) denote the integer closest to √n . Evaluate
∑n=1∞ (2s(n) + 2–s(n))/2n .

Solution: The sum is 3 . Why? Observe first that s(n) = m just when m(m–1) < n ≤ m(m+1)
because (m ± 1/2)2 = m(m ± 1) + 1/4 . Therefore the range 1 ≤ n < ∞ of summation can be
broken into disjoint subintervals of the form T(m)+1 := m(m–1) + 1 ≤ n ≤ m(m+1) = T(m+1)
for m = 1, 2, 3, … . Then the sum in question takes the form
∑1∞ (2s(n) + 2–s(n))/2n = ∑m=1∞ ∑n=T(m)+1T(m+1) (2s(n) + 2–s(n))/2n
= ∑m=1∞ ∑n=T(m)+1T(m+1) (2m + 2–m)/2n
= ∑m=1∞ (2m + 2–m) ∑n=T(m)+1T(m+1) 2–n
= ∑m=1∞ (2m + 2–m) ( 2–T(m) – 2–T(m+1) ) … geom. series’ sum
= ∑m=1∞ (2–m(m–2) – 2–m(m+2)) after some algebra
= ∑m=1∞ 2–m(m–2) – ∑M=3∞ 2–M(M–2)
= 2 + 1 , as claimed.

Prof. W. Kahan page 5/8 December 17, 2001 7:58 am

 Solutions to Putnam Exam Problems for 1 Dec.. 2001

B4) Let S denote the set of rational numbers other than –1, 0 and 1 . Define ƒ : S → S by
ƒ(x) := x – 1/x . Prove or disprove that ∩1∞ ƒ(n)(S) = ∅ wherein the n-fold composition
ƒ(n) := ƒoƒo…oƒ , and ƒ(n)(S) is the set of all values taken by ƒ(n)(s) as s ranges over S .
← n →

Solution: We shall prove that the intersection ∩1∞ ƒ(n)(S) is empty. The set S consists of
rational numbers m/n with integers n ≠ 0 , m ≠ 0 , |m| ≠ |n| and GCD(|m|, |n|) = 1 . For all
such rational numbers define K(m/n) to be the sum of the exponents in the prime factorization of
|m·n| . For example, K(–8/45) = 6 . Observe that ƒ(m/n) = (m–n)(m+n)/(m·n) lies in S
whenever m/n does, and that K(ƒ(m/n)) > K(m/n) because GCD(|(m–n)(m+n)|, |m·n|) = 1 .
Therefore every s in ƒ(n)(S) has K(s) > n ; and each s in ƒ(n)(S) is absent from ƒ(K(s))(S) .

B5) Let µ and ß be given real numbers strictly between 0 and 1/2 , and let g be a
continuous real-valued function such that g(g(x)) = µ·g(x) + ß·x for all real x . Prove that
g(x) = c·x for some constant c .

Solution: Let ı denote the identity function ı(x) = x and let gn denote the n-fold composition
gn(x) = g(gn–1(x)) starting from g0 = ı and g1 = g . Now the given equation takes the form
g2 = µ·g1 + ß·g0 , whence repeated substitution yields gn+1 = µ·gn + ß·gn–1 , and therefore

[gn+1, gn] = [gn, gn–1]G = [g, ı]Gn where G := µ 1 . Its eigenvalues are ç := (√(µ2+4ß) + µ)/2
β 0
and ¢ := –(√(µ2+4ß) – µ)/2 with 0 < –¢ < ç < 1 , 0 < ç+¢ = µ < 1/2 and 0 < ß = –¢·ç < 1/2 .
n
Its eigenvalue/vector decomposition leads to Gn = 1 – 1 · ç 0 · ç 1 /(ç–¢) for all integers
–¢ ç n ¢ 1
0 ¢
n , positive and negative. Evidently Gn → O as n → +∞ , and consequently so does
[gn+1(x), gn(x)] = [g(x), x]Gn → [0, 0] for each real x . Because g is continuous, we may take
the limit in the equation g(gn(x)) = gn+1(x) to infer that g(0) = 0 . However, if x ≠ 0 then
0 ≠ ß·x = g(g(x)) – µ·g(x) and therefore g(x) ≠ 0 ; and then gn(x) ≠ 0 for every n ≥ 0 .

More generally, g takes every value in its range just once. To see why, suppose g(x) = g(x') ;
then x = (g(g(x)) – µ·g(x))/ß = (g(g(x')) – µ·g(x'))/ß = x' . Consequently the function inverse to
g must be g–1(y) := (g(y) – µ·y)/ß ; for any y in the range of g , the equation y = g(x) has just
the one solution x = g–1(y) , and this g–1 is continuous too. Therefore g must be a strictly
monotonic function, either strictly increasing or strictly decreasing; and since g(0) = 0 we infer
that the sign of g(x)/x must be the same for all x ≠ 0 . Now two cases must be considered:

Prof. W. Kahan page 6/8 December 17, 2001 7:58 am

 Solutions to Putnam Exam Problems for 1 Dec.. 2001

In the first case, g(x)/x < 0 for all x ≠ 0 . Then we can infer that g(x) = ¢·x as follows: For any
x for which g(x) – ¢·x ≠ 0 we would find from the eigen-decomposition of Gn that

[gn+1(x), gn(x)]/çn → [g(x), x] 1 – 1 · 1 0 · ç 1 /(ç–¢) = [ç, 1](g(x) – ¢·x)/(ç–¢) ≠ [0, 0] ,

–¢ ç 0 0 ¢ 1
whence gn+1(x)/gn(x) → ç > 0 , when actually every gn+1(x)/gn(x) = g(gn(x))/gn(x) < 0 . This
contradiction implies that g(x) = ¢·x for all x if ever g(x)/x < 0 .

In the second case g(x)/x > 0 for all x ≠ 0 . In this case we wish to let n → –∞ in the formula
[gn+1, gn] = [g, ı]Gn , interpreting gn(x) = g–1(gn+1(x)) as the |n|-fold composition of the inverse
function g–1 when n < 0 . Before doing so, let’s find out whether the range of g , the domain
of g–1 , is the whole real axis. Because g is strictly increasing, it could be bounded above by a
finite least upper bound L only if g(x) → L as x → +∞ ; but then taking limits in the equation
g(g(x)) = µ·g(x) + ß·x would lead to the contradiction L ≥ g(L) = µ·L + ∞ . Similarly we infer
that g is unbounded below. Therefore the domain of g–n is the whole real axis for –n = –1 and
then for all –n ≤ –1 . Moreover, the formula g(y) = µ·y + ß·g–1(y) that defined g–1 can be
composed to yield g–n+1 = µ·g–n + ß·g–n–1 which, when rewritten [g–n+1, g–n] = [g–n, g–n–1]G ,
vindicates the formula [g1–n, g–n] = [g, ı]G–n we shall use to deduce that g(x) = ç·x : For any x
for which ç·x – g(x) ≠ 0 we would find from the eigen-decomposition of G–n that as n → +∞

[g1–n(x), g–n(x)]·¢n → [g(x), x] 1 – 1 · 0 0 · ç 1 /(ç–¢) = [¢, 1](ç·x – g(x))/(ç–¢) ≠ [0, 0] ,

–¢ ç 0 1 ¢ 1
whence g1–n(x)/g–n(x) → ¢ < 0 , when actually every g1–n(x)/g–n(x) = g(g–n(x))/g–n(x) > 0 .
This contradiction implies that g(x) = ç·x for all x if ever g(x)/x > 0 . End of proof for B5.
Of all the problems on this exam, I think B5 comes closest to what Mathematicians like me do for a living.

B6) Assume that a1, a2, a3, …, an, … is an increasing sequence of positive real numbers such
that an/n → 0 as n → +∞ . Must there exist infinitely many positive integers n such that
an–j + an+j < 2an for j = 1, 2, …, and n–1 ?

Solution: Yes. To see why, plot the points (n, an) in the (x, y)-plane and let C be the upper
boundary of the convex hull of all those points. C consists of segments of lines lying above all
those points except for the points that lie on C . Could only finitely many of them lie on C ? If
so, there would be a last point, say (N, aN) , beyond which C would be a semi-infinite line
segment lying barely above all points (n, an) with n > N . Therefore this segment’s slope would
be s := supn>N (an – aN)/(n–N) > 0 . But (an – aN)/(n–N) → 0 as n → +∞ because an/n → 0 ,
so actually s = maxn>N (an – aN)/(n–N) = (aM – aN)/(M–N) for some M > N , implying that
(N, aN) could not be the last point on C after all. Therefore C passes through infinitely many
boundary vertices (n, an) . Each such boundary vertex lies above every line segment joining two
points (n–j, an–j) and (n+j, an+j) on or under C for 1 ≤ j < n ; this means an > (an–j + an+j)/2
for every j = 1, 2, …, n–1 , as the problem requires.

Prof. W. Kahan page 7/8 December 17, 2001 7:58 am

 Solutions to Putnam Exam Problems for 1 Dec.. 2001

.........................

I am no exception to the complaint “Everybody wants to be an editor”. I have taken the liberty of redrafting some of
the problems on this year’s Putnam Exam. There are several reasons to do so. One is that I eschew jargon as much
as possible because several of my students are not yet comfortable with it; for instance, I prefer the sequence “ a1,
a2, a3, …, an, … ” to “ (an)n≥1 ” and “n-by-n” to “nxn”. I avoid using an unadorned “ a ” as a variable lest it be
confused with the indefinite article, and decline to omit “and” from “ for j = 1, 2, …, and n–1 ” lest someone read
“or” in its place. I use the future tense instead of the present in “If all n coins are tossed, what is the probability
that the number of Heads will be odd?” because after the toss the probability is either 0 or 1 . The last two
commas in “Points E, F, G lie, respectively, on sides …” are undeserved. “Prove that there are unique positive
integers …” is too easy because every integer is unique. In B3 I typed “s(n)” instead of using symbols absent from
some computers’ fonts. I use “ := ” for assignment or definition to distinguish it from the predicate “ = ”. And so
on. I am a nit-picker; I would have to be one to solve B5 fully correctly. W. K.

Prof. W. Kahan page 8/8 December 17, 2001 7:58 am