Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

The 75th William Lowell Putnam Mathematical Competition
Saturday, December 6, 2014

A1 Prove that every nonzero coefficient of the Taylor series
of
(1 − x + x2 )ex
about x = 0 is a rational number whose numerator (in
lowest terms) is either 1 or a prime number
...
How
R
large can 13 f (x)
x dx be?
B3 Let A be an m × n matrix with rational entries
...
Show that
the rank of A is at least 2
...
Compute det(A)
...
Compute


1
1
−
∏
ak
k=0
∞

in closed form
...
(Here E [y] denotes the expectation of the
random variable Y
...

A5 Let
Pn (x) = 1 + 2x + 3x2 + · · · + nxn−1
...

B5 In the 75th annual Putnam Games, participants compete
at mathematical games
...
The
rules of the game are:
(1) A player cannot choose an element that has been
chosen by either player on any previous turn
...

(3) A player who cannot choose an element on his/her
turn loses the game
...


Patniss takes the first turn
...
)

A6 Let n be a positive integer
...
, Mk and
N1 ,
...
Suppose also that for each rational number
r ∈ [0, 1], there exist integers a and b such that f (r) =
a + br
...
, InSsuch that f is a linear function on each Ii and
[0, 1] = ni=1 Ii
...
, 10} for all i
...
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 +
x2 )ex for n = 0, 1, 2 is 1, 0, 12 , respectively
...

n(n − 2)!

Let C denote the matrix obtained from B by replacing
the bottom-right entry with −2n2 (for consistency with
the rest of the diagonal)
...


If n − 1 is prime, then the lowest-terms numerator is
clearly either 1 or the prime n − 1 (and in fact the latter,
since n−1 is relatively prime to n and to (n−2)!)
...
(In the latter case,
the numerator is actually 1 unless p = 2, as in all other
cases both p and 2p appear in (n − 2)!
...
, vn denote the rows of A
...
Since vk−1 and vk agree in their first
1
,
k − 1 entries, and the k-th entry of vk − vk−1 is 1k − k−1
the result of these row operations is an upper triangular
1
matrix with diagonal entries 1, 21 −1, 31 − 12 ,
...

The determinant is then


n 
n 
1
1
−1
−
=
∏
∏
k−1
k=2 k
k=2 k(k − 1)
=

Remark: This problem and solution are due to one of
us (Kedlaya)
...
e
...
org), attributed to Benoit Cloitre in 2002
...


k

we may check by induction on k that ak = 22 + 2−2 ; in
particular, the product is absolutely convergent
...

(n − 1)!n!

Note that a similar calculation can be made whenever
A has the form Ai j = min{ai , a j } for any monotone sequence a1 ,
...
Note also that the standard Gaussian
elimination algorithm leads to the same upper triangular matrix, but the nonstandard order of operations used
here makes the computations somewhat easier
...

0 12 −32 20 
0
0
20 −20

we may telescope the product to obtain


k
k
∞
1
22 − 1 + 2−2
1
−
=
∏
∏ 2k −2k
ak
k=0
k=0 2 + 2
∞

k+1

k+1

22 + 1 + 2−2
2k
−2k
k=0 2 + 1 + 2
∞

=∏

0

k

·

k

22 − 2−2
k+1
−k−1
22 − 22

0

22 − 2−2
3
= 0

...
We instead note
first that the ak form an increasing sequence which cannot approach a finite limit (since the equation L = L2 −2
has no real solution L > 2), and is thus unbounded
...

k=0

note crucially that these equations also hold for n ∈
{0, 1}
...

3
Hence
n



1
3 an+1 + 1
1
−
= q
∏
a
7 a2 − 4
k
k=0
n+1
tends to
infinity
...
On the other
hand, for all t ≥ 0 we have
f 000 (t) = (2 log |w|)3 |w|2t > 0,
so by Rolle’s theorem, the equation f (3−k) (t) = 0 has at
most k distinct solutions for k = 0, 1, 2, 3
...

Remark: By similar reasoning, an equation of the form
ex = P(x) in which P is a real polynomial of degree
d has at most d + 1 real solutions
...

Second solution: (by Noam Elkies) We recall a result
commonly known as the Enestr¨om-Kakeya theorem
...

