The 71st William Lowell Putnam Mathematical Competition
Saturday, December 4, 2010
A1 Given a positive integer n, what is the largest k such that B1 Is there an infinite sequence of real numbers
the numbers 1, 2, . . . , n can be put into k boxes so that a1 , a2 , a3 , . . . such that
the sum of the numbers in each box is the same? [When
n = 8, the example {1, 2, 3, 6}, {4, 8}, {5, 7} shows that am m m
1 + a2 + a3 + · · · = m
the largest k is at least 3.]
for every positive integer m?
A2 Find all differentiable functions f : R → R such that
B2 Given that A, B, and C are noncollinear points in the
f (x + n) − f (x) plane with integer coordinates such that the distances
f 0 (x) = AB, AC, and BC are integers, what is the smallest possi-
n
ble value of AB?
for all real numbers x and all positive integers n.
B3 There are 2010 boxes labeled B1 , B2 , . . . , B2010 , and
A3 Suppose that the function h : R2 → R has continuous 2010n balls have been distributed among them, for
partial derivatives and satisfies the equation some positive integer n. You may redistribute the balls
by a sequence of moves, each of which consists of
∂h ∂h choosing an i and moving exactly i balls from box Bi
h(x, y) = a (x, y) + b (x, y)
∂x ∂y into any one other box. For which values of n is it possi-
ble to reach the distribution with exactly n balls in each
for some constants a, b. Prove that if there is a constant
box, regardless of the initial distribution of balls?
M such that |h(x, y)| ≤ M for all (x, y) ∈ R2 , then h is
identically zero. B4 Find all pairs of polynomials p(x) and q(x) with real
coefficients for which
A4 Prove that for each positive integer n, the number
10n n
1010 + 1010 + 10n − 1 is not prime. p(x)q(x + 1) − p(x + 1)q(x) = 1.
A5 Let G be a group, with operation ∗. Suppose that
B5 Is there a strictly increasing function f : R → R such
(i) G is a subset of R3 (but ∗ need not be related to that f 0 (x) = f ( f (x)) for all x?
addition of vectors);
B6 Let A be an n × n matrix of real numbers for some n ≥
(ii) For each a, b ∈ G, either a × b = a ∗ b or a × b = 0 1. For each positive integer k, let A[k] be the matrix
(or both), where × is the usual cross product in obtained by raising each entry to the kth power. Show
R3 . that if Ak = A[k] for k = 1, 2, . . . , n + 1, then Ak = A[k] for
Prove that a × b = 0 for all a, b ∈ G. all k ≥ 1.
A6 Let f : [0, ∞) → R be a strictly decreasing continu-
ous function such that limx→∞ f (x) = 0. Prove that
R ∞ f (x)− f (x+1)
0 f (x) dx diverges.
, Solutions to the 71st William Lowell Putnam Mathematical Competition
Saturday, December 4, 2010
Kiran Kedlaya and Lenny Ng
A–1 The largest such k is b n+1 n
2 c = d 2 e. For n even, this value Since 10n ≥ n ≥ 2m ≥ m + 1, 10n is divisible by 2n and
n n
is achieved by the partition hence by 2m+1 , and similarly 1010 is divisible by 210
and hence by 2 m+1 . It follows that
{1, n}, {2, n − 1}, . . . ;
m
N ≡ 1 + 1 + (−1) + (−1) ≡ 0 (mod 102 + 1).
for n odd, it is achieved by the partition
n m
Since N ≥ 1010 > 10n + 1 ≥ 102 + 1, it follows that N
{n}, {1, n − 1}, {2, n − 2}, . . . . is composite.
One way to see that this is optimal is to note that the A–5 We start with three lemmas.
common sum can never be less than n, since n itself
belongs to one of the boxes. This implies that k ≤ (1 + Lemma 1. If x, y ∈ G are nonzero orthogonal vectors, then
· · · + n)/n = (n + 1)/2. Another argument is that if k > x ∗ x is parallel to y.
(n + 1)/2, then there would have to be two boxes with
one number each (by the pigeonhole principle), but such Proof. Put z = x × y 6= 0, so that x, y, and z = x ∗ y are nonzero
boxes could not have the same sum. and mutually orthogonal. Then w = x × z 6= 0, so w = x ∗ z is
nonzero and orthogonal to x and z. However, if (x∗x)×y 6= 0,
Remark. A much subtler question would be to find
then w = x∗(x∗y) = (x∗x)∗y = (x∗x)×y is also orthogonal
the smallest k (as a function of n) for which no such
to y, a contradiction.
arrangement exists.
Lemma 2. If x ∈ G is nonzero, and there exists y ∈ G nonzero
A–2 The only such functions are those of the form f (x) =
and orthogonal to x, then x ∗ x = 0.
cx + d for some real numbers c, d (for which the prop-
erty is obviously satisfied). To see this, suppose that f
Proof. Lemma 1 implies that x ∗ x is parallel to both y and
has the desired property. Then for any x ∈ R,
x × y, so it must be zero.
2 f 0 (x) = f (x + 2) − f (x) Lemma 3. If x, y ∈ G commute, then x × y = 0.
= ( f (x + 2) − f (x + 1)) + ( f (x + 1) − f (x))
= f 0 (x + 1) + f 0 (x). Proof. If x × y 6= 0, then y × x is nonzero and distinct from
x×y. Consequently, x∗y = x×y and y∗x = y×x 6= x∗y.
Consequently, f 0 (x + 1) = f 0 (x).
We proceed now to the proof. Assume by way of con-
Define the function g : R → R by g(x) = f (x + 1) −
tradiction that there exist a, b ∈ G with a × b 6= 0. Put
f (x), and put c = g(0), d = f (0). For all x ∈ R,
c = a × b = a ∗ b, so that a, b, c are nonzero and lin-
g0 (x) = f 0 (x + 1) − f 0 (x) = 0, so g(x) = c identically,
early independent. Let e be the identity element of G.
and f 0 (x) = f (x+1)− f (x) = g(x) = c, so f (x) = cx+d
Since e commutes with a, b, c, by Lemma 3 we have
identically as desired.
e×a = e×b = e×c = 0. Since a, b, c span R3 , e×x = 0
A–3 If a = b = 0, then the desired result holds trivially, so for all x ∈ R3 , so e = 0.
we assume that at least one of a, b is nonzero. Pick Since b, c, and b × c = b ∗ c are nonzero and mutually
any point (a0 , b0 ) ∈ R2 , and let L be the line given by orthogonal, Lemma 2 implies
the parametric equation L(t) = (a0 , b0 ) + (a, b)t for t ∈
R. By the chain rule and the given equation, we have b ∗ b = c ∗ c = (b ∗ c) ∗ (b ∗ c) = 0 = e.
d
dt (h ◦ L) = h ◦ L. If we write f = h ◦ L : R → R, then
f 0 (t) = f (t) for all t. It follows that f (t) = Cet for some Hence b ∗ c = c ∗ b, contradicting Lemma 3 because b ×
constant C. Since | f (t)| ≤ M for all t, we must have c 6= 0. The desired result follows.
C = 0. It follows that h(a0 , b0 ) = 0; since (a0 , b0 ) was
an arbitrary point, h is identically 0 over all of R2 . A–6 First solution. Note that the hypotheses on f imply
that f (x) > 0 for all x ∈ [0, +∞), so the integrand is a
A–4 Put continuous function of f and the integral makes sense.
10n n
Rewrite the integral as
N = 1010 + 1010 + 10n − 1. Z ∞
f (x + 1)
1− dx,
Write n = 2m k with m a nonnegative integer and k a 0 f (x)
positive odd integer. For any nonnegative integer j,
mj m
102 ≡ (−1) j (mod 102 + 1).
Saturday, December 4, 2010
A1 Given a positive integer n, what is the largest k such that B1 Is there an infinite sequence of real numbers
the numbers 1, 2, . . . , n can be put into k boxes so that a1 , a2 , a3 , . . . such that
the sum of the numbers in each box is the same? [When
n = 8, the example {1, 2, 3, 6}, {4, 8}, {5, 7} shows that am m m
1 + a2 + a3 + · · · = m
the largest k is at least 3.]
for every positive integer m?
A2 Find all differentiable functions f : R → R such that
B2 Given that A, B, and C are noncollinear points in the
f (x + n) − f (x) plane with integer coordinates such that the distances
f 0 (x) = AB, AC, and BC are integers, what is the smallest possi-
n
ble value of AB?
for all real numbers x and all positive integers n.
B3 There are 2010 boxes labeled B1 , B2 , . . . , B2010 , and
A3 Suppose that the function h : R2 → R has continuous 2010n balls have been distributed among them, for
partial derivatives and satisfies the equation some positive integer n. You may redistribute the balls
by a sequence of moves, each of which consists of
∂h ∂h choosing an i and moving exactly i balls from box Bi
h(x, y) = a (x, y) + b (x, y)
∂x ∂y into any one other box. For which values of n is it possi-
ble to reach the distribution with exactly n balls in each
for some constants a, b. Prove that if there is a constant
box, regardless of the initial distribution of balls?
M such that |h(x, y)| ≤ M for all (x, y) ∈ R2 , then h is
identically zero. B4 Find all pairs of polynomials p(x) and q(x) with real
coefficients for which
A4 Prove that for each positive integer n, the number
10n n
1010 + 1010 + 10n − 1 is not prime. p(x)q(x + 1) − p(x + 1)q(x) = 1.
A5 Let G be a group, with operation ∗. Suppose that
B5 Is there a strictly increasing function f : R → R such
(i) G is a subset of R3 (but ∗ need not be related to that f 0 (x) = f ( f (x)) for all x?
addition of vectors);
B6 Let A be an n × n matrix of real numbers for some n ≥
(ii) For each a, b ∈ G, either a × b = a ∗ b or a × b = 0 1. For each positive integer k, let A[k] be the matrix
(or both), where × is the usual cross product in obtained by raising each entry to the kth power. Show
R3 . that if Ak = A[k] for k = 1, 2, . . . , n + 1, then Ak = A[k] for
Prove that a × b = 0 for all a, b ∈ G. all k ≥ 1.
A6 Let f : [0, ∞) → R be a strictly decreasing continu-
ous function such that limx→∞ f (x) = 0. Prove that
R ∞ f (x)− f (x+1)
0 f (x) dx diverges.
, Solutions to the 71st William Lowell Putnam Mathematical Competition
Saturday, December 4, 2010
Kiran Kedlaya and Lenny Ng
A–1 The largest such k is b n+1 n
2 c = d 2 e. For n even, this value Since 10n ≥ n ≥ 2m ≥ m + 1, 10n is divisible by 2n and
n n
is achieved by the partition hence by 2m+1 , and similarly 1010 is divisible by 210
and hence by 2 m+1 . It follows that
{1, n}, {2, n − 1}, . . . ;
m
N ≡ 1 + 1 + (−1) + (−1) ≡ 0 (mod 102 + 1).
for n odd, it is achieved by the partition
n m
Since N ≥ 1010 > 10n + 1 ≥ 102 + 1, it follows that N
{n}, {1, n − 1}, {2, n − 2}, . . . . is composite.
One way to see that this is optimal is to note that the A–5 We start with three lemmas.
common sum can never be less than n, since n itself
belongs to one of the boxes. This implies that k ≤ (1 + Lemma 1. If x, y ∈ G are nonzero orthogonal vectors, then
· · · + n)/n = (n + 1)/2. Another argument is that if k > x ∗ x is parallel to y.
(n + 1)/2, then there would have to be two boxes with
one number each (by the pigeonhole principle), but such Proof. Put z = x × y 6= 0, so that x, y, and z = x ∗ y are nonzero
boxes could not have the same sum. and mutually orthogonal. Then w = x × z 6= 0, so w = x ∗ z is
nonzero and orthogonal to x and z. However, if (x∗x)×y 6= 0,
Remark. A much subtler question would be to find
then w = x∗(x∗y) = (x∗x)∗y = (x∗x)×y is also orthogonal
the smallest k (as a function of n) for which no such
to y, a contradiction.
arrangement exists.
Lemma 2. If x ∈ G is nonzero, and there exists y ∈ G nonzero
A–2 The only such functions are those of the form f (x) =
and orthogonal to x, then x ∗ x = 0.
cx + d for some real numbers c, d (for which the prop-
erty is obviously satisfied). To see this, suppose that f
Proof. Lemma 1 implies that x ∗ x is parallel to both y and
has the desired property. Then for any x ∈ R,
x × y, so it must be zero.
2 f 0 (x) = f (x + 2) − f (x) Lemma 3. If x, y ∈ G commute, then x × y = 0.
= ( f (x + 2) − f (x + 1)) + ( f (x + 1) − f (x))
= f 0 (x + 1) + f 0 (x). Proof. If x × y 6= 0, then y × x is nonzero and distinct from
x×y. Consequently, x∗y = x×y and y∗x = y×x 6= x∗y.
Consequently, f 0 (x + 1) = f 0 (x).
We proceed now to the proof. Assume by way of con-
Define the function g : R → R by g(x) = f (x + 1) −
tradiction that there exist a, b ∈ G with a × b 6= 0. Put
f (x), and put c = g(0), d = f (0). For all x ∈ R,
c = a × b = a ∗ b, so that a, b, c are nonzero and lin-
g0 (x) = f 0 (x + 1) − f 0 (x) = 0, so g(x) = c identically,
early independent. Let e be the identity element of G.
and f 0 (x) = f (x+1)− f (x) = g(x) = c, so f (x) = cx+d
Since e commutes with a, b, c, by Lemma 3 we have
identically as desired.
e×a = e×b = e×c = 0. Since a, b, c span R3 , e×x = 0
A–3 If a = b = 0, then the desired result holds trivially, so for all x ∈ R3 , so e = 0.
we assume that at least one of a, b is nonzero. Pick Since b, c, and b × c = b ∗ c are nonzero and mutually
any point (a0 , b0 ) ∈ R2 , and let L be the line given by orthogonal, Lemma 2 implies
the parametric equation L(t) = (a0 , b0 ) + (a, b)t for t ∈
R. By the chain rule and the given equation, we have b ∗ b = c ∗ c = (b ∗ c) ∗ (b ∗ c) = 0 = e.
d
dt (h ◦ L) = h ◦ L. If we write f = h ◦ L : R → R, then
f 0 (t) = f (t) for all t. It follows that f (t) = Cet for some Hence b ∗ c = c ∗ b, contradicting Lemma 3 because b ×
constant C. Since | f (t)| ≤ M for all t, we must have c 6= 0. The desired result follows.
C = 0. It follows that h(a0 , b0 ) = 0; since (a0 , b0 ) was
an arbitrary point, h is identically 0 over all of R2 . A–6 First solution. Note that the hypotheses on f imply
that f (x) > 0 for all x ∈ [0, +∞), so the integrand is a
A–4 Put continuous function of f and the integral makes sense.
10n n
Rewrite the integral as
N = 1010 + 1010 + 10n − 1. Z ∞
f (x + 1)
1− dx,
Write n = 2m k with m a nonnegative integer and k a 0 f (x)
positive odd integer. For any nonnegative integer j,
mj m
102 ≡ (−1) j (mod 102 + 1).
