Solutions to the 73rd William Lowell Putnam Mathematical Competition

Saturday, December 1, 2012

Kiran Kedlaya and Lenny Ng
A1 Without loss of generality, assume d
1
d
2

d
12
. If d
2
i+2
< d
2
i
+ d
2
i+1
for some i 10, then
d
i
, d
i+1
, d
i+2
are the side lengths of an acute triangle,
since in this case d
2
i
< d
2
i+1
+ d
2
i+2
and d
2
i+1
< d
2
i
+
d
2
i+2
as well. Thus we may assume d
2
i+2
d
2
i
+ d
2
i+1
for all i. But then by induction, d
2
i
F
i
d
2
1
for all i,
where F
i
is the i-th Fibonacci number (with F
1
= F
2
=
1): i = 1 is clear, i = 2 follows from d
2
d
1
, and
the induction step follows from the assumed inequality.
Setting i = 12 now gives d
2
12
144d
2
1
, contradicting
d
1
> 1 and d
12
< 12.
Remark. A materially equivalent problem appeared on
the 2012 USA Mathematical Olympiad and USA Junior
Mathematical Olympiad.
A2 Write d for ac = bc S. For some e S, de = a,
and thus for f = c e, a f = a c e = d e = a and
bf = bce = de = a. Let g S satisfy g a = b;
then b = g a = g (a f) = (g a) f = b f = a,
as desired.
Remark. With slightly more work, one can show that
S forms an abelian group with the operation .
A3 We will prove that f(x) =

1 x
2
for all x [1, 1].
Dene g : (1, 1) R by g(x) = f(x)/

1 x
2
.
Plugging f(x) = g(x)

1 x
2
into equation (i) and
simplifying yields
g(x) = g
_
x
2
2 x
2
_
(1)
for all x (1, 1). Now x x (1, 1) and dene
a sequence a
n

