The 70th William Lowell Putnam Mathematical Competition
Saturday, December 5, 2009
A1 Let f be a real-valued function on the plane such that for B1 Show that every positive rational number can be written
every square ABCD in the plane, f (A) + f (B) + f (C) + as a quotient of products of factorials of (not necessarily
f (D) = 0. Does it follow that f (P) = 0 for all points P distinct) primes. For example,
in the plane?
10 2! · 5!
A2 Functions f , g, h are differentiable on some open inter- = .
9 3! · 3! · 3!
val around 0 and satisfy the equations and initial condi-
tions
B2 A game involves jumping to the right on the real number
1 line. If a and b are real numbers and b > a, the cost of
f 0 = 2 f 2 gh + , f (0) = 1, jumping from a to b is b3 − ab2 . For what real numbers
gh
4 c can one travel from 0 to 1 in a finite number of jumps
0 2
g = f g h + , g(0) = 1, with total cost exactly c?
fh
1 B3 Call a subset S of {1, 2, . . . , n} mediocre if it has the fol-
h0 = 3 f gh2 + , h(0) = 1.
fg lowing property: Whenever a and b are elements of S
whose average is an integer, that average is also an ele-
Find an explicit formula for f (x), valid in some open ment of S. Let A(n) be the number of mediocre subsets
interval around 0. of {1, 2, . . . , n}. [For instance, every subset of {1, 2, 3}
except {1, 3} is mediocre, so A(3) = 7.] Find all posi-
A3 Let dn be the determinant of the n × n matrix whose tive integers n such that A(n + 2) − 2A(n + 1) + A(n) =
entries, from left to right and then from top to bottom, 1.
are cos 1, cos 2, . . . , cos n2 . (For example,
B4 Say that a polynomial with real coefficients in two vari-
cos 1 cos 2 cos 3 ables, x, y, is balanced if the average value of the poly-
d3 = cos 4 cos 5 cos 6 . nomial on each circle centered at the origin is 0. The
cos 7 cos 8 cos 9 balanced polynomials of degree at most 2009 form a
vector space V over R. Find the dimension of V .
The argument of cos is always in radians, not degrees.)
Evaluate limn→∞ dn . B5 Let f : (1, ∞) → R be a differentiable function such that
A4 Let S be a set of rational numbers such that x2 − f (x)2
f 0 (x) = for all x > 1.
(a) 0 ∈ S; x2 ( f (x)2 + 1)
(b) If x ∈ S then x + 1 ∈ S and x − 1 ∈ S; and Prove that limx→∞ f (x) = ∞.
1
(c) If x ∈ S and x 6∈ {0, 1}, then x(x−1) ∈ S.
B6 Prove that for every positive integer n, there is a se-
Must S contain all rational numbers? quence of integers a0 , a1 , . . . , a2009 with a0 = 0 and
a2009 = n such that each term after a0 is either an ear-
A5 Is there a finite abelian group G such that the product of lier term plus 2k for some nonnegative integer k, or of
the orders of all its elements is 22009 ? the form b mod c for some earlier positive terms b and c.
[Here b mod c denotes the remainder when b is divided
A6 Let f : [0, 1]2 → R be a continuous function on the by c, so 0 ≤ (b mod c) < c.]
closed unit square such that ∂∂ xf and ∂∂ yf exist and are
continuous on the interior (0, 1)2 . Let a = 01 f (0, y) dy,
R
b = 01 f (1, y) dy, c = 01 f (x, 0) dx, d = 01 f (x, 1) dx.
R R R
Prove or disprove: There must be a point (x0 , y0 ) in
(0, 1)2 such that
∂f ∂f
(x0 , y0 ) = b − a and (x0 , y0 ) = d − c.
∂x ∂y
, Solutions to the 70th William Lowell Putnam Mathematical Competition
Saturday, December 5, 2009
Kiran Kedlaya and Lenny Ng
A–1 Yes, it does follow. Let P be any point in the plane. Let A–3 The limit is 0; we will show this by checking that
ABCD be any square with center P. Let E, F, G, H be dn = 0 for all n ≥ 3. Starting from the given matrix,
the midpoints of the segments AB, BC,CD, DA, respec- add the third column to the first column; this does not
tively. The function f must satisfy the equations change the determinant. However, thanks to the identity
cos x+cos y = 2 cos x+y x−y
2 cos 2 , the resulting matrix has
0= f (A) + f (B) + f (C) + f (D) the form
0= f (E) + f (F) + f (G) + f (H)
2 cos 2 cos 1 cos 2 ···
0= f (A) + f (E) + f (P) + f (H) 2 cos(n + 2) cos 1 cos(n + 2) · · ·
0= f (B) + f (F) + f (P) + f (E) 2 cos(2n + 2) cos 1 2 cos(2n + 2) · · ·
0= f (C) + f (G) + f (P) + f (F) .. .. ..
. . .
0= f (D) + f (H) + f (P) + f (G).
with the first column being a multiple of the second.
If we add the last four equations, then subtract the first Hence dn = 0.
equation and twice the second equation, we obtain 0 = Remark. Another way to draw the same conclu-
4 f (P), whence f (P) = 0. sion is to observe that the given matrix is the sum of
Remark. Problem 1 of the 1996 Romanian IMO team the two rank 1 matrices A jk = cos( j − 1)n cos k and
selection exam asks the same question with squares re- B jk = − sin( j − 1)n sin k, and so has rank at most 2.
placed by regular polygons of any (fixed) number of One can also use the matrices A jk = ei(( j−1)n+k) , B jk =
vertices. e−i( j−1)n+k .
A–2 Multiplying the first differential equation by gh, the sec- A–4 The answer is no; indeed, S = Q \ {n + 2/5 | n ∈ Z} sat-
ond by f h, and the third by f g, and summing gives isfies the given conditions. Clearly S satisfies (a) and
(b); we need only check that it satisfies (c). It suffices
( f gh)0 = 6( f gh)2 + 6.
to show that if x = p/q is a fraction with (p, q) = 1 and
Write k(x) = f (x)g(x)h(x); then k0 = 6k2 +6 and k(0) = p > 0, then we cannot have 1/(x(x − 1)) = n + 2/5 for
1. One solution for this differential equation with this an integer n. Suppose otherwise; then
initial condition is k(x) = tan(6x + π/4); by standard
(5n + 2)p(p − q) = 5q2 .
uniqueness, this must necessarily hold for x in some
open interval around 0. Now the first given equation Since p and q are relatively prime, and p divides
becomes 5q2 , we must have p | 5, so p = 1 or p = 5. On the
other hand, p − q and q are also relatively prime, so
f 0 / f = 2k(x) + 1/k(x)
p − q divides 5 as well, and p − q must be ±1 or
= 2 tan(6x + π/4) + cot(6x + π/4); ±5. This leads to eight possibilities for (p, q): (1, 0),
(5, 0), (5, 10), (1, −4), (1, 2), (1, 6), (5, 4), (5, 6). The
integrating both sides gives first three are impossible, while the final five lead to
−2 ln cos(6x + π/4) + ln sin(6x + π/4) 5n + 2 = 16, −20, −36, 16, −36 respectively, none of
ln( f (x)) = + c, which holds for integral n.
6
Remark. More generally, no rational number of the
sin(6x+π/4) 1/6 form m/n, where m, n are relatively prime and neither
whence f (x) = ec cos 2 (6x+π/4) . Substituting
of ±m is a quadratic residue mod n, need be in S. If
f (0) = 1 gives ec = 2−1/12 and thus f (x) = x = p/q is in lowest terms and 1/(x(x − 1)) = m/n + k
sin(6x+π/4) 1/6 for some integer k, then p(p − q) is relatively prime to
2−1/12 cos 2 (6x+π/4) .
q2 ; q2 /(p(p − q)) = (m + kn)/n then implies that m +
Remark. The answer can be put in alternate forms kn = ±q2 and so ±m must be a quadratic residue mod
using trigonometric identities. One particularly simple n.
one is
A–5 No, there is no such group. By the structure theorem
f (x) = (sec 12x)1/12 (sec 12x + tan 12x)1/4 . for finitely generated abelian groups, G can be written
as a product of cyclic groups. If any of these factors has
odd order, then G has an element of odd order, so the
Saturday, December 5, 2009
A1 Let f be a real-valued function on the plane such that for B1 Show that every positive rational number can be written
every square ABCD in the plane, f (A) + f (B) + f (C) + as a quotient of products of factorials of (not necessarily
f (D) = 0. Does it follow that f (P) = 0 for all points P distinct) primes. For example,
in the plane?
10 2! · 5!
A2 Functions f , g, h are differentiable on some open inter- = .
9 3! · 3! · 3!
val around 0 and satisfy the equations and initial condi-
tions
B2 A game involves jumping to the right on the real number
1 line. If a and b are real numbers and b > a, the cost of
f 0 = 2 f 2 gh + , f (0) = 1, jumping from a to b is b3 − ab2 . For what real numbers
gh
4 c can one travel from 0 to 1 in a finite number of jumps
0 2
g = f g h + , g(0) = 1, with total cost exactly c?
fh
1 B3 Call a subset S of {1, 2, . . . , n} mediocre if it has the fol-
h0 = 3 f gh2 + , h(0) = 1.
fg lowing property: Whenever a and b are elements of S
whose average is an integer, that average is also an ele-
Find an explicit formula for f (x), valid in some open ment of S. Let A(n) be the number of mediocre subsets
interval around 0. of {1, 2, . . . , n}. [For instance, every subset of {1, 2, 3}
except {1, 3} is mediocre, so A(3) = 7.] Find all posi-
A3 Let dn be the determinant of the n × n matrix whose tive integers n such that A(n + 2) − 2A(n + 1) + A(n) =
entries, from left to right and then from top to bottom, 1.
are cos 1, cos 2, . . . , cos n2 . (For example,
B4 Say that a polynomial with real coefficients in two vari-
cos 1 cos 2 cos 3 ables, x, y, is balanced if the average value of the poly-
d3 = cos 4 cos 5 cos 6 . nomial on each circle centered at the origin is 0. The
cos 7 cos 8 cos 9 balanced polynomials of degree at most 2009 form a
vector space V over R. Find the dimension of V .
The argument of cos is always in radians, not degrees.)
Evaluate limn→∞ dn . B5 Let f : (1, ∞) → R be a differentiable function such that
A4 Let S be a set of rational numbers such that x2 − f (x)2
f 0 (x) = for all x > 1.
(a) 0 ∈ S; x2 ( f (x)2 + 1)
(b) If x ∈ S then x + 1 ∈ S and x − 1 ∈ S; and Prove that limx→∞ f (x) = ∞.
1
(c) If x ∈ S and x 6∈ {0, 1}, then x(x−1) ∈ S.
B6 Prove that for every positive integer n, there is a se-
Must S contain all rational numbers? quence of integers a0 , a1 , . . . , a2009 with a0 = 0 and
a2009 = n such that each term after a0 is either an ear-
A5 Is there a finite abelian group G such that the product of lier term plus 2k for some nonnegative integer k, or of
the orders of all its elements is 22009 ? the form b mod c for some earlier positive terms b and c.
[Here b mod c denotes the remainder when b is divided
A6 Let f : [0, 1]2 → R be a continuous function on the by c, so 0 ≤ (b mod c) < c.]
closed unit square such that ∂∂ xf and ∂∂ yf exist and are
continuous on the interior (0, 1)2 . Let a = 01 f (0, y) dy,
R
b = 01 f (1, y) dy, c = 01 f (x, 0) dx, d = 01 f (x, 1) dx.
R R R
Prove or disprove: There must be a point (x0 , y0 ) in
(0, 1)2 such that
∂f ∂f
(x0 , y0 ) = b − a and (x0 , y0 ) = d − c.
∂x ∂y
, Solutions to the 70th William Lowell Putnam Mathematical Competition
Saturday, December 5, 2009
Kiran Kedlaya and Lenny Ng
A–1 Yes, it does follow. Let P be any point in the plane. Let A–3 The limit is 0; we will show this by checking that
ABCD be any square with center P. Let E, F, G, H be dn = 0 for all n ≥ 3. Starting from the given matrix,
the midpoints of the segments AB, BC,CD, DA, respec- add the third column to the first column; this does not
tively. The function f must satisfy the equations change the determinant. However, thanks to the identity
cos x+cos y = 2 cos x+y x−y
2 cos 2 , the resulting matrix has
0= f (A) + f (B) + f (C) + f (D) the form
0= f (E) + f (F) + f (G) + f (H)
2 cos 2 cos 1 cos 2 ···
0= f (A) + f (E) + f (P) + f (H) 2 cos(n + 2) cos 1 cos(n + 2) · · ·
0= f (B) + f (F) + f (P) + f (E) 2 cos(2n + 2) cos 1 2 cos(2n + 2) · · ·
0= f (C) + f (G) + f (P) + f (F) .. .. ..
. . .
0= f (D) + f (H) + f (P) + f (G).
with the first column being a multiple of the second.
If we add the last four equations, then subtract the first Hence dn = 0.
equation and twice the second equation, we obtain 0 = Remark. Another way to draw the same conclu-
4 f (P), whence f (P) = 0. sion is to observe that the given matrix is the sum of
Remark. Problem 1 of the 1996 Romanian IMO team the two rank 1 matrices A jk = cos( j − 1)n cos k and
selection exam asks the same question with squares re- B jk = − sin( j − 1)n sin k, and so has rank at most 2.
placed by regular polygons of any (fixed) number of One can also use the matrices A jk = ei(( j−1)n+k) , B jk =
vertices. e−i( j−1)n+k .
A–2 Multiplying the first differential equation by gh, the sec- A–4 The answer is no; indeed, S = Q \ {n + 2/5 | n ∈ Z} sat-
ond by f h, and the third by f g, and summing gives isfies the given conditions. Clearly S satisfies (a) and
(b); we need only check that it satisfies (c). It suffices
( f gh)0 = 6( f gh)2 + 6.
to show that if x = p/q is a fraction with (p, q) = 1 and
Write k(x) = f (x)g(x)h(x); then k0 = 6k2 +6 and k(0) = p > 0, then we cannot have 1/(x(x − 1)) = n + 2/5 for
1. One solution for this differential equation with this an integer n. Suppose otherwise; then
initial condition is k(x) = tan(6x + π/4); by standard
(5n + 2)p(p − q) = 5q2 .
uniqueness, this must necessarily hold for x in some
open interval around 0. Now the first given equation Since p and q are relatively prime, and p divides
becomes 5q2 , we must have p | 5, so p = 1 or p = 5. On the
other hand, p − q and q are also relatively prime, so
f 0 / f = 2k(x) + 1/k(x)
p − q divides 5 as well, and p − q must be ±1 or
= 2 tan(6x + π/4) + cot(6x + π/4); ±5. This leads to eight possibilities for (p, q): (1, 0),
(5, 0), (5, 10), (1, −4), (1, 2), (1, 6), (5, 4), (5, 6). The
integrating both sides gives first three are impossible, while the final five lead to
−2 ln cos(6x + π/4) + ln sin(6x + π/4) 5n + 2 = 16, −20, −36, 16, −36 respectively, none of
ln( f (x)) = + c, which holds for integral n.
6
Remark. More generally, no rational number of the
sin(6x+π/4) 1/6 form m/n, where m, n are relatively prime and neither
whence f (x) = ec cos 2 (6x+π/4) . Substituting
of ±m is a quadratic residue mod n, need be in S. If
f (0) = 1 gives ec = 2−1/12 and thus f (x) = x = p/q is in lowest terms and 1/(x(x − 1)) = m/n + k
sin(6x+π/4) 1/6 for some integer k, then p(p − q) is relatively prime to
2−1/12 cos 2 (6x+π/4) .
q2 ; q2 /(p(p − q)) = (m + kn)/n then implies that m +
Remark. The answer can be put in alternate forms kn = ±q2 and so ±m must be a quadratic residue mod
using trigonometric identities. One particularly simple n.
one is
A–5 No, there is no such group. By the structure theorem
f (x) = (sec 12x)1/12 (sec 12x + tan 12x)1/4 . for finitely generated abelian groups, G can be written
as a product of cyclic groups. If any of these factors has
odd order, then G has an element of odd order, so the
