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 77th William Lowell Putnam Mathematical Competition
Saturday, December 3, 2016

A1 Find the smallest positive integer j such that for every
polynomial p(x) with integer coefficients and for every
integer k, the integer


dj

p(x)
p( j) (k) =

j
dx
x=k

A6 Find the smallest constant C such that for every real
polynomial P(x) of degree 3 that has a root in the interval [0, 1],

(the j-th derivative of p(x) at k) is divisible by 2016
...
be the sequence such that x0 = 1 and
for n ≥ 0,

A2 Given a positive integer n, let M(n) be the largest integer m such that

 

m
m−1
>

...

x∈[0,1]

0

xn+1 = ln(exn − xn )
(as usual, the function ln is the natural logarithm)
...

n

A3 Suppose that f is a function from R to R such that


1
f (x) + f 1 −
= arctan x
x
for all real x 6= 0
...
) Find
Z 1

f (x) dx
...
This
region is to be tiled using tiles of the two types shown:

converges and find its sum
...
For example, 2016
is squarish, because the nearest perfect square to 2016
is 452 = 2025 and 2025 − 2016 = 9 is a perfect square
...
)
For a positive integer N, let S(N) be the number of
squarish integers between 1 and N, inclusive
...

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
...


(The dotted lines divide the tiles into 1 × 1 squares
...

They must all fit within the region, and they must cover
it completely without overlapping
...
Show
that every element of G can be written in the form
gm1 hn1 gm2 hn2 · · · gmr hnr
with 1 ≤ r ≤ |G| and m1 , n1 , m2 , n2 ,
...
(Here |G| is the number of elements of G
...
Every entry is chosen to be 0 or 1,
each with probability 1/2
...

B5 Find all functions f from the interval (1, ∞) to (1, ∞)
with the following property: if x, y ∈ (1, ∞) and x2 ≤
y ≤ x3 , then ( f (x))2 ≤ f (y) ≤ ( f (x))3
...

n=0
k=1
∞

Solutions to the 77th William Lowell Putnam Mathematical Competition
Saturday, December 3, 2016
Kiran Kedlaya and Lenny Ng

A1 The answer is j = 8
...
For p(x) = x j , we have p( j) (x) = j!
and thus j! is divisible by 2016
...
Conversely, we
claim that j = 8 works
...

Remark: By the same reasoning, if one replaces 2016
in the problem by a general integer N, then the minimum value of j is the smallest one for which N divides j!
...
That statement can be extended to polynomials evaluated on a subset of a Dedekind domain using
Bhargava’s method of P-orderings; we do not know if
this generalization can be adapted to the analogue of
this problem, where one considers polynomials whose
j-th derivatives take integral values on a prescribed subset
...


A2 The answer is
Note that for m > n + 1, both binomial coefficients are nonzero and their ratio is

 

m
m−1
m!n!(m − n − 1)!
/
=
n−1
n
(m − 1)!(n − 1)!(m − n + 1)!
mn
=

...
The left hand side of this last
inequality is a quadratic function of m with roots
√
3n − 1 + 5n2 − 2n + 1
α(n) =
,
√2
3n − 1 − 5n2 − 2n + 1
β (n) =
,
2
both of which are real since 5n2 − 2n + 1 = 4n2 + (n −
1)2 > 0; it follows that m satisfies the given inequality
if and only if β (n) <√
m < α(n)
...
)

We conclude that M(n) is the greatest integer strictly
less than α(n), and thus that α(n) − 1 ≤ M(n) < α(n)
...


=
and similarly limn→∞ α(n)−1
n
sandwich theorem,

so by the

A3 The given functional equation, along with the same
1
equation but with x replaced by x−1
x and 1−x respectively, yields:


1
= tan−1 (x)
f (x) + f 1 −
x






x−1
1
−1 x − 1
f
+f
= tan
x
1−x
x




1
1
−1
f
+ f (x) = tan

...

2 f (x) = tan (x) + tan
1−x
x
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),


2( f (x) + f (1 − x)) = tan−1 (x) + tan−1 (1/x)



1
−1
−1
+ tan (1 − x) + tan
1−x





x
−1 x − 1
−1
− tan
+ tan
x
x−1
π π π
= + +
2 2 2
3π
=

...


Remark: Once one has the formula for f (x), one can
also (with some effort) directly evaluate the integral of
each summand over [0, 1] to obtain the same result
...