First solution: Let an = P(X = n); we want the mink
imum value for a0
...
Now define f (n) = 11n − 6n2 + n3 , and note
that f (0) = 0, f (1) = f (2) = f (3) = 6, and f (n) > 6
for n ≥ 4; thus 4 = 11S1 − 6S2 + S3 = ∑∞
n=1 f (n)an ≥
∞
∞
6 ∑n=1 an
...

Equality is achieved when a0 = 31 , a1 = 12 , a3 = 16 , and
an = 0 for all other n, and so the answer is 31
...
Then every root z ∈ C of f satisfies |z| ≤ 1
...


∞

G(z) =

We compute that G(1) = G0 (1) = G00 (1) = G000 (1) = 1
...

2!
3!
4!
1 0000
24 G (c)

for some c ∈ [0, 1]
...
As in the
first solution, we see that this bound is best possible
...
Note that z cannot be a nonnegative
real number or else Pi (z), Pj (z) > 0; we may put w =
z−1 6= 0, 1
...
If f (z) = 0, then we may rearrange the equality 0 =
f (z)(z − 1) to obtain

But if |z| > 1, then

∑ P(x = n)z
...
Let

wn = nw − n + 1;

|an zn+1 | ≤ (|an − an−1 | + · · · + |a1 − a0 |)|z|n ≤ |an zn |,
contradiction
...
Let
f (x) = a0 + a1 x + · · · + an xn
be a polynomial with positive real coefficients
...
, an−1 /an }
R = max{a0 /a1 ,
...

Proof
...
The bound |z| ≥ r follows by applying
the lemma to the reverse of the polynomial f (x/r)
...
We clearly cannot have j = i+1, as
then Pi (0) 6= 0 and so Pj (z) − Pi (z) = (i + 1)zi 6= 0; we
thus have j − i ≥ 2
...
On the other hand, by applying

3
Corollary 2 to (Pj (x) − Pi (x))/xi−1 , we see that |z| ≥
1
, contradiction
...
It dates back further to Example 3
...

London Math
...
(2) 33 (1986), 430–440, in which
the second solution is given
...

Remark: It seems likely that the individual polynomials Pk (x) are all irreducible, but this appears difficult to
prove
...


Remark: The reader may notice a strong similarity between this solution and the first solution
...

Remark: It is also possible to solve this problem using a p-adic valuation on the field of algebraic numbers in place of the complex absolute value;
however, this leads to a substantially more complicated solution
...
artofproblemsolving
...
php?f=80&t=616731
...
We first show that this
value can be achieved by an explicit construction
...
, en be the standard basis of Rn
...
, in ∈
{1,
...
,in be the matrix with row vectors
ei1 ,
...
,in be the transpose of Mi1 ,
...

Then Mi1 ,
...
, jn has k-th diagonal entry eik · e jk ,
proving the claim
...
Let V be the n-fold tensor product of Rn , i
...
, the vector space with orthonormal basis ei1 ⊗ · · · ⊗ ein for i1 ,
...
, n}
...


i1 ,
...
Hence the equation Pn (z)(1 − z) = 0 has no solutions with |z| ≥ 1 other than the trivial solution z = 1
...

Write z = u + iv; we may assume without loss of generality that v ≥ 0
...

One computes that for n ∈ R, Ez00 (n) < 0 if and only if
u+v−1
u−v−1

...
From this, it follows that the
equation Ez (n) = 0 can have at most one solution with
n > 0
...
One computes easily that mi · n j equals the product
of the diagonal entries of Mi N j , and so vanishes if and
only if i 6= j
...

i

Therefore the vectors m1 ,
...

Remark: Noam Elkies points out that similar argument
may be made in the case that the Mi are m × n matrices
and the N j are n × m matrices
...
If the usual base 10 expansion of N is
dk 10k + · · · + d0 100 and one of the digits is 0, then there
exists an i ≤ k − 1 such that di = 0 and di+1 > 0; then
we can replace di+1 10i+1 + (0)10i by (di+1 − 1)10i+1 +
(10)10i to obtain a second base 10 over-expansion
...
This holds by induction on the number of digits of N: if 1 ≤ N ≤ 9,
then the result is clear
...

Remark: Karl Mahlburg suggests an alternate proof of
uniqueness (due to Shawn Williams): write the usual
expansion N = dk 10k + · · · + d0 100 and suppose di 6= 0
for all i
...
To have M = N, we
must have l ≤ k; we may pad the expansion of M with
zeroes to force l = k
...
Moreover, there exists at least one index i with ei 6= 0, since
any index for which ci = 10 has this property
...
Using integration by parts, we obtain
Z 3
f (x)
1

x

dx =

1

≤

First solution: Let g(x) be 1 for 1 ≤ x ≤ 2 and −1
for 2 < x ≤ 3, and define h(x) = g(x) − f (x)
...
Now

1

x

Z 2
|h(x)|

dx −

Z 3
|h(x)|

dx
x
x
2
Z 2
Z 3
|h(x)|
|h(x)|
≥
dx −
dx = 0,
2
2
1
2
1

R 3 f (x)

x2

dx
dx +

Z 3
3−x

x2

2

dx

4
= log
...
g
...
)
B3 First solution: Assume by way of contradiction that A
has rank at most 1; in this case, we can find rational
numbers a1 ,
...
, bn such that Ai j = ai b j for
all i, j
...

