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

---

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