A4 The minimum number of tiles is mn
...

It remains to show that we can cover any (2m − 1) ×
(2n − 1) rectangle with mn tiles when m, n ≥ 4
...
Thus if we
can cover a 7×7 square with 16 tiles, then we can do the
general (2m − 1) × (2n − 1) rectangle, by decomposing
this rectangle into a 7×7 square in the lower left corner,
along with m − 4 (2 × 7) rectangles to the right of the
square, and n − 4 ((2m − 1) × 2) rectangles above, and
tiling each of these rectangles separately, for a total of
16 + 4(m − 4) + m(n − 4) = mn tiles
...
We may thus construct a suitable covering by covering all but the center square with eight
2 × 3 rectangles, in such a way that we can attach the
center square to one of these rectangles to get a shape
that can be covered by two tiles
...
(Many other
solutions are possible
...
, mr , nr ∈ {−1, 1} for which
s = gm1 hn1 · · · gmr hnr
...
Since S is closed under the group operation and G is finite, S is also closed
under formation of inverses and contains the identity
element; that is, S is a subgroup of G
...

Since g is of odd order in G, g−2 is also a generator of
the cyclic subgroup containing g; it follows that g ∈ S
and hence h ∈ S
...

To complete the proof, we must now check that for each
s ∈ G, the smallest possible length of a representation of
s cannot exceed |G|
...
Set
si = gm1 hn1 · · · gmi hni

(i = 0,
...
Then
s = gm1 hn1 · · · gmi hni gm j+1 hn j+1 · · · gmr hnr
is another representation of s of length strictly less than
r, a contradiction
...
, sr instead of
s0 ,
...

Reinterpretation:
Note that the elements
gh, gh−1 , g−1 h, g−1 h−1 generate gh(g−1 h)−1 = g2
and hence all of G (again using the hypothesis that g
has odd order, as above)
...
e
...

Since G is finite, this digraph is strongly connected:
there exists at least one path from any vertex to any
other vertex (traveling all edges in the correct direction)
...


A5 First solution: For s ∈ G and r a positive integer, define
a representation of s of length r to be a sequence of

Second solution: For r a positive integer, let Sr be the
set of s ∈ G which admit a representation of length at
most r (terminology as in the first solution); obviously
Sr ⊆ Sr+1
...


3
Suppose that Sr = Sr+1
...
By the same token, Sr is closed under right multiplication by each of
gh−1 , g−1 h, g−1 h−1
...
since r + 1 ≤ |G|, we are done in this case also
...
On the other hand, if one assumes that both
g and h have odd order, then one can say a bit more:
there exists some positive integer r with 1 ≤ r ≤ |G|
such that every element of G has a representation of
length exactly r
...
)
A6 We prove that the smallest such value of C is 5/6
...
To achieve this reduction, suppose
that a given value C obeys the inequality for such P
...
, Ik at the roots of P
...
, k)
...

Suppose now that P takes nonnegative values on [0, 1],
P(0) = 0, and maxx∈[0,1] P(x) = 1
...

3 6 6

Consequently, the originally claimed inequality holds
with C = 5/6
...
It is apparent that 01 P(x) dx = 5/6
...
Hence P has the desired form
...
Let V be the set of polynomials
of degree at most 3 vanishing at 0, viewed as a threedimensional vector space over R
...
We may then compute the minimal C as the
R
maximum value of 01 P(x) dx over all P ∈ S, provided
that the maximum is achieved for some polynomial of
degree exactly 3
...
)
Let f : V → R be the function taking P(x) to 01 P(x) dx
...
It is obvious that the unique minimum is
achieved by the zero polynomial, so this accounts for
one of the planes
...
The calculation made in the solution
amounts to verifying that
P(x) = 4x3 − 8x2 + 5x
has this property, by interpolating between the constraints P(1/2) ≤ 1 and P(1) ≤ 1
...
If one supposes that it should be
extremized both at x = 1 and at an interval value of
the disc, it is forced to have the form P(x) = 1 + (x −
1)(cx − 1)2 for some c > 0; the interpolation property
then pins down c uniquely
...
Since P has degree at most 3,
R
Simpson’s rule for approximating 01 P(x) dx is an exact
formula:
 
Z 1
1
1
P(x) dx = (P(0) + 4P
+ P(1))
...
Again as in the first solution, we obtain an example
showing that this value is best possible
...