Recall that any nonzero rational number q has a unique
prime factorization
q = ±2c1 3c2 5c3 · · ·

B2 In all solutions, we assume that the function f is integrable
...


Z 3
h(x)

Z 3
F(x)

R 3 g(x)

with exponents in Z
...

Note that |ai b j | is prime if and only if c(ai ) + c(b j ) has
one entry equal to 1 and all others equal to 0
...

Since g(x) achieves the upper bound, the answer is
log 34
...
But
that space evidently has dimension at most m + n − 1,
contradiction
...
We first recall the quick induction proof that
that a graph on k vertices with no cycles contains at
most k − 1 edges: for k = 1, the claim is trivially true
because there can be no edges
...
Removing the vertex v
and the edges incident to it leaves a disjoint union of d
different graphs, each having no cycles
...
, kd , by induction
the total number of edges in the original graph is at most
(k1 − 1) + · · · + (kd − 1) + d = k − 1
...

More precisely, we have f (x) = ∑n cn Hn (x) for some cn
R
with |c0 | + |c1 | + | · · · | ≤ 1
...

Thus
Z 3
1

4
( f (x)/x)dx = c0 g0 + c1 g1 + · · · ≤ 1 · g0 = log
...
Draw a bipartite graph whose vertices
correspond to the rows and columns of A, with an edge
joining a particular row and column if the entry where
they intersect has prime absolute value
...
Since

5
the graph is bipartite, this cycle must be of length 2k for
some integer k ≥ 2 (we cannot have k = 1 because the
graph has no repeated edges)
...
There must then
exist distinct prime numbers p1 ,
...
, |Akk | = p2k−1 , |A1k | = p2k
...
If we put ri = |Ai1 | and

c j = Ai j /A11 , we have
p1 · · · p2k = (r1 c1 )(r2 c1 ) · · · (rk ck )(r1 ck )
= (r1 c1 · · · rk ck )2 ,
which contradicts the existence of unique prime factorizations for positive rational numbers: the prime p1 occurs with exponent 1 on the left, but with some even
exponent on the right
...

B4 Define the polynomial fn (x) = ∑nk=0 2k(n−k) xk
...
For n ≥ 3, we show that
the quantities
fn (−2−n ), fn (−2−n+2 ),
...
, (−2n−2 , −2n ), forcing fn to have
as many distinct real roots as its degree
...
, n}, group the terms of fn (x) as
···
+ 2( j−5)(n− j+5) x j−5 + 2( j−4)(n− j+4) x j−4
+ 2( j−3)(n− j+3) x j−3 + 2( j−2)(n− j+2) x j−2
+ 2( j−1)(n− j+1) x j−1 + 2 j(n− j) x j + 2( j+1)(n− j−1) x j+1
+ 2( j+2)(n− j−2) x j+2 + 2( j+3)(n− j−3) x j+3
+ 2( j+4)(n− j−4) x j+4 + 2( j+5)(n− j−5) x j+5
···
...
When evaluating at x = −2−n+2 j , the trinomial evaluates to 0
...
In the binomials following the trinomial, the left-hand term dominates, so
again the contribution has sign (−1) j
...
Since n ≥ 3, there exists at least one contribution other than the trinomial,

