The 72nd William Lowell Putnam Mathematical Competition
Saturday, December 3, 2011
A1 Define a growing spiral in the plane to be a sequence
of points with integer coordinates P0 = (0, 0), P1 , . . . , Pn
1 2
such that n ≥ 2 and: 1
lim ∑ Prob(g = x) −
m→∞ b2m n
x∈G
– the directed line segments P0 P1 , P1 P2 , . . . , Pn−1 Pn
are in the successive coordinate directions east is positive and finite.
(for P0 P1 ), north, west, south, east, etc.;
– the lengths of these line segments are positive and B1 Let h and k be positive integers. Prove that for every
strictly increasing. ε > 0, there are positive integers m and n such that
√ √
[Picture omitted.] How many of the points (x, y) with ε < |h m − k n| < 2ε.
integer coordinates 0 ≤ x ≤ 2011, 0 ≤ y ≤ 2011 cannot
be the last point, Pn of any growing spiral? B2 Let S be the set of all ordered triples (p, q, r) of prime
numbers for which at least one rational number x satis-
A2 Let a1 , a2 , . . . and b1 , b2 , . . . be sequences of positive fies px2 + qx + r = 0. Which primes appear in seven or
real numbers such that a1 = b1 = 1 and bn = bn−1 an − 2 more elements of S?
for n = 2, 3, . . . . Assume that the sequence (b j ) is
bounded. Prove that B3 Let f and g be (real-valued) functions defined on an
∞ open interval containing 0, with g nonzero and contin-
1 uous at 0. If f g and f /g are differentiable at 0, must f
S= ∑ a1 ...an
n=1 be differentiable at 0?
converges, and evaluate S. B4 In a tournament, 2011 players meet 2011 times to play
a multiplayer game. Every game is played by all 2011
A3 Find a real number c and a positive number L for which players together and ends with each of the players either
R π/2 r winning or losing. The standings are kept in two 2011×
rc 0 x sin x dx 2011 matrices, T = (Thk ) and W = (Whk ). Initially, T =
lim R π/2 = L.
r→∞ xr cos x dx W = 0. After every game, for every (h, k) (including for
0
h = k), if players h and k tied (that is, both won or both
lost), the entry Thk is increased by 1, while if player h
A4 For which positive integers n is there an n × n matrix
won and player k lost, the entry Whk is increased by 1
with integer entries such that every dot product of a row
and Wkh is decreased by 1.
with itself is even, while every dot product of two dif-
ferent rows is odd? Prove that at the end of the tournament, det(T + iW ) is
a non-negative integer divisible by 22010 .
A5 Let F : R2 → R and g : R → R be twice continuously
differentiable functions with the following properties: B5 Let a1 , a2 , . . . be real numbers. Suppose that there is a
constant A such that for all n,
– F(u, u) = 0 for every u ∈ R;
!2
n
– for every x ∈ R, g(x) > 0 and x2 g(x) ≤ 1; 1
Z ∞
∑ 2
dx ≤ An.
– for every (u, v) ∈ R2 , the vector ∇F(u, v) is either −∞ i=1 1 + (x − ai )
0 or parallel to the vector hg(u), −g(v)i.
Prove there is a constant B > 0 such that for all n,
Prove that there exists a constant C such that for every
n
n ≥ 2 and any x1 , . . . , xn+1 ∈ R, we have
∑ (1 + (ai − a j )2 ) ≥ Bn3 .
C i, j=1
min |F(xi , x j )| ≤ .
i6= j n
B6 Let p be an odd prime. Show that for at least (p + 1)/2
A6 Let G be an abelian group with n elements, and let values of n in {0, 1, 2, . . . , p − 1},
p−1
{g1 = e, g2 , . . . , gk } $ G
∑ k!nk is not divisible by p.
k=0
be a (not necessarily minimal) set of distinct generators
of G. A special die, which randomly selects one of the
elements g1 , g2 , ..., gk with equal probability, is rolled m
times and the selected elements are multiplied to pro-
duce an element g ∈ G. Prove that there exists a real
number b ∈ (0, 1) such that
, Solutions to the 72nd William Lowell Putnam Mathematical Competition
Saturday, December 3, 2011
Kiran Kedlaya and Lenny Ng
bj B
A1 We claim that the set of points with 0 ≤ x ≤ 2011 and Now if (b j ) is bounded above by B, then b j +2 ≤ B+2
0 ≤ y ≤ 2011 that cannot be the last point of a growing B m
for all j, and so 3/2 > Sm ≥ 3/2(1 − ( B+2 ) ). Since
spiral are as follows: (0, y) for 0 ≤ y ≤ 2011; (x, 0) and B
(x, 1) for 1 ≤ x ≤ 2011; (x, 2) for 2 ≤ x ≤ 2011; and B+2 < 1, it follows that the sequence (Sm ) converges to
(x, 3) for 3 ≤ x ≤ 2011. This gives a total of S = 3/2.
A3 We claim that (c, L) = (−1, 2/π) works. Write f (r) =
2012 + 2011 + 2011 + 2010 + 2009 = 10053 R π/2 r
0 x sin x dx. Then
excluded points.
(π/2)r+1
Z π/2
The complement of this set is the set of (x, y) with 0 < f (r) < xr dx =
x < y, along with (x, y) with x ≥ y ≥ 4. Clearly the 0 r+1
former set is achievable as P2 in a growing spiral, while while since sin x ≥ 2x/π for x ≤ π/2,
a point (x, y) in the latter set is P6 in a growing spiral
with successive lengths 1, 2, 3, x + 1, x + 2, and x + y − Z π/2 r+1
2x (π/2)r+1
1. f (r) > dx = .
0 π r+2
We now need to rule out the other cases. Write x1 <
y1 < x2 < y2 < . . . for the lengths of the line segments It follows that
in the spiral in order, so that P1 = (x1 , 0), P2 = (x1 , y1 ), r+1
P3 = (x1 − x2 , y1 ), and so forth. Any point beyond P0 2
lim r f (r) = 1,
has x-coordinate of the form x1 − x2 + · · · + (−1)n−1 xn r→∞ π
for n ≥ 1; if n is odd, we can write this as x1 + (−x2 +
whence
x3 ) + · · · + (−xn−1 + xn ) > 0, while if n is even, we can
write this as (x1 − x2 ) + · · · + (xn−1 − xn ) < 0. Thus no f (r) r(2/π)r+1 f (r) 2(r + 1) 2
point beyond P0 can have x-coordinate 0, and we have lim = lim · = .
r→∞ f (r + 1) r→∞ (r + 1)(2/π)r+2 f (r + 1) πr π
ruled out (0, y) for 0 ≤ y ≤ 2011.
Next we claim that any point beyond P3 must have Now by integration by parts, we have
y-coordinate either negative or ≥ 4. Indeed, each
such point has y-coordinate of the form y1 − y2 + · · · + Z π/2
1
Z π/2
f (r + 1)
(−1)n−1 yn for n ≥ 2, which we can write as (y1 − y2 ) + xr cos x dx = xr+1 sin x dx = .
0 r+1 0 r+1
· · · + (yn−1 − yn ) < 0 if n is even, and
Thus setting c = −1 in the given limit yields
y1 + (−y2 + y3 ) + · · · + (−yn−1 + yn ) ≥ y1 + 2 ≥ 4
(r + 1) f (r) 2
if n ≥ 3 is odd. Thus to rule out the rest of the forbidden lim = ,
r→∞ r f (r + 1) π
points, it suffices to check that they cannot be P2 or P3
for any growing spiral. But none of them can be P3 = as desired.
(x1 − x2 , y1 ) since x1 − x2 < 0, and none of them can
be P2 = (x1 , y1 ) since they all have y-coordinate at most A4 The answer is n odd. Let I denote the n × n identity
equal to their x-coordinate. matrix, and let A denote the n × n matrix all of whose
entries are 1. If n is odd, then the matrix A − I satisfies
A2 For m ≥ 1, write the conditions of the problem: the dot product of any
row with itself is n − 1, and the dot product of any two
3 b1 · · · bm distinct rows is n − 2.
Sm = 1− .
2 (b1 + 2) · · · (bm + 2) Conversely, suppose n is even, and suppose that the ma-
trix M satisfied the conditions of the problem. Consider
Then S1 = 1 = 1/a1 and a quick calculation yields
all matrices and vectors mod 2. Since the dot product
b1 · · · bm−1 1 of a row with itself is equal mod 2 to the sum of the en-
Sm − Sm−1 = = tries of the row, we have Mv = 0 where v is the vector
(b2 + 2) · · · (bm + 2) a1 · · · am
(1, 1, . . . , 1), and so M is singular. On the other hand,
for m ≥ 2, since a j = (b j + 2)/b j−1 for j ≥ 2. It follows MM T = A − I; since
that Sm = ∑m n=1 1/(a1 · · · an ).
(A − I)2 = A2 − 2A + I = (n − 2)A + I = I,
we have (det M)2 = det(A − I) = 1 and det M = 1, con-
tradicting the fact that M is singular.
Saturday, December 3, 2011
A1 Define a growing spiral in the plane to be a sequence
of points with integer coordinates P0 = (0, 0), P1 , . . . , Pn
1 2
such that n ≥ 2 and: 1
lim ∑ Prob(g = x) −
m→∞ b2m n
x∈G
– the directed line segments P0 P1 , P1 P2 , . . . , Pn−1 Pn
are in the successive coordinate directions east is positive and finite.
(for P0 P1 ), north, west, south, east, etc.;
– the lengths of these line segments are positive and B1 Let h and k be positive integers. Prove that for every
strictly increasing. ε > 0, there are positive integers m and n such that
√ √
[Picture omitted.] How many of the points (x, y) with ε < |h m − k n| < 2ε.
integer coordinates 0 ≤ x ≤ 2011, 0 ≤ y ≤ 2011 cannot
be the last point, Pn of any growing spiral? B2 Let S be the set of all ordered triples (p, q, r) of prime
numbers for which at least one rational number x satis-
A2 Let a1 , a2 , . . . and b1 , b2 , . . . be sequences of positive fies px2 + qx + r = 0. Which primes appear in seven or
real numbers such that a1 = b1 = 1 and bn = bn−1 an − 2 more elements of S?
for n = 2, 3, . . . . Assume that the sequence (b j ) is
bounded. Prove that B3 Let f and g be (real-valued) functions defined on an
∞ open interval containing 0, with g nonzero and contin-
1 uous at 0. If f g and f /g are differentiable at 0, must f
S= ∑ a1 ...an
n=1 be differentiable at 0?
converges, and evaluate S. B4 In a tournament, 2011 players meet 2011 times to play
a multiplayer game. Every game is played by all 2011
A3 Find a real number c and a positive number L for which players together and ends with each of the players either
R π/2 r winning or losing. The standings are kept in two 2011×
rc 0 x sin x dx 2011 matrices, T = (Thk ) and W = (Whk ). Initially, T =
lim R π/2 = L.
r→∞ xr cos x dx W = 0. After every game, for every (h, k) (including for
0
h = k), if players h and k tied (that is, both won or both
lost), the entry Thk is increased by 1, while if player h
A4 For which positive integers n is there an n × n matrix
won and player k lost, the entry Whk is increased by 1
with integer entries such that every dot product of a row
and Wkh is decreased by 1.
with itself is even, while every dot product of two dif-
ferent rows is odd? Prove that at the end of the tournament, det(T + iW ) is
a non-negative integer divisible by 22010 .
A5 Let F : R2 → R and g : R → R be twice continuously
differentiable functions with the following properties: B5 Let a1 , a2 , . . . be real numbers. Suppose that there is a
constant A such that for all n,
– F(u, u) = 0 for every u ∈ R;
!2
n
– for every x ∈ R, g(x) > 0 and x2 g(x) ≤ 1; 1
Z ∞
∑ 2
dx ≤ An.
– for every (u, v) ∈ R2 , the vector ∇F(u, v) is either −∞ i=1 1 + (x − ai )
0 or parallel to the vector hg(u), −g(v)i.
Prove there is a constant B > 0 such that for all n,
Prove that there exists a constant C such that for every
n
n ≥ 2 and any x1 , . . . , xn+1 ∈ R, we have
∑ (1 + (ai − a j )2 ) ≥ Bn3 .
C i, j=1
min |F(xi , x j )| ≤ .
i6= j n
B6 Let p be an odd prime. Show that for at least (p + 1)/2
A6 Let G be an abelian group with n elements, and let values of n in {0, 1, 2, . . . , p − 1},
p−1
{g1 = e, g2 , . . . , gk } $ G
∑ k!nk is not divisible by p.
k=0
be a (not necessarily minimal) set of distinct generators
of G. A special die, which randomly selects one of the
elements g1 , g2 , ..., gk with equal probability, is rolled m
times and the selected elements are multiplied to pro-
duce an element g ∈ G. Prove that there exists a real
number b ∈ (0, 1) such that
, Solutions to the 72nd William Lowell Putnam Mathematical Competition
Saturday, December 3, 2011
Kiran Kedlaya and Lenny Ng
bj B
A1 We claim that the set of points with 0 ≤ x ≤ 2011 and Now if (b j ) is bounded above by B, then b j +2 ≤ B+2
0 ≤ y ≤ 2011 that cannot be the last point of a growing B m
for all j, and so 3/2 > Sm ≥ 3/2(1 − ( B+2 ) ). Since
spiral are as follows: (0, y) for 0 ≤ y ≤ 2011; (x, 0) and B
(x, 1) for 1 ≤ x ≤ 2011; (x, 2) for 2 ≤ x ≤ 2011; and B+2 < 1, it follows that the sequence (Sm ) converges to
(x, 3) for 3 ≤ x ≤ 2011. This gives a total of S = 3/2.
A3 We claim that (c, L) = (−1, 2/π) works. Write f (r) =
2012 + 2011 + 2011 + 2010 + 2009 = 10053 R π/2 r
0 x sin x dx. Then
excluded points.
(π/2)r+1
Z π/2
The complement of this set is the set of (x, y) with 0 < f (r) < xr dx =
x < y, along with (x, y) with x ≥ y ≥ 4. Clearly the 0 r+1
former set is achievable as P2 in a growing spiral, while while since sin x ≥ 2x/π for x ≤ π/2,
a point (x, y) in the latter set is P6 in a growing spiral
with successive lengths 1, 2, 3, x + 1, x + 2, and x + y − Z π/2 r+1
2x (π/2)r+1
1. f (r) > dx = .
0 π r+2
We now need to rule out the other cases. Write x1 <
y1 < x2 < y2 < . . . for the lengths of the line segments It follows that
in the spiral in order, so that P1 = (x1 , 0), P2 = (x1 , y1 ), r+1
P3 = (x1 − x2 , y1 ), and so forth. Any point beyond P0 2
lim r f (r) = 1,
has x-coordinate of the form x1 − x2 + · · · + (−1)n−1 xn r→∞ π
for n ≥ 1; if n is odd, we can write this as x1 + (−x2 +
whence
x3 ) + · · · + (−xn−1 + xn ) > 0, while if n is even, we can
write this as (x1 − x2 ) + · · · + (xn−1 − xn ) < 0. Thus no f (r) r(2/π)r+1 f (r) 2(r + 1) 2
point beyond P0 can have x-coordinate 0, and we have lim = lim · = .
r→∞ f (r + 1) r→∞ (r + 1)(2/π)r+2 f (r + 1) πr π
ruled out (0, y) for 0 ≤ y ≤ 2011.
Next we claim that any point beyond P3 must have Now by integration by parts, we have
y-coordinate either negative or ≥ 4. Indeed, each
such point has y-coordinate of the form y1 − y2 + · · · + Z π/2
1
Z π/2
f (r + 1)
(−1)n−1 yn for n ≥ 2, which we can write as (y1 − y2 ) + xr cos x dx = xr+1 sin x dx = .
0 r+1 0 r+1
· · · + (yn−1 − yn ) < 0 if n is even, and
Thus setting c = −1 in the given limit yields
y1 + (−y2 + y3 ) + · · · + (−yn−1 + yn ) ≥ y1 + 2 ≥ 4
(r + 1) f (r) 2
if n ≥ 3 is odd. Thus to rule out the rest of the forbidden lim = ,
r→∞ r f (r + 1) π
points, it suffices to check that they cannot be P2 or P3
for any growing spiral. But none of them can be P3 = as desired.
(x1 − x2 , y1 ) since x1 − x2 < 0, and none of them can
be P2 = (x1 , y1 ) since they all have y-coordinate at most A4 The answer is n odd. Let I denote the n × n identity
equal to their x-coordinate. matrix, and let A denote the n × n matrix all of whose
entries are 1. If n is odd, then the matrix A − I satisfies
A2 For m ≥ 1, write the conditions of the problem: the dot product of any
row with itself is n − 1, and the dot product of any two
3 b1 · · · bm distinct rows is n − 2.
Sm = 1− .
2 (b1 + 2) · · · (bm + 2) Conversely, suppose n is even, and suppose that the ma-
trix M satisfied the conditions of the problem. Consider
Then S1 = 1 = 1/a1 and a quick calculation yields
all matrices and vectors mod 2. Since the dot product
b1 · · · bm−1 1 of a row with itself is equal mod 2 to the sum of the en-
Sm − Sm−1 = = tries of the row, we have Mv = 0 where v is the vector
(b2 + 2) · · · (bm + 2) a1 · · · am
(1, 1, . . . , 1), and so M is singular. On the other hand,
for m ≥ 2, since a j = (b j + 2)/b j−1 for j ≥ 2. It follows MM T = A − I; since
that Sm = ∑m n=1 1/(a1 · · · an ).
(A − I)2 = A2 − 2A + I = (n − 2)A + I = I,
we have (det M)2 = det(A − I) = 1 and det M = 1, con-
tradicting the fact that M is singular.
