The 73rd William Lowell Putnam Mathematical Competition
Saturday, December 1, 2012
A1 Let d1 , d2 , . . . , d12 be real numbers in the open interval (i) The functions f1 (x) = ex − 1 and f2 (x) = ln(x + 1)
(1, 12). Show that there exist distinct indices i, j, k such are in S;
that di , d j , dk are the side lengths of an acute triangle. (ii) If f (x) and g(x) are in S, the functions f (x) + g(x)
A2 Let ∗ be a commutative and associative binary operation and f (g(x)) are in S;
on a set S. Assume that for every x and y in S, there (iii) If f (x) and g(x) are in S and f (x) ≥ g(x) for all
exists z in S such that x ∗ z = y. (This z may depend on x ≥ 0, then the function f (x) − g(x) is in S.
x and y.) Show that if a, b, c are in S and a ∗ c = b ∗ c,
then a = b. Prove that if f (x) and g(x) are in S, then the function
f (x)g(x) is also in S.
A3 Let f : [−1, 1] → R be a continuous function such that B2 Let P be a given (non-degenerate) polyhedron. Prove
2
2 that there is a constant c(P) > 0 with the following
(i) f (x) = 2−x
2 f x
2−x2
for every x in [−1, 1], property: If a collection of n balls whose volumes sum
to V contains the entire surface of P, then n > c(P)/V 2 .
(ii) f (0) = 1, and
√f (x)
B3 A round-robin tournament of 2n teams lasted for 2n − 1
(iii) limx→1− exists and is finite.
1−x days, as follows. On each day, every team played one
game against another team, with one team winning and
Prove that f is unique, and express f (x) in closed form.
one team losing in each of the n games. Over the course
A4 Let q and r be integers with q > 0, and let A and B be of the tournament, each team played every other team
intervals on the real line. Let T be the set of all b + mq exactly once. Can one necessarily choose one winning
where b and m are integers with b in B, and let S be team from each day without choosing any team more
the set of all integers a in A such that ra is in T . Show than once?
that if the product of the lengths of A and B is less than
B4 Suppose that a0 = 1 and that an+1 = an + e−an for n =
q, then S is the intersection of A with some arithmetic
0, 1, 2, . . . . Does an − log n have a finite limit as n → ∞?
progression.
(Here log n = loge n = ln n.)
A5 Let F p denote the field of integers modulo a prime p,
B5 Prove that, for any two bounded functions g1 , g2 : R →
and let n be a positive integer. Let v be a fixed vec-
[1, ∞), there exist functions h1 , h2 : R → R such that, for
tor in Fnp , let M be an n × n matrix with entries of F p ,
every x ∈ R,
and define G : Fnp → Fnp by G(x) = v + Mx. Let G(k)
denote the k-fold composition of G with itself, that is, sup(g1 (s)x g2 (s)) = max(xh1 (t) + h2 (t)).
G(1) (x) = G(x) and G(k+1) (x) = G(G(k) (x)). Determine s∈R t∈R
all pairs p, n for which there exist v and M such that the
pn vectors G(k) (0), k = 1, 2, . . . , pn are distinct. B6 Let p be an odd prime number such that p ≡ 2 (mod 3).
Define a permutation π of the residue classes modulo p
A6 Let f (x, y) be a continuous, real-valued function on R2 . by π(x) ≡ x3 (mod p). Show that π is an even permu-
Suppose that, for every rectangular region R of area 1, tation if and only if p ≡ 3 (mod 4).
the double integral of f (x, y) over R equals 0. Must
f (x, y) be identically 0?
B1 Let S be a class of functions from [0, ∞) to [0, ∞) that
satisfies:
, Solutions to the 73rd William Lowell Putnam Mathematical Competition
Saturday, December 1, 2012
Kiran Kedlaya and Lenny Ng
A1 Without loss of generality, assume d1 ≤ d2 ≤ · · · ≤ d12 . Proof. We may assume #S ≥ 3, as otherwise S is trivially an
2 < d 2 + d 2 for some i ≤ 10, then d , d
If di+2 i i+1 i i+1 , di+2 arithmetic progression. Let a1 , a2 be the smallest and second-
are the side lengths of an acute triangle, since in this smallest elements of S, respectively, and put d = a2 − a1 . Let
case di2 < di+1
2 +d 2 and d 2 < d 2 +d 2 as well. Thus
i+2 i+1 i i+2 m be the smallest positive integer such that a1 + md ∈ / S. Sup-
we may assume di+2 2 ≥ d2 + d2 pose that there exists an integer n contained in S but not in
i i+1 for all i. But then
by induction, di2 ≥ Fi d12 for all i, where Fi is the i-th {a1 , a1 + d, . . . , a1 + (m − 1)d}, and choose the least such n.
Fibonacci number (with F1 = F2 = 1): i = 1 is clear, i = By the hypothesis applied with (a, b, c) = (a1 , a2 , n), we see
2 follows from d2 ≥ d1 , and the induction step follows that n − d also has the property, a contradiction.
from the assumed inequality. Setting i = 12 now gives
2 ≥ 144d 2 , contradicting d > 1 and d < 12.
d12 1 12
We now return to the original problem. By dividing
1
B, q, r by gcd(q, r) if necessary, we may reduce to the
Remark. A materially equivalent problem appeared on case where gcd(q, r) = 1. We may assume #S ≥ 3, as
the 2012 USA Mathematical Olympiad and USA Junior otherwise S is trivially an arithmetic progression. Let
Mathematical Olympiad. a1 , a2 , a3 be any three distinct elements of S, labeled
A2 Write d for a ∗ c = b ∗ c ∈ S. For some e ∈ S, d ∗ e = a, so that a1 < a2 < a3 , and write rai = bi + mi q with
and thus for f = c ∗ e, a ∗ f = a ∗ c ∗ e = d ∗ e = a and bi , mi ∈ Z and bi ∈ B. Note that b1 , b2 , b3 must also be
b ∗ f = b ∗ c ∗ e = d ∗ e = a. Let g ∈ S satisfy g ∗ a = b; distinct, so the differences b2 − b1 , b3 − b1 , b3 − b2 are
then b = g ∗ a = g ∗ (a ∗ f ) = (g ∗ a) ∗ f = b ∗ f = a, as all nonzero; consequently, two of them have the same
desired. sign. If bi − b j and bk − bl have the same sign, then we
must have
Remark. With slightly more work, one can show that
S forms an abelian group with the operation ∗. (ai − a j )(bk − bl ) = (bi − b j )(ak − al )
√
A3 We will prove that f (x) = 1 − x2 for √ all x ∈ [−1, 1]. because both sides are of the same sign, of absolute
Define g : (−1, 1)
√ → R by g(x) = f (x)/ 1 − x2 . Plug- value less than q, and congruent to each other modulo
2
ging f (x) = g(x) 1 − x into equation (i) and simplify- q. In other words, the points (a1 , b1 ), (a2 , b2 ), (a3 , b3 )
ing yields in R2 are collinear. It follows that a4 = a1 + a3 − a2
2 also belongs to S (by taking b4 = b1 + b3 − b2 ), so S
x satisfies the conditions of the lemma. It is therefore an
g(x) = g (1)
2 − x2 arithmetic progression.
for all x ∈ (−1, 1). Now fix x ∈ (−1, 1) and define a Reinterpretations. One can also interpret this argu-
a2n ment geometrically using cross products (suggested by
sequence {an }∞
n=1 by a1 = x and an+1 = 2−a2n
. Then Noam Elkies), or directly in terms of congruences (sug-
|2
an ∈ (−1, 1) and thus |an+1 | ≤ |an for all n. It follows gested by Karl Mahlburg).
that {|an |} is a decreasing sequence with |an | ≤ |x|n for Remark. The problem phrasing is somewhat confus-
all n, and so limn→∞ an = 0. Since g(an ) = g(x) for ing: to say that “S is the intersection of [the interval]
all n by (1) and g is continuous at 0, we conclude that A with an arithmetic progression” is the same thing as
g(x) = g(0) = f (0) = 1. This holds for all x ∈ (−1, 1) saying that “S is the empty set or an arithmetic progres-
and thus for x = ±1 as well by continuity. The result sion” unless it is implied that arithmetic progressions
follows. are necessarily infinite. Under that interpretation, how-
Remark. As pointed out by Noam Elkies, condition ever, the problem becomes false; for instance, for
(iii) is unnecessary. However, one can use it to derive
a slightly different solution by running the recursion in q = 5, r = 1, A = [1, 3], B = [0, 2],
the opposite direction.
we have
A4 We begin with an easy lemma.
T = {· · · , 0, 1, 2, 5, 6, 7, . . . }, S = {1, 2}.
Lemma. Let S be a finite set of integers with the following
property: for all a, b, c ∈ S with a ≤ b ≤ c, we also have a + A5 The pairs (p, n) with the specified property are those
c − b ∈ S. Then S is an arithmetic progression. pairs with n = 1, together with the single pair (2, 2).
We first check that these do work. For n = 1, it is clear
that taking v = (1) and M = (0) has the desired effect.
Saturday, December 1, 2012
A1 Let d1 , d2 , . . . , d12 be real numbers in the open interval (i) The functions f1 (x) = ex − 1 and f2 (x) = ln(x + 1)
(1, 12). Show that there exist distinct indices i, j, k such are in S;
that di , d j , dk are the side lengths of an acute triangle. (ii) If f (x) and g(x) are in S, the functions f (x) + g(x)
A2 Let ∗ be a commutative and associative binary operation and f (g(x)) are in S;
on a set S. Assume that for every x and y in S, there (iii) If f (x) and g(x) are in S and f (x) ≥ g(x) for all
exists z in S such that x ∗ z = y. (This z may depend on x ≥ 0, then the function f (x) − g(x) is in S.
x and y.) Show that if a, b, c are in S and a ∗ c = b ∗ c,
then a = b. Prove that if f (x) and g(x) are in S, then the function
f (x)g(x) is also in S.
A3 Let f : [−1, 1] → R be a continuous function such that B2 Let P be a given (non-degenerate) polyhedron. Prove
2
2 that there is a constant c(P) > 0 with the following
(i) f (x) = 2−x
2 f x
2−x2
for every x in [−1, 1], property: If a collection of n balls whose volumes sum
to V contains the entire surface of P, then n > c(P)/V 2 .
(ii) f (0) = 1, and
√f (x)
B3 A round-robin tournament of 2n teams lasted for 2n − 1
(iii) limx→1− exists and is finite.
1−x days, as follows. On each day, every team played one
game against another team, with one team winning and
Prove that f is unique, and express f (x) in closed form.
one team losing in each of the n games. Over the course
A4 Let q and r be integers with q > 0, and let A and B be of the tournament, each team played every other team
intervals on the real line. Let T be the set of all b + mq exactly once. Can one necessarily choose one winning
where b and m are integers with b in B, and let S be team from each day without choosing any team more
the set of all integers a in A such that ra is in T . Show than once?
that if the product of the lengths of A and B is less than
B4 Suppose that a0 = 1 and that an+1 = an + e−an for n =
q, then S is the intersection of A with some arithmetic
0, 1, 2, . . . . Does an − log n have a finite limit as n → ∞?
progression.
(Here log n = loge n = ln n.)
A5 Let F p denote the field of integers modulo a prime p,
B5 Prove that, for any two bounded functions g1 , g2 : R →
and let n be a positive integer. Let v be a fixed vec-
[1, ∞), there exist functions h1 , h2 : R → R such that, for
tor in Fnp , let M be an n × n matrix with entries of F p ,
every x ∈ R,
and define G : Fnp → Fnp by G(x) = v + Mx. Let G(k)
denote the k-fold composition of G with itself, that is, sup(g1 (s)x g2 (s)) = max(xh1 (t) + h2 (t)).
G(1) (x) = G(x) and G(k+1) (x) = G(G(k) (x)). Determine s∈R t∈R
all pairs p, n for which there exist v and M such that the
pn vectors G(k) (0), k = 1, 2, . . . , pn are distinct. B6 Let p be an odd prime number such that p ≡ 2 (mod 3).
Define a permutation π of the residue classes modulo p
A6 Let f (x, y) be a continuous, real-valued function on R2 . by π(x) ≡ x3 (mod p). Show that π is an even permu-
Suppose that, for every rectangular region R of area 1, tation if and only if p ≡ 3 (mod 4).
the double integral of f (x, y) over R equals 0. Must
f (x, y) be identically 0?
B1 Let S be a class of functions from [0, ∞) to [0, ∞) that
satisfies:
, Solutions to the 73rd William Lowell Putnam Mathematical Competition
Saturday, December 1, 2012
Kiran Kedlaya and Lenny Ng
A1 Without loss of generality, assume d1 ≤ d2 ≤ · · · ≤ d12 . Proof. We may assume #S ≥ 3, as otherwise S is trivially an
2 < d 2 + d 2 for some i ≤ 10, then d , d
If di+2 i i+1 i i+1 , di+2 arithmetic progression. Let a1 , a2 be the smallest and second-
are the side lengths of an acute triangle, since in this smallest elements of S, respectively, and put d = a2 − a1 . Let
case di2 < di+1
2 +d 2 and d 2 < d 2 +d 2 as well. Thus
i+2 i+1 i i+2 m be the smallest positive integer such that a1 + md ∈ / S. Sup-
we may assume di+2 2 ≥ d2 + d2 pose that there exists an integer n contained in S but not in
i i+1 for all i. But then
by induction, di2 ≥ Fi d12 for all i, where Fi is the i-th {a1 , a1 + d, . . . , a1 + (m − 1)d}, and choose the least such n.
Fibonacci number (with F1 = F2 = 1): i = 1 is clear, i = By the hypothesis applied with (a, b, c) = (a1 , a2 , n), we see
2 follows from d2 ≥ d1 , and the induction step follows that n − d also has the property, a contradiction.
from the assumed inequality. Setting i = 12 now gives
2 ≥ 144d 2 , contradicting d > 1 and d < 12.
d12 1 12
We now return to the original problem. By dividing
1
B, q, r by gcd(q, r) if necessary, we may reduce to the
Remark. A materially equivalent problem appeared on case where gcd(q, r) = 1. We may assume #S ≥ 3, as
the 2012 USA Mathematical Olympiad and USA Junior otherwise S is trivially an arithmetic progression. Let
Mathematical Olympiad. a1 , a2 , a3 be any three distinct elements of S, labeled
A2 Write d for a ∗ c = b ∗ c ∈ S. For some e ∈ S, d ∗ e = a, so that a1 < a2 < a3 , and write rai = bi + mi q with
and thus for f = c ∗ e, a ∗ f = a ∗ c ∗ e = d ∗ e = a and bi , mi ∈ Z and bi ∈ B. Note that b1 , b2 , b3 must also be
b ∗ f = b ∗ c ∗ e = d ∗ e = a. Let g ∈ S satisfy g ∗ a = b; distinct, so the differences b2 − b1 , b3 − b1 , b3 − b2 are
then b = g ∗ a = g ∗ (a ∗ f ) = (g ∗ a) ∗ f = b ∗ f = a, as all nonzero; consequently, two of them have the same
desired. sign. If bi − b j and bk − bl have the same sign, then we
must have
Remark. With slightly more work, one can show that
S forms an abelian group with the operation ∗. (ai − a j )(bk − bl ) = (bi − b j )(ak − al )
√
A3 We will prove that f (x) = 1 − x2 for √ all x ∈ [−1, 1]. because both sides are of the same sign, of absolute
Define g : (−1, 1)
√ → R by g(x) = f (x)/ 1 − x2 . Plug- value less than q, and congruent to each other modulo
2
ging f (x) = g(x) 1 − x into equation (i) and simplify- q. In other words, the points (a1 , b1 ), (a2 , b2 ), (a3 , b3 )
ing yields in R2 are collinear. It follows that a4 = a1 + a3 − a2
2 also belongs to S (by taking b4 = b1 + b3 − b2 ), so S
x satisfies the conditions of the lemma. It is therefore an
g(x) = g (1)
2 − x2 arithmetic progression.
for all x ∈ (−1, 1). Now fix x ∈ (−1, 1) and define a Reinterpretations. One can also interpret this argu-
a2n ment geometrically using cross products (suggested by
sequence {an }∞
n=1 by a1 = x and an+1 = 2−a2n
. Then Noam Elkies), or directly in terms of congruences (sug-
|2
an ∈ (−1, 1) and thus |an+1 | ≤ |an for all n. It follows gested by Karl Mahlburg).
that {|an |} is a decreasing sequence with |an | ≤ |x|n for Remark. The problem phrasing is somewhat confus-
all n, and so limn→∞ an = 0. Since g(an ) = g(x) for ing: to say that “S is the intersection of [the interval]
all n by (1) and g is continuous at 0, we conclude that A with an arithmetic progression” is the same thing as
g(x) = g(0) = f (0) = 1. This holds for all x ∈ (−1, 1) saying that “S is the empty set or an arithmetic progres-
and thus for x = ±1 as well by continuity. The result sion” unless it is implied that arithmetic progressions
follows. are necessarily infinite. Under that interpretation, how-
Remark. As pointed out by Noam Elkies, condition ever, the problem becomes false; for instance, for
(iii) is unnecessary. However, one can use it to derive
a slightly different solution by running the recursion in q = 5, r = 1, A = [1, 3], B = [0, 2],
the opposite direction.
we have
A4 We begin with an easy lemma.
T = {· · · , 0, 1, 2, 5, 6, 7, . . . }, S = {1, 2}.
Lemma. Let S be a finite set of integers with the following
property: for all a, b, c ∈ S with a ≤ b ≤ c, we also have a + A5 The pairs (p, n) with the specified property are those
c − b ∈ S. Then S is an arithmetic progression. pairs with n = 1, together with the single pair (2, 2).
We first check that these do work. For n = 1, it is clear
that taking v = (1) and M = (0) has the desired effect.