By induction on n, we see that xn > 0 for all n
...

3
2
3
3
For general N, one can then use the estimates

xn = exn − exn+1
...


4
2
(N − 1)3/4 + (N − 1)1/4 ≤ S(bN 1/4 c4 )
3
3
≤ S(N)
≤ S(dN 1/4 e4 )
2
4
≤ (N + 1)3/4 + (N + 1)1/4
3
3

– Since xn > 0, we have exn > exn+1 , so xn > xn+1
...

– Taking limits in the equation yields L = eL − eL ,
whence L = 0
...


We now have a telescoping sum:
x0 + · · · + xn = (ex0 − ex1 ) + · · · + (exn − exn+1 )
= ex0 − exn+1 = e − exn+1
...

B2 We prove that the limit exists for α = 43 , β = 43
...
The √
number of squar√
ish numbers in this interval is 1 + b n − 1c + b nc
...

3

To make this precise, we use the bounds x−1 ≤ bxc ≤ x,
and the upper
√ and lower Riemann sum estimates for the
integral of x, to derive upper and lower bounds on
S(N):
√
b Nc−1

S(N) ≥
≥

√
(2 n − 1 − 1)

∑

n=1
Z b√Nc−2

√
√
2 x dx − N

0

√
4 √
≥ ( N − 3)3/2 − N
3
√
d Ne

S(N) ≤

√
n + 1)

∑ (2

n=1

≤

Z d√Ne+1
0

√
√
2 x dx + N + 1

√
4 √
≤ ( N + 2)3/2 + N + 1
...

B3 Since S is finite, we can choose three points A, B,C in
S so as to maximize the area of the triangle ABC
...

We claim that this triangle has the desired effect; that
is, every point P of S is contained within the triangle
A0 B0C0
...
) To see this, note that since the area of the
triangle PBC is no more than that of ABC, P must lie
in the half-plane bounded by B0C0 containing B and C
...
These three half-planes intersect
precisely in the region bounded by the triangle A0 B0C0 ,
proving the claim
...

4n n!
First solution:
Write the determinant of A − At as the sum over permutations σ of {1,
...

Note that if we partition {1,
...
This means that we can

5
compute Eσ as the product of the expected values of
the individual factors
...
For an orbit of size m ≥ 3,
the corresponding factor contains 2m distinct matrix entries, so again we may compute the expected value of
the factor as the product of the expected values of the
individual terms Aiσ (i) − Aσ (i)i
...

We conclude that Eσ = 0 unless σ acts with n orbits of
size 2
...
, {2n −
1, 2n}; note that sgn(σ ) = (−1)n
...
Since A12 − A21 takes the values −1, 0, 1
with probabilities 41 , 12 , 41 , its square takes the values 0, 1
with probabilities 21 , 12 ; we conclude that
Eσ = 2−n
...
, 2n} into n sets of size 2,
so there are
(2n)!
n!(2!)n
such permutations
...

Second solution: (by Manjul Bhargava) Note that the
matrix A − At is skew-symmetric:
(A − At )t = At − A = −(A − At )
...

Define a perfect matching of {1,
...
, 2n} that is the product of n disjoint
transpositions
...

The
determinant
in
jn
1 1 2 2 ···
of M is then the square of (1), i
...
,
det(M) =

∑ sgn(α) sgn(β )Mi1 , j1 · · · Min , jn Mi01 , j10 · · · Mi0n , jn0
α,β

(2)

Taking M = A − At , so that Mi j = Ai j − A ji , we wish
to find the expected value of (2); again, this is the sum
of the expected values of each summand in (2)
...

Consider first a summand in (2) with α 6= β
...

Consider next a summand in (2) with α = β
...

Since the total number of perfect matchings α is
(2n)!/(2n n!), the expected value of (2) is therefore
(2n)!/(2n n!) · 1/2n = (2n)!/(4n n!), as desired
...

Define the function g : (0, ∞) → (0, ∞) given by g(x) =
log f (ex ); this function has the property that if x, y ∈
(0, ∞) and 2x ≤ y ≤ 3x, then 2g(x) ≤ g(y) ≤ 3g(x)
...

Similarly, define the function h : R → R given by h(x) =
log g(ex ); this function has the property that if x, y ∈ R
and x + log 2 ≤ y ≤ x + log 3, then h(x) + log 2 ≤ h(y) ≤
h(x) + log 3
...

By interchanging the roles of x and y, we may restate the
condition on h as follows: if x − log 3 ≤ y ≤ x − log 2,
then h(x)−log 3 ≤ h(y) ≤ h(x)−log 2
...

To this end, suppose that a + b > 0 and that the claim
is known for all smaller values of a + b
...
Define the function
j(t) =

where the sum is now over ordered pairs
(α = (i1 , j1 ) · · · (in , jn ), β = (i01 , j10 ) · · · (i0n , jn0 ))
of perfect matchings
...


6
converges to 2 ln 2 − 1 as N → ∞, and so S1 = 2 ln 2 − 1
...

m+2 2mn+n
k=1 n=1 m=0 k
∞

S2 =

and thus the desired inequalities
...
Since log 2
and log 3 are linearly independent over Q, the fractional
parts of the nonnegative integer multiples of log 3/ log 2
are dense in [0, 1)
...
) In particular, for any
ε > 0 and any N > 0, we can find integers a, b > N such
that

