The 75th William Lowell Putnam Mathematical Competition
Saturday, December 6, 2014
A1 Prove that every nonzero coefficient of the Taylor series B2 Suppose that f is a function on the interval [1, 3] such
of that −1 ≤ f (x) ≤ 1 for all x and 13 f (x) dx = 0. How
R
large can 13 f (x)
R
(1 − x + x2 )ex x dx be?
B3 Let A be an m × n matrix with rational entries. Sup-
about x = 0 is a rational number whose numerator (in pose that there are at least m + n distinct prime numbers
lowest terms) is either 1 or a prime number. among the absolute values of the entries of A. Show that
the rank of A is at least 2.
A2 Let A be the n × n matrix whose entry in the i-th row
and j-th column is B4 Show that for each positive integer n, all the roots of the
polynomial
1
min(i, j) n
∑ 2k(n−k) xk
for 1 ≤ i, j ≤ n. Compute det(A). k=0
A3 Let a0 = 5/2 and ak = a2k−1 − 2 for k ≥ 1. Compute are real numbers.
∞ B5 In the 75th annual Putnam Games, participants compete
1 at mathematical games. Patniss and Keeta play a game
∏ 1 −
k=0 ak in which they take turns choosing an element from the
group of invertible n × n matrices with entries in the
in closed form. field Z/pZ of integers modulo p, where n is a fixed
A4 Suppose X is a random variable that takeson only non- positive integer and p is a fixed prime number. The
2 rules of the game are:
3 integer values, with E [X] = 1, E X = 2, and
negative
E X = 5. (Here E [y] denotes the expectation of the (1) A player cannot choose an element that has been
random variable Y .) Determine the smallest possible chosen by either player on any previous turn.
value of the probability of the event X = 0.
(2) A player can only choose an element that com-
A5 Let mutes with all previously chosen elements.
(3) A player who cannot choose an element on his/her
Pn (x) = 1 + 2x + 3x2 + · · · + nxn−1 . turn loses the game.
Prove that the polynomials Pj (x) and Pk (x) are relatively Patniss takes the first turn. Which player has a winning
prime for all positive integers j and k with j 6= k. strategy? (Your answer may depend on n and p.)
A6 Let n be a positive integer. What is the largest k B6 Let f : [0, 1] → R be a function for which there exists a
for which there exist n × n matrices M1 , . . . , Mk and constant K > 0 such that | f (x) − f (y)| ≤ K |x − y| for all
N1 , . . . , Nk with real entries such that for all i and j, the x, y ∈ [0, 1]. Suppose also that for each rational number
matrix product Mi N j has a zero entry somewhere on its r ∈ [0, 1], there exist integers a and b such that f (r) =
diagonal if and only if i 6= j? a + br. Prove that there exist finitely many intervals
I1 , . . . , InSsuch that f is a linear function on each Ii and
B1 A base 10 over-expansion of a positive integer N is an [0, 1] = ni=1 Ii .
expression of the form
N = dk 10k + dk−1 10k−1 + · · · + d0 100
with dk 6= 0 and di ∈ {0, 1, 2, . . . , 10} for all i. For
instance, the integer N = 10 has two base 10 over-
expansions: 10 = 10 · 100 and the usual base 10 expan-
sion 10 = 1 · 101 + 0 · 100 . Which positive integers have
a unique base 10 over-expansion?
, Solutions to the 75th William Lowell Putnam Mathematical Competition
Saturday, December 6, 2014
Kiran Kedlaya and Lenny Ng
A1 The coefficient of xn in the Taylor series of (1 − x + For example, for n = 5,
x2 )ex for n = 0, 1, 2 is 1, 0, 12 , respectively. For n ≥ 3,
the coefficient of xn is −1 2 0 0 0
2 −8 6 0 0
1 1 1 1 − n + n(n − 1) B= 0
6 −18 12 0 .
− + =
n! (n − 1)! (n − 2)! n! 0 0 12 −32 20
n−1 0 0 0 20 −20
= .
n(n − 2)!
Let C denote the matrix obtained from B by replacing
If n − 1 is prime, then the lowest-terms numerator is the bottom-right entry with −2n2 (for consistency with
clearly either 1 or the prime n − 1 (and in fact the latter, the rest of the diagonal). Expanding in minors along
since n−1 is relatively prime to n and to (n−2)!). If n− the bottom row produces a second-order recursion for
1 is composite, either it can be written as ab for some det(C) solving to det(C) = (−1)n (n!)2 ; a similar ex-
a 6= b, in which case both a and b appear separately in pansion then yields det(B) = (−1)n−1 n!(n − 1)!.
(n − 2)! and so the numerator is 1, or n − 1 = p2 for Remark: This problem and solution are due to one of
some prime p, in which case p appears in (n − 2)! and us (Kedlaya). The statement appears in the comments
so the numerator is either 1 or p. (In the latter case, on sequence A010790 (i.e., the sequence (n − 1)!n!) in
the numerator is actually 1 unless p = 2, as in all other the On-Line Encyclopedia of Integer Sequences (http:
cases both p and 2p appear in (n − 2)!.) //oeis.org), attributed to Benoit Cloitre in 2002.
A2 Let v1 , . . . , vn denote the rows of A. The determinant is A3 First solution: Using the identity
unchanged if we replace vn by vn − vn−1 , and then vn−1
by vn−1 − vn−2 , and so forth, eventually replacing vk by (x + x−1 )2 − 2 = x2 + x−2 ,
vk − vk−1 for k ≥ 2. Since vk−1 and vk agree in their first
k k
k − 1 entries, and the k-th entry of vk − vk−1 is 1k − k−1 1
, we may check by induction on k that ak = 22 + 2−2 ; in
the result of these row operations is an upper triangular particular, the product is absolutely convergent. Using
matrix with diagonal entries 1, 21 −1, 31 − 12 , . . . , n1 − n−1
1
. the identities
The determinant is then
x2 + 1 + x−2
n
1 1
n
−1
= x − 1 + x−1 ,
− = x + 1 + x−1
∏ k−1 ∏
k=2 k k=2 k(k − 1) x2 − x−2
= x + x−1 ,
(−1)n−1 x − x−1
= .
(n − 1)!n! we may telescope the product to obtain
Note that a similar calculation can be made whenever k k
22 − 1 + 2−2
∞ ∞
A has the form Ai j = min{ai , a j } for any monotone se- 1
∏ 1 − = ∏ 2k −2k
quence a1 , . . . , an . Note also that the standard Gaussian k=0 ak k=0 2 + 2
elimination algorithm leads to the same upper triangu- k+1 k+1 k k
∞
22 + 1 + 2−2 22 − 2−2
lar matrix, but the nonstandard order of operations used =∏ · −k−1
2k −2k k+1
22 − 22
here makes the computations somewhat easier. k=0 2 + 1 + 2
0 0
Remark: The inverse of A can be identified explicitly: 22 − 2−2 3
for n ≥ 2, it is the matrix B given by = 0 0 = .
2
2 +1+2 −2 7
−1 i= j=1 Second solution: (by Catalin Zara) In this solution, we
2
−2i
1<i= j<n do not use the explicit formula for ak . We instead note
Bi j = −(n − 1)n i = j = n first that the ak form an increasing sequence which can-
ij |i − j| = 1 not approach a finite limit (since the equation L = L2 −2
has no real solution L > 2), and is thus unbounded. Us-
0 otherwise.
ing the identity
ak+1 + 1 = (ak − 1)(ak + 1),
Saturday, December 6, 2014
A1 Prove that every nonzero coefficient of the Taylor series B2 Suppose that f is a function on the interval [1, 3] such
of that −1 ≤ f (x) ≤ 1 for all x and 13 f (x) dx = 0. How
R
large can 13 f (x)
R
(1 − x + x2 )ex x dx be?
B3 Let A be an m × n matrix with rational entries. Sup-
about x = 0 is a rational number whose numerator (in pose that there are at least m + n distinct prime numbers
lowest terms) is either 1 or a prime number. among the absolute values of the entries of A. Show that
the rank of A is at least 2.
A2 Let A be the n × n matrix whose entry in the i-th row
and j-th column is B4 Show that for each positive integer n, all the roots of the
polynomial
1
min(i, j) n
∑ 2k(n−k) xk
for 1 ≤ i, j ≤ n. Compute det(A). k=0
A3 Let a0 = 5/2 and ak = a2k−1 − 2 for k ≥ 1. Compute are real numbers.
∞ B5 In the 75th annual Putnam Games, participants compete
1 at mathematical games. Patniss and Keeta play a game
∏ 1 −
k=0 ak in which they take turns choosing an element from the
group of invertible n × n matrices with entries in the
in closed form. field Z/pZ of integers modulo p, where n is a fixed
A4 Suppose X is a random variable that takeson only non- positive integer and p is a fixed prime number. The
2 rules of the game are:
3 integer values, with E [X] = 1, E X = 2, and
negative
E X = 5. (Here E [y] denotes the expectation of the (1) A player cannot choose an element that has been
random variable Y .) Determine the smallest possible chosen by either player on any previous turn.
value of the probability of the event X = 0.
(2) A player can only choose an element that com-
A5 Let mutes with all previously chosen elements.
(3) A player who cannot choose an element on his/her
Pn (x) = 1 + 2x + 3x2 + · · · + nxn−1 . turn loses the game.
Prove that the polynomials Pj (x) and Pk (x) are relatively Patniss takes the first turn. Which player has a winning
prime for all positive integers j and k with j 6= k. strategy? (Your answer may depend on n and p.)
A6 Let n be a positive integer. What is the largest k B6 Let f : [0, 1] → R be a function for which there exists a
for which there exist n × n matrices M1 , . . . , Mk and constant K > 0 such that | f (x) − f (y)| ≤ K |x − y| for all
N1 , . . . , Nk with real entries such that for all i and j, the x, y ∈ [0, 1]. Suppose also that for each rational number
matrix product Mi N j has a zero entry somewhere on its r ∈ [0, 1], there exist integers a and b such that f (r) =
diagonal if and only if i 6= j? a + br. Prove that there exist finitely many intervals
I1 , . . . , InSsuch that f is a linear function on each Ii and
B1 A base 10 over-expansion of a positive integer N is an [0, 1] = ni=1 Ii .
expression of the form
N = dk 10k + dk−1 10k−1 + · · · + d0 100
with dk 6= 0 and di ∈ {0, 1, 2, . . . , 10} for all i. For
instance, the integer N = 10 has two base 10 over-
expansions: 10 = 10 · 100 and the usual base 10 expan-
sion 10 = 1 · 101 + 0 · 100 . Which positive integers have
a unique base 10 over-expansion?
, Solutions to the 75th William Lowell Putnam Mathematical Competition
Saturday, December 6, 2014
Kiran Kedlaya and Lenny Ng
A1 The coefficient of xn in the Taylor series of (1 − x + For example, for n = 5,
x2 )ex for n = 0, 1, 2 is 1, 0, 12 , respectively. For n ≥ 3,
the coefficient of xn is −1 2 0 0 0
2 −8 6 0 0
1 1 1 1 − n + n(n − 1) B= 0
6 −18 12 0 .
− + =
n! (n − 1)! (n − 2)! n! 0 0 12 −32 20
n−1 0 0 0 20 −20
= .
n(n − 2)!
Let C denote the matrix obtained from B by replacing
If n − 1 is prime, then the lowest-terms numerator is the bottom-right entry with −2n2 (for consistency with
clearly either 1 or the prime n − 1 (and in fact the latter, the rest of the diagonal). Expanding in minors along
since n−1 is relatively prime to n and to (n−2)!). If n− the bottom row produces a second-order recursion for
1 is composite, either it can be written as ab for some det(C) solving to det(C) = (−1)n (n!)2 ; a similar ex-
a 6= b, in which case both a and b appear separately in pansion then yields det(B) = (−1)n−1 n!(n − 1)!.
(n − 2)! and so the numerator is 1, or n − 1 = p2 for Remark: This problem and solution are due to one of
some prime p, in which case p appears in (n − 2)! and us (Kedlaya). The statement appears in the comments
so the numerator is either 1 or p. (In the latter case, on sequence A010790 (i.e., the sequence (n − 1)!n!) in
the numerator is actually 1 unless p = 2, as in all other the On-Line Encyclopedia of Integer Sequences (http:
cases both p and 2p appear in (n − 2)!.) //oeis.org), attributed to Benoit Cloitre in 2002.
A2 Let v1 , . . . , vn denote the rows of A. The determinant is A3 First solution: Using the identity
unchanged if we replace vn by vn − vn−1 , and then vn−1
by vn−1 − vn−2 , and so forth, eventually replacing vk by (x + x−1 )2 − 2 = x2 + x−2 ,
vk − vk−1 for k ≥ 2. Since vk−1 and vk agree in their first
k k
k − 1 entries, and the k-th entry of vk − vk−1 is 1k − k−1 1
, we may check by induction on k that ak = 22 + 2−2 ; in
the result of these row operations is an upper triangular particular, the product is absolutely convergent. Using
matrix with diagonal entries 1, 21 −1, 31 − 12 , . . . , n1 − n−1
1
. the identities
The determinant is then
x2 + 1 + x−2
n
1 1
n
−1
= x − 1 + x−1 ,
− = x + 1 + x−1
∏ k−1 ∏
k=2 k k=2 k(k − 1) x2 − x−2
= x + x−1 ,
(−1)n−1 x − x−1
= .
(n − 1)!n! we may telescope the product to obtain
Note that a similar calculation can be made whenever k k
22 − 1 + 2−2
∞ ∞
A has the form Ai j = min{ai , a j } for any monotone se- 1
∏ 1 − = ∏ 2k −2k
quence a1 , . . . , an . Note also that the standard Gaussian k=0 ak k=0 2 + 2
elimination algorithm leads to the same upper triangu- k+1 k+1 k k
∞
22 + 1 + 2−2 22 − 2−2
lar matrix, but the nonstandard order of operations used =∏ · −k−1
2k −2k k+1
22 − 22
here makes the computations somewhat easier. k=0 2 + 1 + 2
0 0
Remark: The inverse of A can be identified explicitly: 22 − 2−2 3
for n ≥ 2, it is the matrix B given by = 0 0 = .
2
2 +1+2 −2 7
−1 i= j=1 Second solution: (by Catalin Zara) In this solution, we
2
−2i
1<i= j<n do not use the explicit formula for ak . We instead note
Bi j = −(n − 1)n i = j = n first that the ak form an increasing sequence which can-
ij |i − j| = 1 not approach a finite limit (since the equation L = L2 −2
has no real solution L > 2), and is thus unbounded. Us-
0 otherwise.
ing the identity
ak+1 + 1 = (ak − 1)(ak + 1),