so fn (−2−n+2 j ) has overall sign (−1) j , proving the
claimed alternation
...
Then each row is an alternating series whose sum carries the sign of (−1) j unless
it has only two terms
...

Remark: One of us (Kedlaya) received this problem
and solution from David Speyer in 2009 and submitted
it to the problem committee
...
We first analyze the analogous game
played using an arbitrary finite group G
...
At any
given point in the game, the set S of previously chosen elements is contained in Z(S)
...
In particular,
if the order of Z(S) is odd at some point, it remains
odd thereafter; conversely, if S contains an element of
even order, then the order of Z(S) remains even thereafter
...
g
...
In both cases, the win
is guaranteed no matter what moves follow
...
If p > 2, then Z(S) will always contain
the scalar matrix −1 of order 2, so the win for Keeta is
guaranteed
...
)
If p = 2, we establish the existence of g ∈ G such that
Z({g}) has odd order using the existence of an irreducible polynomial P(x) of degree n over Z/pZ (see
remark)
...

g=

...


...

0 0 · · · 1 −Pn−1
In particular, det(g) = (−1)n P0 6= 0, so g ∈ G
...
In particular, Z({g}) is of odd order, so Patniss has a winning strategy
...

Remark: We sketch two ways to verify the existence
of an irreducible polynomial of degree n over Z/pZ for
any positive integer n and any prime number p
...
The other
is to first establish the existence of a finite field F of
cardinality pn , e
...
, as the set of roots of the polynomial
n
x p −1 inside a splitting field, and then take the minimal
polynomial of a nonzero element of F over Z/pZ which
is a primitive (pn − 1)-st root of unity in F (which exist
because the multiplicative group of F contains at most
one cyclic subgroup of any given order)
...

One may also describe the preceding analysis in terms
of an identification of F as a Z/pZ-vector space with
the space of column vectors of length n
...
Any such endomorphism
is itself multiplication by an element of F, so Z({g})
is identified with the multiplicative group of F, whose
order is the odd number 2n − 1
...

For each positive integer n, define the n-th Farey sequence Fn as the sequence of rational numbers in [0, 1]
with denominators at most n
...
Namely, this is obvious
for n = 1 because F1 = 01 , 11
...
If s + s = n, then for m = r + r0 we
0
0
have rs < mn < rs0 and the pairs rs , mn and mn , rs0 satisfy the
0
desired conditions
...

Let fn : [0, 1] → R be the piecewise linear function
which agrees with f at each element of Fn and is linear
between any two consecutive elements of Fn
...
Since s f ( rs ), s0 f ( rs0 ) ∈
Z, we deduce first that
r0
r
b = ss0 ( f ( 0 ) − f ( ))
s
s
is an integer of absolute value at most K, and second
0
that both as = s f ( rs ) − br and as0 = s0 f ( rs0 ) − br0 are
integral
...

We now check that if n > 2K, then fn = fn−1
...

Define the integer t = n f ( mn ) − a0 n − b0 m
...

0
In order to have |b0 + st| , |b0 − s t| ≤ K, we must have
(s + s0 ) |t| ≤ 2K; since s + s0 = n > 2K, this is only possible if t = 0
...

It follows that for any n > 2K, we must have fn =
fn+1 = · · ·
...

Remark: The condition on f and K is called Lipschitz
continuity
...
In this
approach, the role of the Farey sequence may also be
played by the convergents of the continued fraction of x
(at least in the case where x is irrational)
...
Some related results can be proved
with the Lipschitz continuity condition replaced by suitable convexity conditions
...

Kedlaya and Philip Tynan, Detecting integral polyhedral functions, Confluentes Mathematici 1 (2009), 87–
109
...
Kedlaya and
Liang Xiao, Differential modules on p-adic polyannuli,
J
...
Math
...
,
669–671)

---

Title: The 75th William Lowell Putnam Mathematical Competition, 2014
Description: The William Lowell Putnam Mathematics Competition Is a North American math contest for college students, organized by the Mathematical Association of America (MAA). Each year on the first Saturday in December, several thousands US and Canadian students spend 6 hours (in two sittings) trying to solve 12 problems. This past papers content problems and solutions.

Buy These NotesPreview