as the geo-

∞

∞

∑∑∑

(This step requires n ≥ 1, as otherwise the geometric
series would not converge for k = 0
...


and so

By writing

∞

∞ ∞
1
1
≤
∑ ∑ ∑ km+2 2mn+n ∑ ∑ k2 2n−1
k=1 n=1 m=0
k=1 n=1

log 2
(a log 3 − b log 2)
log 3
(log 3)2 − (log 2)2
−b
,
log 3

a log 2 − b log 3 =

∞

∞

∞

=

2

∑ k2 < ∞
...

m=0
n=1 2
k=1 k

we see that this quantity tends to −∞ as N → ∞; in particular, for N sufficiently large we have that a log 2 −
b log 3 < y − x
...
A similar argument shows that h(y) − h(x) ≥ y − x; we deduce that
h(y) − h(x) = y − x, or equivalently h(y) − y = h(x) − x
...


The sum in n is the geometric series
1
2m+1 (1 −

B6 Let S denote the desired sum
...


1
2m+1

)

=

1

...

k
n=1
k=1

It follows that

∑

To compute S1 , note that
N
(−1)k−1
∑ k(k + 1) = ∑ (−1)k−1
k=1
k=1



1
1
−
k k+1

(−1)m ∞ 1
m+1 ∑ km+2
m=0 2
k=1

∞
∞ 
1
1 m
=∑ 2 ∑ −
2k
k=1 2k m=0
∞

The rearrangement is valid because both S1 and S2 converge absolutely in k, by comparison to ∑ 1/k2
...

2
k=1 k

k=1
∞

S2 =

∑ km+2

1
1 ∞ 1
=
S
+
3
∑ km+2
m+2
2m+1 k=1
k=1 (2k)
∞

= S3 + 2 ∑

n=1

then we may write S = S1 + S2 where
S1 =

1

S2 =



N
(−1)N
(−1)k−1
= −1 +
+2 ∑
N +1
k
k=1

∑

∞

=

1

∑ k(2k + 1)

k=1
∞

=2∑
k=1



1
1
−
2k 2k + 1


= 2(1 − ln 2)
...

Second solution: (by Tewodros Amdeberhan) Since
R1 t
1
0 x dx = 1+t for any t ≥ 1, we also have

(−1)k−1
k
k=1 n=0
∞

S=

∞

Z 1

∑∑

n

xk2 dx
...

j i=1 2 j 2 j m − 1

0

Again by absolute convergence, we are free to permute
the integral and the sums:
Z 1

where k runs over all positive integers for which m =
k2n +1 for some n
...
, e
...

m
m=2 m(m − 1)
m=2 m − 1
∞

n

∑ log(1 + x2 )
...

In S1 , we may write k = 2` to obtain
∞

S1 =

`=1

the product converges absolutely for 0 ≤ x < 1
...

Third solution: (by Serin Hong) Again using absolute
convergence, we may write
∞

S=

1

∑ m∑

m=2

k

(−1)k−1
k

1

∞

1

∑ 2` ∑ `2n+1 + 1
n=0

∞
1
1
= (S0 + S1 ) − ∑
2
2`(`
+ 1)
`=1

1
1
= (S0 + S1 ) −
2
2
because the last sum telescopes; this immediately yields
S = 1

---