n=1
by a
1
= x and a
n+1
=
a
2
n
2a
2
n
.
Then a
n
(1, 1) and thus [a
n+1
[ [a
n
[
2
for all
n. It follows that [a
n
[ is a decreasing sequence with
[a
n
[ [x[
n
for all n, and so lim
n
a
n
= 0. Since
g(a
n
) = g(x) for all n by (1) and g is continuous at
0, we conclude that g(x) = g(0) = f(0) = 1. This
holds for all x (1, 1) and thus for x = 1 as well
by continuity. The result follows.
Remark. As pointed out by Noam Elkies, condition
(iii) is unnecessary. However, one can use it to derive
a slightly different solution by running the recursion in
the opposite direction.
A4 We begin with an easy lemma.
Lemma. Let S be a nite set of integers with the following
property: for all a, b, c S with a b c, we also have
a +c b S. Then S is an arithmetic progression.
Proof. We may assume #S 3, as otherwise S is trivially an
arithmetic progression. Let a
1
, a
2
be the smallest and second-
smallest elements of S, respectively, and put d = a
2
a
1
. Let
mbe the smallest integer such that a
1
+md / S. Suppose that
there exists an integer n contained in S but not in a
1
, a
1
+
d, . . . , a
1
+ (m 1)d, and choose the least such n. By the
hypothesis applied with (a, b, c) = (a
1
, a
2
, n), we see that
n d also has the property, a contradiction.
We now return to the original problem. By dividing
B, q, r by gcd(q, r) if necessary, we may reduce to the
case where gcd(q, r) = 1. We may assume #S 3, as
otherwise S is trivially an arithmetic progression. Let
a
1
, a
2
, a
3
be any three distinct elements of S, labeled
so that a
1
< a
2
< a
3
, and write ra
i
= b
i
+ m
i
q with
b
i
, m
i
Z and b
i
B. Note that b
1
, b
2
, b
3
must also be
distinct, so the differences b
2
b
1
, b
3
b
1
, b
3
b
2
are
all nonzero; consequently, two of them have the same
sign. If b
i
b
j
and b
k
b
l
have the same sign, then we
must have
(a
i
a
j
)(b
k
b
l
) = (b
i
b
j
)(a
k
a
l
)
because both sides are of the same sign, of absolute
value less than q, and congruent to each other modulo
q. In other words, the points (a
1
, b
1
), (a
2
, b
2
), (a
3
, b
3
)
in R
2
are collinear. It follows that a
4
= a
1
+ a
3
a
2
also belongs to S (by taking b
4
= b
1
+ b
3
b
2
), so S
satises the conditions of the lemma. It is therefore an
arithmetic progression.
Reinterpretations. One can also interpret this argu-
ment geometrically using cross products (suggested by
Noam Elkies), or directly in terms of congruences (sug-
gested by Karl Mahlburg).
Remark. The problem phrasing is somewhat confus-
ing: to say that S is the intersection of [the interval]
A with an arithmetic progression is the same thing as
saying that S is the empty set or an arithmetic progres-
sion unless it is implied that arithmetic progressions
are necessarily innite. Under that interpretation, how-
ever, the problem becomes false; for instance, for
q = 5, r = 1, A = [1, 3], B = [0, 2],
we have
T = , 0, 1, 2, 5, 6, 7, . . . , S = 1, 2.
A5 The pairs (p, n) with the specied property are those
pairs with n = 1, together with the single pair (2, 2).
We rst check that these do work. For n = 1, it is
clear that taking v = (1) and M = (0) has the desired
2
effect. For (p, n) = (2, 2), we take v =
_
0 1
_
and
M =
_
1 1
0 1
_
and then observe that
G
(k)
(0) =
_
0
0
_
,
_
0
1
_
,
_
1
0
_
,
_
1
1
_
, k = 0, 1, 2, 3.
We next check that no other pairs work, keeping in mind
that the desired condition means that G acts on F
n
p
as a
cyclic permutation. Assume by way of contradiction
that (p, n) has the desired property but does not appear
in our list. In particular, we have n 2.
Let I be the n n identity matrix over F
p
. Decompose
F
n
p
as a direct sum of two subspaces V, W such that
M I is nilpotent on V and invertible on W. Suppose
that W ,= 0. Split v as v
1
+ v
2
with v
1
V , v
2
W.
Since M I is invertible on W, there exists a unique
w W such that (M I)w = v
2
. Then G
(k)
(w)
w V for all nonnegative integers k. Let k be the least
positive integer such that G
(k)
(w) = w; then k is at
most the cardinality of V , which is strictly less than p
n
because W ,= 0. This gives a contradiction and thus
forces W = 0.
In other words, the matrix N = M I is nilpotent;
consequently, N
n
= 0. For any positive integer k, we
have
G
(k)
(0) = v +Mv + +M
k1
v
=
k1

j=0
n1

i=0
_
j
i
_
N
i
v
=
n1

i=0
_
k
i + 1
_
N
i
v.
If n 2 and (p, n) ,= (2, 2), then p
n1
> n and so
G
k
(0) = 0 for k = p
n1
(because all of the binomial
coefcients are divisible by p). This contradiction com-
pletes the proof.
A6 First solution. Yes, f(x, y) must be identically 0. We
proceed using a series of lemmas.
Lemma 1. Let R be a rectangular region of area 1 with
corners A, B, C, D labeled in counterclockwise order. Then
f(A) +f(C) = f(B) +f(D).
Proof. We may choose coordinates so that for some c > 0,
A = (0, 0), B = (c, 0), C = (c, 1/c), D = (0, 1/c).
Dene the functions
g(x, y) =
_
x+c
x
f(t, y) dt
h(x, y) =
_
y
0
g(x, u) du.
For any x, y R,
h(x, y + 1/c) h(x, y) =
_
x+c
x
_
y+1/c
y
f(t, u) dt du = 0
by hypothesis, so h(x, y +1/c) = h(x, y). By the fundamen-
tal theorem of calculus, we may differentiate both sides of
this identity with respect to y to deduce that g(x, y + 1/c) =
g(x, y). Differentiating this new identity with respect to x
yields the desired equality.
Lemma 2. Let C be a circle whose diameter d is at least

2,
and let AB and A

be two diameters of C. Then f(A) +

f(B) = f(A

) +f(B

).
Proof. By continuity, it sufces to check the case where =
arcsin
2
d
2
is an irrational multiple of 2. Let be the ra-
dian measure of the counterclockwise arc from A to A

. By
Lemma 1, the claim holds when = . By induction, the
claim also holds when n (mod 2) for any positive
integer n. Since is an irrational multiple of 2, the posi-
tive multiples of ll out a dense subset of the real numbers
modulo 2, so by continuity the claim holds for all .
Lemma 3. Let R be a rectangular region of arbitrary (pos-
itive) area with corners A, B, C, D labeled in counterclock-
wise order. Then f(A) +f(C) = f(B) +f(D).
Proof. Let EF be a segment such that AEFD and BEFC
are rectangles whose diagonals have length at least

2. By
Lemma 2,
f(A) +f(F) = f(D) +f(E)
f(C) +f(E) = f(B) +f(F),
yielding the claim.
Lemma 4. The restriction of f to any straight line is constant.
Proof. We may choose coordinates so that the line in question
is the x-axis. Dene the function g(y) by
g(y) = f(0, y) f(0, 0).
By Lemma 3, for all x R,
f(x, y) = f(x, 0) +g(y).
For any c > 0, by the original hypothesis we have
0 =
_
x+c
x
_
y+1/c
y
f(u, v) dudv
=
_
x+c
x
_
y+1/c
y
(f(u, 0) +g(v)) dudv
=
1
c
_
x+c
x
f(u, 0) du +c
_
y+1/c
y
g(v) dv.
In particular, the function F(x) =
_
x+c
x
f(u, 0) du is con-
stant. By the fundamental theorem of calculus, we may dif-
ferentiate to conclude that f(x+c, 0) = f(x, 0) for all x R.
Since c was also arbitrary, we deduce the claim.
3
To complete the proof, note that since any two points in
R
2
are joined by a straight line, Lemma 4 implies that f
is constant. This constant equals the integral of f over
any rectangular region of area 1, and hence must be 0
as desired.
Second solution (by Eric Larson, communicated by
Noam Elkies). In this solution, we x coordinates and
assume only that the double integral vanishes on each
rectangular region of area 1 with sides parallel to the
coordinate axes, and still conclude that f must be iden-
tically 0.
Lemma. Let R be a rectangular region of area 1 with sides
parallel to the coordinate axes. Then the averages of f over
any two adjacent sides of R are equal.
Proof. Without loss of generality, we may take R to have cor-
ners (0, 0), (c, 0), (c, 1/c), (0, 1/c) and consider the two sides
adjacent to (c, 1/c). Differentiate the equality
0 =
_
x+c
x
_
y+1/c
y
f(u, v) dudv
with respect to c to obtain
0 =
_
y+1/c
y
f(x +c, v) dv
1
c
2
_
x+c
x
f(u, y + 1/c) du.
Rearranging yields
c
_
y+1/c
y
f(x +c, v) dv =
1
c
_
x+c
x
f(u, y + 1/c) du,
which asserts the desired result.
Returning to the original problem, given any c > 0,
we can tile the plane with rectangles of area 1 whose
vertices lie in the lattice (mc, n/c) : m, n Z. By
repeated application of the lemma, we deduce that for
any positive integer n,
_
c
0
f(u, 0) du =
_
(n+1)c
nc
f(u, 0) du.
Replacing c with c/n, we obtain
_
c/n
0
f(u, 0) du =
_
c+1/n
c
f(u, 0) du.
Fixing c and taking the limit as n yields f(0, 0) =
f(c, 0). By similar reasoning, f is constant on any hor-
izontal line and on any vertical line, and as in the rst
solution the constant value is forced to equal 0.
Third solution. (by Sergei Artamoshin) We retain the
weaker hypothesis of the second solution. Assume by
way of contradiction that f is not identically zero.
We rst exhibit a vertical segment PQ with f(P) > 0
and f(Q) < 0. It cannot be the case that f(P) 0
for all P, as otherwise the vanishing of the zero over
any rectangle would force f to vanish identically. By
continuity, there must exist an open disc U such that
f(P) > 0 for all P U. Choose a rectangle R of
area 1 with sides parallel to the coordinate axes with
one horizontal edge contained in U. Since the integral
of f over Ris zero, there must exist a point Q Rsuch
that f(Q) < 0. Take P to be the vertical projection of
Q onto the edge of R contained in U.
By translating coordinates, we may assume that P =
(0, 0) and Q = (0, a) for some a > 0. For s suf-
ciently small, f is positive on the square of side length
2s centered at P, which we call S, and negative on the
square of side length 2s centered at Q, which we call
S

. Since the ratio 2s/(1 4s

2
) tends to 0 as s does,
we can choose s so that 2s/(1 4s
2
) = a/n for some
positive integer n.
For i Z, let A
i
be the rectangle
_
(x, y) : s x s +
1 4s
2
2s
,
s +i
2s
1 4s
2
y s +i
2s
1 4s
2
_
and let B
i
be the rectangle
_
(x, y) : s x s +
1 4s
2
2s
,
s +i
2s
1 4s
2
y s + (i + 1)
2s
1 4s
2
_
.
Then for all i Z,
S A
0
, A
n
S

, A
i
B
i
, B
i
A
i+1
are all rectangles of area 1 with sides parallel to the co-
ordinate axes, so the integral over f over each of these
rectangles is zero. Since the integral over S is positive,
the integral over A
0
must be negative; by induction, for
all i Z the integral over A
i
is negative and the integral
over B
i
is positive. But this forces the integral over S

to be positive whereas f is negative everywhere on S

,
a contradiction.
B1 Each of the following functions belongs to S for the
reasons indicated.
f(x), g(x) given
ln(x + 1) (i)
ln(f(x) + 1), ln(g(x) + 1) (ii) plus two previous lines
ln(f(x) + 1) + ln(g(x) + 1) (ii)
e
x
1 (i)
(f(x) + 1)(g(x) + 1) 1 (ii) plus two previous lines
f(x)g(x) +f(x) +g(x) previous line
f(x) +g(x) (ii) plus rst line
f(x)g(x) (iii) plus two previous lines
4
B2 Fix a face F of the polyhedron with area A. Suppose F
is completely covered by balls of radii r
1
, . . . , r
n
whose
volumes sum to V . Then on one hand,
n

i=1
4
3
r
3
i
= V.
On the other hand, the intersection of a ball of radius r
with the plane containing F is a disc of radius at most r,
which covers a piece of F of area at most r
2
; therefore
n

i=1
r
2
i
A.
By writing n as

n
i=1
1 and applying H olders inequal-
ity, we obtain
nV
2

_
n

i=1
_
4
3
r
3
i
_
2/3
_
3

16
9

2
A
3
.
Consequently, any value of c(P) less than
16
9

2
A
3
works.
B3 The answer is yes. We rst note that for any collection
of m days with 1 m 2n 1, there are at least m
distinct teams that won a game on at least one of those
days. If not, then any of the teams that lost games on
all of those days must in particular have lost to m other
teams, a contradiction.
If we now construct a bipartite graph whose vertices
are the 2n teams and the 2n 1 days, with an edge
linking a day to a team if that team won their game on
that day, then any collection of m days is connected
to a total of at least m teams. It follows from Halls
Marriage Theorem that one can match the 2n 1 days
with 2n 1 distinct teams that won on their respective
days, as desired.
B4 First solution. We will show that the answer is yes.
First note that for all x > 1, e
x
1 +x and thus
x log(1 +x). (2)
We next claim that a
n
> log(n + 1) (and in particular
that a
n
log n > 0) for all n, by induction on n. For
n = 0 this follows from a
0
= 1. Now suppose that
a
n
> log(n + 1), and dene f(x) = x +e
x
, which is
an increasing function in x > 0; then a
n+1
= f(a
n
) >
f(log(n+1)) = log(n+1) +1/(n+1) log(n+2),
where the last inequality is (2) with x = 1/(n+1). This
completes the induction step.
It follows that a
n
log n is a decreasing function in n:
we have (a
n+1
log(n+1)) (a
n
log n) = e
an
+
log(n/(n + 1)) < 1/(n + 1) + log(n/(n + 1)) 0,
where the nal inequality is (2) with x = 1/(n +
1). Thus a
n
log n

n=0
is a decreasing sequence of
positive numbers, and so it has a limit as n .
Second solution. Put b
n
= e
an
, so that b
n+1
=
b
n
e
1/bn
. In terms of the b
n
, the problem is to prove
that b
n
/n has a limit as n ; we will show that the
limit is in fact equal to 1.
Expanding e
1/bn
as a Taylor series in 1/b
n
, we have
b
n+1
= b
n
+ 1 +R
n
where 0 R
n
c/b
n
for some absolute constant c >
0. By writing
b
n
= n +e +
n1

i=0
R
i
,
we see rst that b
n
n +e. We then see that
0
b
n
n
1

e
n
+
n1

i=0
R
i
n

e
n
+
n1

i=0
1
nb
i

e
n
+
n1

i=0
1
n(i +e)

e
n
+
log n
n
.
It follows that b
n
/n 1 as n .
Remark. This problem is an example of the general
principle that one can often predict the asymptotic be-
havior of a recursive sequence by studying solutions of
a sufciently similar-looking differential equation. In
this case, we start with the equation a
n+1
a
n
= e
an
,
then replace a
n
with a function y(x) and replace the
difference a
n+1
a
n
with the derivative y

(x) to obtain
the differential equation y

= e
y
, which indeed has
the solution y = log x.
B5 Dene the function
f(x) = sup
sR
xlog g
1
(s) + log g
2
(s).
As a function of x, f is the supremum of a collection
of afne functions, so it is convex. The function e
f(x)
is then also convex, as may be checked directly from
the denition: for x
1
, x
2
R and t [0, 1], by the
weighted AM-GM inequality
te
f(x1)
+ (1 t)e
f(x2)
e
tf(x1)+(1t)f(x2)
e
f(tx1+(1t)x2)
.
For each t R, draw a supporting line to the graph of
e
f(x)
at x = t; it has the form y = xh
1
(t) + h
2
(t) for
some h
1
(t), h
2
(t) R. For all x, we then have
sup
sR
g
1
(s)
x
g
2
(s) xh
1
(t) +h
2
(t)
5
with equality for x = t. This proves the desired equality
(including the fact that the maximum on the right side
is achieved).
Remark. This problemdemonstrates an example of du-
ality for convex functions.
B6 First solution. Since xed points do not affect the sig-
nature of a permutation, we may ignore the residue class
of 0 and consider as a permutation on the nonzero
residue classes modulo p. These form a cyclic group of
order p 1, so the signature of is also the signature
of multiplication by 3 as a permutation of the residue
classes modulo p 1. If we identify these classes with
the integers 0, . . . , p 2, then the signature equals the
parity of the number of inversions: these are the pairs
(i, j) with 0 i < j p 2 for which (i) > (j).
We may write
(i) = 3i (p 1)
_
3i
p 1
_
from which we see that (i, j) cannot be an inversion
unless
3j
p1
| >
3i
p1
|. In particular, we only obtain
inversions when i < 2(p 1)/3.
If i < (p 1)/3, the elements j of 0, . . . , p 2 for
which (i, j) is an inversion correspond to the elements
of 0, . . . , 3i which are not multiples of 3, which are
2i in number. This contributes a total of 0 + 2 + +
2(p 2)/3 = (p 2)(p + 1)/9 inversions.
If (p 1)/3 < i < 2(p 1)/3, the elements j of
0, . . . , p 2 for which (i, j) is an inversion corre-
spond to the elements of 0, . . . , 3i p +1 congruent
to 1 modulo 3, which are (3ip+2)/3 = i(p2)/3 in
number. This contributes a total of 1+ +(p2)/3 =
(p 2)(p + 1)/18 inversions.
Summing up, the total number of inversions is (p
2)(p + 1)/6, which is even if and only if p 3
(mod 4). This proves the claim.
Second solution (by Noam Elkies). Recall that the sign
of (which is +1 if is even and 1 if is odd) can
be computed as

0x<y<p
(x) (y)
x y
(because composing with a transposition changes the
sign of the product). Reducing modulo p, we get a con-
gruence with

0x<y<p
x
3
y
3
x y
=

0x<y<p
(x
2
+xy +y
2
).
It thus sufces to count the number of times each pos-
sible value of x
2
+ xy + y
2
occurs. Each nonzero
value c modulo p occurs p + 1 times as x
2
+ xy + y
2
with 0 x, y < p and hence (p + (c/3))/2 times
with 0 x < y < p, where denotes the quadratic
character modulo p. Since p 2 (mod 3), by the
law of quadratic reciprocity we have (3) = +1, so
(c/3) = (c). It thus remains to evaluate the prod-
uct

p1
c=1
c
(p+(c))/2
modulo p.
If p 3 (mod 4), this is easy: each factor is a
quadratic residue (this is clear if c is a residue, and oth-
erwise (c) = +1 so p+(c) is divisible by 4) and
1 is not, so we must get +1 modulo p.
If p 1 (mod 4), we must do more work: we choose
a primitive root g modulo p and rewrite the product as
p2

i=0
g
i(p+(1)
i
)/2
.
The sum of the exponents, split into sums over i odd
and i even, gives
(p3)/2

j=0
_
j(p + 1) +
(2j + 1)(p 1)
2
_
which simplies to
(p 3)(p 1)(p + 1)
8
+
(p 1)
3
8
=
p 1
2
_
p
2
1
2
p
_
.
Hence the product we are trying to evaluate is congruent
to g
(p1)/2
1 modulo p.
Third solution (by Mark van Hoeij). We compute the
parity of as the parity of the number of cycles of
even length in the cycle decomposition of . For x a
nonzero residue class modulo p of multiplicative order
d, the elements of the orbit of x under also have or-
der d (because d divides p 1 and hence is coprime to
3). Since the group of nonzero residue classes modulo
p is cyclic of order p 1, the elements of order d fall
into (d)/f(d) orbits under , where is the Euler phi
function and f(d) is the multiplicative order of 3 mod-
ulo d. The parity of is then the parity of the sum of
(d)/f(d) over all divisors d of p 1 for which f(d)
is even.
If d is odd, then (d)/f(d) = (2d)/f(2d), so the
summands corresponding to d and 2d coincide. It thus
sufces to consider those d divisible by 4. If p 3
(mod 4), then there are no such summands, so the sum
is trivially even.
If p 1 (mod 4), then d = 4 contributes a summand
of (4)/f(4) = 2/2 = 1. For each d which is a
larger multiple of 4, the group (Z/dZ)

is isomorphic
to the product of Z/2Z with another group of even or-
der, so the maximal power of 2 dividing f(d) is strictly
smaller than the maximal power of 2 dividing d. Hence
(d)/f(d) is even, and so the overall sum is odd.
Remark. Note that the second proof uses quadratic
reciprocity, whereas the rst and third proofs are sim-
ilar to several classical proofs of quadratic reciprocity.
6
Abhinav Kumar notes that the problem itself is a spe-
cial case of the Duke-Hopkins quadratic reciprocity
law for abelian groups (Quadratic reciprocity in a -
nite group, Amer. Math. Monthly 112 (2005), 251
256; see also http://math.uga.edu/

pete/
morequadrec.pdf).