The 77th William Lowell Putnam Mathematical Competition
Saturday, December 3, 2016
A1 Find the smallest positive integer j such that for every A6 Find the smallest constant C such that for every real
polynomial p(x) with integer coefficients and for every polynomial P(x) of degree 3 that has a root in the in-
integer k, the integer terval [0, 1],
dj
Z 1
p( j) (k) = p(x) |P(x)| dx ≤ C max |P(x)| .
dx j x=k 0 x∈[0,1]
(the j-th derivative of p(x) at k) is divisible by 2016. B1 Let x0 , x1 , x2 , . . . be the sequence such that x0 = 1 and
A2 Given a positive integer n, let M(n) be the largest inte- for n ≥ 0,
ger m such that
xn+1 = ln(exn − xn )
m m−1
> . (as usual, the function ln is the natural logarithm). Show
n−1 n that the infinite series
Evaluate x0 + x1 + x2 + · · ·
M(n)
lim . converges and find its sum.
n→∞ n
B2 Define a positive integer n to be squarish if either n is
A3 Suppose that f is a function from R to R such that itself a perfect square or the distance from n to the near-
est perfect square is a perfect square. For example, 2016
1
f (x) + f 1 − = arctan x is squarish, because the nearest perfect square to 2016
x is 452 = 2025 and 2025 − 2016 = 9 is a perfect square.
(Of the positive integers between 1 and 10, only 6 and
for all real x 6= 0. (As usual, y = arctan x means −π/2 < 7 are not squarish.)
y < π/2 and tan y = x.) Find
For a positive integer N, let S(N) be the number of
Z 1
squarish integers between 1 and N, inclusive. Find pos-
f (x) dx. itive constants α and β such that
0
S(N)
A4 Consider a (2m − 1) × (2n − 1) rectangular region, lim = β,
N→∞ N α
where m and n are integers such that m, n ≥ 4. This
region is to be tiled using tiles of the two types shown: or show that no such constants exist.
B3 Suppose that S is a finite set of points in the plane such
that the area of triangle 4ABC is at most 1 whenever A,
B, and C are in S. Show that there exists a triangle of
area 4 that (together with its interior) covers the set S.
B4 Let A be a 2n × 2n matrix, with entries chosen indepen-
(The dotted lines divide the tiles into 1 × 1 squares.) dently at random. Every entry is chosen to be 0 or 1,
The tiles may be rotated and reflected, as long as their each with probability 1/2. Find the expected value of
sides are parallel to the sides of the rectangular region. det(A − At ) (as a function of n), where At is the trans-
They must all fit within the region, and they must cover pose of A.
it completely without overlapping. B5 Find all functions f from the interval (1, ∞) to (1, ∞)
What is the minimum number of tiles required to tile with the following property: if x, y ∈ (1, ∞) and x2 ≤
the region? y ≤ x3 , then ( f (x))2 ≤ f (y) ≤ ( f (x))3 .
A5 Suppose that G is a finite group generated by the two B6 Evaluate
elements g and h, where the order of g is odd. Show
that every element of G can be written in the form
∞
(−1)k−1 ∞ 1
∑ k ∑ k2n + 1 .
k=1 n=0
gm1 hn1 gm2 hn2 · · · gmr hnr
with 1 ≤ r ≤ |G| and m1 , n1 , m2 , n2 , . . . , mr , nr ∈
{−1, 1}. (Here |G| is the number of elements of G.)
, Solutions to the 77th William Lowell Putnam Mathematical Competition
Saturday, December 3, 2016
Kiran Kedlaya and Lenny Ng
A1 The answer is j = 8. First suppose that j satisfies the We conclude that M(n) is the greatest integer strictly
given condition. For p(x) = x j , we have p( j) (x) = j! less than α(n), and thus that α(n) − 1 ≤ M(n) < α(n).
and thus j! is divisible by 2016. Since 2016 is divisible Now
by 25 and 7! is not, it follows that j ≥ 8. Conversely, we
√
q
claim that j = 8 works. Indeed, let p(x) = ∑nm=0 am xm α(n) 3 − 1
n + 5 − 2n + n12 3+ 5
be a polynomial with integer coefficients; then if k is lim = lim =
n→∞ n n→∞ 2 2
any integer,
√
3+ 5
n and similarly limn→∞ α(n)−1
n = 2 √, and so by the
p(8) (k) = ∑ m(m − 1) · · · (m − 7)am km−8 sandwich theorem, M(n)
limn→∞ n = 3+2 5 .
m=8
n
A3 The given functional equation, along with the same
m
= ∑ 8!am km−8 equation but with x replaced by x−1 1
m=8 8 x and 1−x respec-
tively, yields:
is divisible by 8! = 20 · 2016, and so p(8) (k) is divisible
1
by 2016. f (x) + f 1 − = tan−1 (x)
x
Remark: By the same reasoning, if one replaces 2016
x−1 1 −1 x − 1
in the problem by a general integer N, then the min- f +f = tan
imum value of j is the smallest one for which N di- x 1−x x
vides j!. This can be deduced from Pólya’s observation 1 −1 1
f + f (x) = tan .
that the set of integer-valued polynomials is the free Z- 1−x 1−x
module generated by the binomial polynomials nx for
n = 0, 1, . . . . That statement can be extended to polyno- Adding the first and third equations and subtracting the
mials evaluated on a subset of a Dedekind domain using second gives:
Bhargava’s method of P-orderings; we do not know if
this generalization can be adapted to the analogue of −1 −1 1 −1 x − 1
2 f (x) = tan (x) + tan − tan .
this problem, where one considers polynomials whose 1−x x
j-th derivatives take integral values on a prescribed sub-
set. Now tan−1 (t) + tan−1 (1/t) is equal to π/2 if t > 0 and
√ −π/2 if t < 0; it follows that for x ∈ (0, 1),
3+ 5
A2 The answer is Note that for m > n + 1, both bi-
2 .
2( f (x) + f (1 − x)) = tan−1 (x) + tan−1 (1/x)
nomial coefficients are nonzero and their ratio is
1
m m−1 m!n!(m − n − 1)! −1
+ tan (1 − x) + tan −1
/ = 1−x
n−1 n (m − 1)!(n − 1)!(m − n + 1)!
mn
= . −1 x − 1 −1 x
− tan + tan
(m − n + 1)(m − n) x x−1
π π π
Thus the condition n−1m
> m−1
is equivalent to (m − = + +
n 2 2 2
n + 1)(m − n) − mn < 0. The left hand side of this last 3π
inequality is a quadratic function of m with roots = .
2
√
3n − 1 + 5n2 − 2n + 1 Thus
α(n) = ,
√2
Z 1 Z 1
3π
3n − 1 − 5n2 − 2n + 1 4 f (x) dx = 2 ( f (x) + f (1 − x))dx =
β (n) = , 0 0 2
2
R1 3π
and finally 0 f (x) dx = 8 .
both of which are real since 5n2 − 2n + 1 = 4n2 + (n −
1)2 > 0; it follows that m satisfies the given inequality Remark: Once one has the formula for f (x), one can
if and only if β (n) <√
m < α(n). (Note in particular that also (with some effort) directly evaluate the integral of
since α(n)−β (n) = 5n2 − 2n + 1 > 1, there is always each summand over [0, 1] to obtain the same result. A
some integer m between β (n) and α(n).)
Saturday, December 3, 2016
A1 Find the smallest positive integer j such that for every A6 Find the smallest constant C such that for every real
polynomial p(x) with integer coefficients and for every polynomial P(x) of degree 3 that has a root in the in-
integer k, the integer terval [0, 1],
dj
Z 1
p( j) (k) = p(x) |P(x)| dx ≤ C max |P(x)| .
dx j x=k 0 x∈[0,1]
(the j-th derivative of p(x) at k) is divisible by 2016. B1 Let x0 , x1 , x2 , . . . be the sequence such that x0 = 1 and
A2 Given a positive integer n, let M(n) be the largest inte- for n ≥ 0,
ger m such that
xn+1 = ln(exn − xn )
m m−1
> . (as usual, the function ln is the natural logarithm). Show
n−1 n that the infinite series
Evaluate x0 + x1 + x2 + · · ·
M(n)
lim . converges and find its sum.
n→∞ n
B2 Define a positive integer n to be squarish if either n is
A3 Suppose that f is a function from R to R such that itself a perfect square or the distance from n to the near-
est perfect square is a perfect square. For example, 2016
1
f (x) + f 1 − = arctan x is squarish, because the nearest perfect square to 2016
x is 452 = 2025 and 2025 − 2016 = 9 is a perfect square.
(Of the positive integers between 1 and 10, only 6 and
for all real x 6= 0. (As usual, y = arctan x means −π/2 < 7 are not squarish.)
y < π/2 and tan y = x.) Find
For a positive integer N, let S(N) be the number of
Z 1
squarish integers between 1 and N, inclusive. Find pos-
f (x) dx. itive constants α and β such that
0
S(N)
A4 Consider a (2m − 1) × (2n − 1) rectangular region, lim = β,
N→∞ N α
where m and n are integers such that m, n ≥ 4. This
region is to be tiled using tiles of the two types shown: or show that no such constants exist.
B3 Suppose that S is a finite set of points in the plane such
that the area of triangle 4ABC is at most 1 whenever A,
B, and C are in S. Show that there exists a triangle of
area 4 that (together with its interior) covers the set S.
B4 Let A be a 2n × 2n matrix, with entries chosen indepen-
(The dotted lines divide the tiles into 1 × 1 squares.) dently at random. Every entry is chosen to be 0 or 1,
The tiles may be rotated and reflected, as long as their each with probability 1/2. Find the expected value of
sides are parallel to the sides of the rectangular region. det(A − At ) (as a function of n), where At is the trans-
They must all fit within the region, and they must cover pose of A.
it completely without overlapping. B5 Find all functions f from the interval (1, ∞) to (1, ∞)
What is the minimum number of tiles required to tile with the following property: if x, y ∈ (1, ∞) and x2 ≤
the region? y ≤ x3 , then ( f (x))2 ≤ f (y) ≤ ( f (x))3 .
A5 Suppose that G is a finite group generated by the two B6 Evaluate
elements g and h, where the order of g is odd. Show
that every element of G can be written in the form
∞
(−1)k−1 ∞ 1
∑ k ∑ k2n + 1 .
k=1 n=0
gm1 hn1 gm2 hn2 · · · gmr hnr
with 1 ≤ r ≤ |G| and m1 , n1 , m2 , n2 , . . . , mr , nr ∈
{−1, 1}. (Here |G| is the number of elements of G.)
, Solutions to the 77th William Lowell Putnam Mathematical Competition
Saturday, December 3, 2016
Kiran Kedlaya and Lenny Ng
A1 The answer is j = 8. First suppose that j satisfies the We conclude that M(n) is the greatest integer strictly
given condition. For p(x) = x j , we have p( j) (x) = j! less than α(n), and thus that α(n) − 1 ≤ M(n) < α(n).
and thus j! is divisible by 2016. Since 2016 is divisible Now
by 25 and 7! is not, it follows that j ≥ 8. Conversely, we
√
q
claim that j = 8 works. Indeed, let p(x) = ∑nm=0 am xm α(n) 3 − 1
n + 5 − 2n + n12 3+ 5
be a polynomial with integer coefficients; then if k is lim = lim =
n→∞ n n→∞ 2 2
any integer,
√
3+ 5
n and similarly limn→∞ α(n)−1
n = 2 √, and so by the
p(8) (k) = ∑ m(m − 1) · · · (m − 7)am km−8 sandwich theorem, M(n)
limn→∞ n = 3+2 5 .
m=8
n
A3 The given functional equation, along with the same
m
= ∑ 8!am km−8 equation but with x replaced by x−1 1
m=8 8 x and 1−x respec-
tively, yields:
is divisible by 8! = 20 · 2016, and so p(8) (k) is divisible
1
by 2016. f (x) + f 1 − = tan−1 (x)
x
Remark: By the same reasoning, if one replaces 2016
x−1 1 −1 x − 1
in the problem by a general integer N, then the min- f +f = tan
imum value of j is the smallest one for which N di- x 1−x x
vides j!. This can be deduced from Pólya’s observation 1 −1 1
f + f (x) = tan .
that the set of integer-valued polynomials is the free Z- 1−x 1−x
module generated by the binomial polynomials nx for
n = 0, 1, . . . . That statement can be extended to polyno- Adding the first and third equations and subtracting the
mials evaluated on a subset of a Dedekind domain using second gives:
Bhargava’s method of P-orderings; we do not know if
this generalization can be adapted to the analogue of −1 −1 1 −1 x − 1
2 f (x) = tan (x) + tan − tan .
this problem, where one considers polynomials whose 1−x x
j-th derivatives take integral values on a prescribed sub-
set. Now tan−1 (t) + tan−1 (1/t) is equal to π/2 if t > 0 and
√ −π/2 if t < 0; it follows that for x ∈ (0, 1),
3+ 5
A2 The answer is Note that for m > n + 1, both bi-
2 .
2( f (x) + f (1 − x)) = tan−1 (x) + tan−1 (1/x)
nomial coefficients are nonzero and their ratio is
1
m m−1 m!n!(m − n − 1)! −1
+ tan (1 − x) + tan −1
/ = 1−x
n−1 n (m − 1)!(n − 1)!(m − n + 1)!
mn
= . −1 x − 1 −1 x
− tan + tan
(m − n + 1)(m − n) x x−1
π π π
Thus the condition n−1m
> m−1
is equivalent to (m − = + +
n 2 2 2
n + 1)(m − n) − mn < 0. The left hand side of this last 3π
inequality is a quadratic function of m with roots = .
2
√
3n − 1 + 5n2 − 2n + 1 Thus
α(n) = ,
√2
Z 1 Z 1
3π
3n − 1 − 5n2 − 2n + 1 4 f (x) dx = 2 ( f (x) + f (1 − x))dx =
β (n) = , 0 0 2
2
R1 3π
and finally 0 f (x) dx = 8 .
both of which are real since 5n2 − 2n + 1 = 4n2 + (n −
1)2 > 0; it follows that m satisfies the given inequality Remark: Once one has the formula for f (x), one can
if and only if β (n) <√
m < α(n). (Note in particular that also (with some effort) directly evaluate the integral of
since α(n)−β (n) = 5n2 − 2n + 1 > 1, there is always each summand over [0, 1] to obtain the same result. A
some integer m between β (n) and α(n).)
