The 76th William Lowell Putnam Mathematical Competition
Saturday, December 5, 2015
A1 Let A and B be points on the same branch of the hyper- four numbers off the list. Repeat with the three smallest
bola xy = 1. Suppose that P is a point lying between remaining numbers 4, 5, 7 and their sum 16. Continue
A and B on this hyperbola, such that the area of the tri- in this way, crossing off the three smallest remaining
angle APB is as large as possible. Show that the re- numbers and their sum, and consider the sequence of
gion bounded by the hyperbola and the chord AP has sums produced: 6, 16, 27, 36, . . . . Prove or disprove that
the same area as the region bounded by the hyperbola there is some number in the sequence whose base 10
and the chord PB. representation ends with 2015.
A2 Let a0 = 1, a1 = 2, and an = 4an−1 − an−2 for n ≥ 2. B3 Let S be the set of all 2 × 2 real matrices
Find an odd prime factor of a2015 .
a b
M=
A3 Compute c d
2015 2015
! whose entries a, b, c, d (in that order) form an arithmetic
2πiab/2015 progression. Find all matrices M in S for which there is
log2 ∏ ∏ (1 + e )
a=1 b=1 some integer k > 1 such that M k is also in S.
Here i is the imaginary unit (that is, i2 = −1). B4 Let T be the set of all triples (a, b, c) of positive integers
for which there exist triangles with side lengths a, b, c.
A4 For each real number x, let Express
1 2a
f (x) = ∑ n
, ∑
n∈Sx 2 3b 5c
(a,b,c)∈T
where Sx is the set of positive integers n for which bnxc as a rational number in lowest terms.
is even. What is the largest real number L such that
f (x) ≥ L for all x ∈ [0, 1)? (As usual, bzc denotes the B5 Let Pn be the number of permutations π of {1, 2, . . . , n}
greatest integer less than or equal to z.) such that
A5 Let q be an odd positive integer, and let Nq denote |i − j| = 1 implies |π(i) − π( j)| ≤ 2
the number of integers a such that 0 < a < q/4 and
gcd(a, q) = 1. Show that Nq is odd if and only if q is for all i, j in {1, 2, . . . , n}. Show that for n ≥ 2, the quan-
of the form pk with k a positive integer and p a prime tity
congruent to 5 or 7 modulo 8.
Pn+5 − Pn+4 − Pn+3 + Pn
A6 Let n be a positive integer. Suppose that A, B, and M are
n×n matrices with real entries such that AM = MB, and does not depend on n, and find its value.
such that A and B have the same characteristic polyno-
mial. Prove that det(A − MX) = det(B − XM) for every B6 For each positive integer k, let A(k)√ be the number of
n × n matrix X with real entries. odd divisors of k in the interval [1, 2k). Evaluate
∞
B1 Let f be a three times differentiable function (defined A(k)
on R and real-valued) such that f has at least five dis- ∑ (−1)k−1 k
.
k=1
tinct real zeros. Prove that f + 6 f 0 + 12 f 00 + 8 f 000 has at
least two distinct real zeros.
B2 Given a list of the positive integers 1, 2, 3, 4, . . . , take the
first three numbers 1, 2, 3 and their sum 6 and cross all
, Solutions to the 76th William Lowell Putnam Mathematical Competition
Saturday, December 5, 2015
Manjul Bhargava, Kiran Kedlaya, and Lenny Ng
A1 First solution: Without loss of generality, assume that any integer m and any prime p dividing am , p also di-
A and B lie in the first quadrant with A = (t1 , 1/t1 ), B = vides a−m ; on the other hand, p cannot divide a−m+1 ,
(t2 , 1/t2 ), and t1 < t2 . If P = (t, 1/t) with t1 ≤ t ≤ t2 , as otherwise p would also divide a−m+2 , . . . , a0 = 1, a
then the area of triangle APB is contradiction. We can thus find an integer k such that
am+1 ≡ ka−m+1 (mod p); by induction on n, we see
1 1 1 1 t2 − t1 that an ≡ kan−2m (mod p) for all n. In particular, if k is
t1 t t2 = (t1 + t2 − t − t1t2 /t). odd, then p also divides akm ; we thus conclude (again)
2 1/t 1/t 1/t 2t1t2
1 2 that a2015 is divisible by a5 = 362 and thus by 181.
Remark: Although it was not needed in the solution,
When t1 ,t2 are fixed, this is maximized when t + t1t2 /t
we note in passing that if an ≡ 0 (mod p), then a2n+k ≡
is minimized,
√ which by AM-GM exactly holds when
−ak (mod p) for all k.
t = t1t2 .
Remark: One can find other odd prime factors of a2015
The line AP is given by y = t1 +t−x tt1 , and so the area of in the same manner. For example, a2015 is divisible by
the region bounded by the hyperbola and AP is each of the following quantities. (The prime factoriza-
Z t tions were computed using the Magma computer algebra
t1 + t − x 1 t t1 t
− dx = − − log , system.)
t1 tt 1 x 2t 1 2t t1
√ a13 = 2 × 6811741
2 −t1
which at t = t1t2 is equal to 2t√
p
t1 t2 − log( t2 /t1 ). a31 = 2 × 373 × 360250962984637
Similarly, the area of the region bounded by the√hyper-
bola and PB is 2t t2
− 2tt 2 − log tt2 , which at t = t1t2 is a5·13 = 2 × 181 × 6811741
2 −t1 × 3045046274679316654761356161
also 2t√
p
t t − log( t2 /t1 ), as desired.
12
a5·31 = 1215497709121 × 28572709494917432101
Second solution: For any λ > 0, the map (x, y) 7→
× 13277360555506179816997827126375881581
(λ x, λ −1 y) preserves both areas and the hyperbola xy =
1. We may thus rescale the picture so that A, B are sym- a13·31 = 2 × 373 × 193441 × 6811741 × 360250962984637
metric across the line y = x, with A above the line. As × 16866100753000669
P moves from A to B, the area of APB increases until P × 79988387992470656916594531961 × p156
passes through the point (1, 1), then decreases. Conse-
quently, P = (1, 1) achieves the maximum area, and the where p156 is a prime of 156 decimal digits. Dividing
desired equality is obvious by symmetry. Alternatively, a2015 by the product of the primes appearing in this list
since the hyperbola is convex, the maximum is uniquely yields a number N of 824 decimal digits which is defi-
achieved at the point where the tangent line is parallel nitely not prime, because 2N 6≡ 2 (mod N), but whose
to AB, and by symmetry that point is P. prime factorization we have been unable to establish.
Note that N is larger than a 2048-bit RSA modulus, so
A2 First solution: One possible√answer is 181. √ nBy in- the difficulty of factoring it is not surprising.
duction, we have an = ((2 + 3)n + (2 − √ 3) )/2 =
(α n √
+ β n )/2 for all n, where α = 2 + 3 and β = One thing we can show is that each prime factor of N is
congruent to 1 modulo 6 × 2015 = 12090, thanks to the
2 − 3. Now note that if k is an odd positive integer
kn +β kn following lemma.
and an 6= 0, then aaknn = αα n +β n =α
(k−1)n −α (k−2)n β n +
· · · − α n β (k−2)n + β (k−1)n . This expression is both ra- Lemma. Let n be an odd integer. Then any odd prime factor
tional√(because an and akn are integers) and of the form p of an which does not divide am for any divisor m of n is
a + b 3 for some integers a, b by the expressions for congruent to 1 modulo lcm(6, n). (By either solution of the
α, β ; it follows that it must be an integer, and so akn is original problem, p also does not divide am for any positive
divisible by an . Applying this to n = 5 and k = 403, we integer m < n.)
find that a2015 is divisible by a5 = 362 and thus by 181. √
Proof. We first check that p ≡ 1 (mod 3). In Fq = F p ( 3)
Second solution: By rewriting the formula for an as we have (α/β )n ≡ −1. If p ≡ 2 (mod 3), then q = p2 and
an−2 = 4an−1 − an , we may extend the sequence back- n
wards to define an for all integers n. Since a−1 = 2,
α and β are conjugate in p; consequently,
n n
√ n
√ equality α =
the
−β in Fq2 means that α = c 3, β = −c 3 for some c ∈
we may see by induction that a−n = an for all n. For
F p . But then −3c2 = α n β n = 1 in Fq and hence in F p , which
contradicts p ≡ 2 (mod 3) by quadratic reciprocity.
Saturday, December 5, 2015
A1 Let A and B be points on the same branch of the hyper- four numbers off the list. Repeat with the three smallest
bola xy = 1. Suppose that P is a point lying between remaining numbers 4, 5, 7 and their sum 16. Continue
A and B on this hyperbola, such that the area of the tri- in this way, crossing off the three smallest remaining
angle APB is as large as possible. Show that the re- numbers and their sum, and consider the sequence of
gion bounded by the hyperbola and the chord AP has sums produced: 6, 16, 27, 36, . . . . Prove or disprove that
the same area as the region bounded by the hyperbola there is some number in the sequence whose base 10
and the chord PB. representation ends with 2015.
A2 Let a0 = 1, a1 = 2, and an = 4an−1 − an−2 for n ≥ 2. B3 Let S be the set of all 2 × 2 real matrices
Find an odd prime factor of a2015 .
a b
M=
A3 Compute c d
2015 2015
! whose entries a, b, c, d (in that order) form an arithmetic
2πiab/2015 progression. Find all matrices M in S for which there is
log2 ∏ ∏ (1 + e )
a=1 b=1 some integer k > 1 such that M k is also in S.
Here i is the imaginary unit (that is, i2 = −1). B4 Let T be the set of all triples (a, b, c) of positive integers
for which there exist triangles with side lengths a, b, c.
A4 For each real number x, let Express
1 2a
f (x) = ∑ n
, ∑
n∈Sx 2 3b 5c
(a,b,c)∈T
where Sx is the set of positive integers n for which bnxc as a rational number in lowest terms.
is even. What is the largest real number L such that
f (x) ≥ L for all x ∈ [0, 1)? (As usual, bzc denotes the B5 Let Pn be the number of permutations π of {1, 2, . . . , n}
greatest integer less than or equal to z.) such that
A5 Let q be an odd positive integer, and let Nq denote |i − j| = 1 implies |π(i) − π( j)| ≤ 2
the number of integers a such that 0 < a < q/4 and
gcd(a, q) = 1. Show that Nq is odd if and only if q is for all i, j in {1, 2, . . . , n}. Show that for n ≥ 2, the quan-
of the form pk with k a positive integer and p a prime tity
congruent to 5 or 7 modulo 8.
Pn+5 − Pn+4 − Pn+3 + Pn
A6 Let n be a positive integer. Suppose that A, B, and M are
n×n matrices with real entries such that AM = MB, and does not depend on n, and find its value.
such that A and B have the same characteristic polyno-
mial. Prove that det(A − MX) = det(B − XM) for every B6 For each positive integer k, let A(k)√ be the number of
n × n matrix X with real entries. odd divisors of k in the interval [1, 2k). Evaluate
∞
B1 Let f be a three times differentiable function (defined A(k)
on R and real-valued) such that f has at least five dis- ∑ (−1)k−1 k
.
k=1
tinct real zeros. Prove that f + 6 f 0 + 12 f 00 + 8 f 000 has at
least two distinct real zeros.
B2 Given a list of the positive integers 1, 2, 3, 4, . . . , take the
first three numbers 1, 2, 3 and their sum 6 and cross all
, Solutions to the 76th William Lowell Putnam Mathematical Competition
Saturday, December 5, 2015
Manjul Bhargava, Kiran Kedlaya, and Lenny Ng
A1 First solution: Without loss of generality, assume that any integer m and any prime p dividing am , p also di-
A and B lie in the first quadrant with A = (t1 , 1/t1 ), B = vides a−m ; on the other hand, p cannot divide a−m+1 ,
(t2 , 1/t2 ), and t1 < t2 . If P = (t, 1/t) with t1 ≤ t ≤ t2 , as otherwise p would also divide a−m+2 , . . . , a0 = 1, a
then the area of triangle APB is contradiction. We can thus find an integer k such that
am+1 ≡ ka−m+1 (mod p); by induction on n, we see
1 1 1 1 t2 − t1 that an ≡ kan−2m (mod p) for all n. In particular, if k is
t1 t t2 = (t1 + t2 − t − t1t2 /t). odd, then p also divides akm ; we thus conclude (again)
2 1/t 1/t 1/t 2t1t2
1 2 that a2015 is divisible by a5 = 362 and thus by 181.
Remark: Although it was not needed in the solution,
When t1 ,t2 are fixed, this is maximized when t + t1t2 /t
we note in passing that if an ≡ 0 (mod p), then a2n+k ≡
is minimized,
√ which by AM-GM exactly holds when
−ak (mod p) for all k.
t = t1t2 .
Remark: One can find other odd prime factors of a2015
The line AP is given by y = t1 +t−x tt1 , and so the area of in the same manner. For example, a2015 is divisible by
the region bounded by the hyperbola and AP is each of the following quantities. (The prime factoriza-
Z t tions were computed using the Magma computer algebra
t1 + t − x 1 t t1 t
− dx = − − log , system.)
t1 tt 1 x 2t 1 2t t1
√ a13 = 2 × 6811741
2 −t1
which at t = t1t2 is equal to 2t√
p
t1 t2 − log( t2 /t1 ). a31 = 2 × 373 × 360250962984637
Similarly, the area of the region bounded by the√hyper-
bola and PB is 2t t2
− 2tt 2 − log tt2 , which at t = t1t2 is a5·13 = 2 × 181 × 6811741
2 −t1 × 3045046274679316654761356161
also 2t√
p
t t − log( t2 /t1 ), as desired.
12
a5·31 = 1215497709121 × 28572709494917432101
Second solution: For any λ > 0, the map (x, y) 7→
× 13277360555506179816997827126375881581
(λ x, λ −1 y) preserves both areas and the hyperbola xy =
1. We may thus rescale the picture so that A, B are sym- a13·31 = 2 × 373 × 193441 × 6811741 × 360250962984637
metric across the line y = x, with A above the line. As × 16866100753000669
P moves from A to B, the area of APB increases until P × 79988387992470656916594531961 × p156
passes through the point (1, 1), then decreases. Conse-
quently, P = (1, 1) achieves the maximum area, and the where p156 is a prime of 156 decimal digits. Dividing
desired equality is obvious by symmetry. Alternatively, a2015 by the product of the primes appearing in this list
since the hyperbola is convex, the maximum is uniquely yields a number N of 824 decimal digits which is defi-
achieved at the point where the tangent line is parallel nitely not prime, because 2N 6≡ 2 (mod N), but whose
to AB, and by symmetry that point is P. prime factorization we have been unable to establish.
Note that N is larger than a 2048-bit RSA modulus, so
A2 First solution: One possible√answer is 181. √ nBy in- the difficulty of factoring it is not surprising.
duction, we have an = ((2 + 3)n + (2 − √ 3) )/2 =
(α n √
+ β n )/2 for all n, where α = 2 + 3 and β = One thing we can show is that each prime factor of N is
congruent to 1 modulo 6 × 2015 = 12090, thanks to the
2 − 3. Now note that if k is an odd positive integer
kn +β kn following lemma.
and an 6= 0, then aaknn = αα n +β n =α
(k−1)n −α (k−2)n β n +
· · · − α n β (k−2)n + β (k−1)n . This expression is both ra- Lemma. Let n be an odd integer. Then any odd prime factor
tional√(because an and akn are integers) and of the form p of an which does not divide am for any divisor m of n is
a + b 3 for some integers a, b by the expressions for congruent to 1 modulo lcm(6, n). (By either solution of the
α, β ; it follows that it must be an integer, and so akn is original problem, p also does not divide am for any positive
divisible by an . Applying this to n = 5 and k = 403, we integer m < n.)
find that a2015 is divisible by a5 = 362 and thus by 181. √
Proof. We first check that p ≡ 1 (mod 3). In Fq = F p ( 3)
Second solution: By rewriting the formula for an as we have (α/β )n ≡ −1. If p ≡ 2 (mod 3), then q = p2 and
an−2 = 4an−1 − an , we may extend the sequence back- n
wards to define an for all integers n. Since a−1 = 2,
α and β are conjugate in p; consequently,
n n
√ n
√ equality α =
the
−β in Fq2 means that α = c 3, β = −c 3 for some c ∈
we may see by induction that a−n = an for all n. For
F p . But then −3c2 = α n β n = 1 in Fq and hence in F p , which
contradicts p ≡ 2 (mod 3) by quadratic reciprocity.
