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 71st William Lowell Putnam Mathematical Competition
Saturday, December 4, 2010

A1 Given a positive integer n, what is the largest k such that
the numbers 1, 2,
...
]
A2 Find all differentiable functions f : R → R such that
f (x + n) − f (x)
f 0 (x) =
n

B1 Is there an infinite sequence of real numbers
a1 , a2 , a3 ,
...

A3 Suppose that the function h : R2 → R has continuous
partial derivatives and satisfies the equation
h(x, y) = a

∂h
∂h
(x, y) + b (x, y)
∂x
∂y

for some constants a, b
...

A4 Prove that for each positive integer n, the number
10n
n
1010 + 1010 + 10n − 1 is not prime
...
Suppose that
(i) G is a subset of R3 (but ∗ need not be related to
addition of vectors);
(ii) For each a, b ∈ G, either a × b = a ∗ b or a × b = 0
(or both), where × is the usual cross product in
R3
...

A6 Let f : [0, ∞) → R be a strictly decreasing continuous function such that limx→∞ f (x) = 0
...

0
f (x)

B3 There are 2010 boxes labeled B1 , B2 ,
...
You may redistribute the balls
by a sequence of moves, each of which consists of
choosing an i and moving exactly i balls from box Bi
into any one other box
...

B5 Is there a strictly increasing function f : R → R such
that f 0 (x) = f ( f (x)) for all x?
B6 Let A be an n × n matrix of real numbers for some n ≥
1
...
Show
that if Ak = A[k] for k = 1, 2,
...


Solutions to the 71st William Lowell Putnam Mathematical Competition
Saturday, December 4, 2010
Kiran Kedlaya and Lenny Ng

n
A–1 The largest such k is b n+1
2 c = d 2 e
...
It follows that

{1, n}, {2, n − 1},
...

One way to see that this is optimal is to note that the
common sum can never be less than n, since n itself
belongs to one of the boxes
...
Another argument is that if k >
(n + 1)/2, then there would have to be two boxes with
one number each (by the pigeonhole principle), but such
boxes could not have the same sum
...
A much subtler question would be to find
the smallest k (as a function of n) for which no such
arrangement exists
...
To see this, suppose that f
has the desired property
...

m

Since N ≥ 1010 > 10n + 1 ≥ 102 + 1, it follows that N
is composite
...

Lemma 1
...

Proof
...
Then w = x × z 6= 0, so w = x ∗ z is
nonzero and orthogonal to x and z
...

Lemma 2
...

Proof
...

Lemma 3
...

Proof
...
Consequently, x∗y = x×y and y∗x = y×x 6= x∗y
...

Consequently, f 0 (x + 1) = f 0 (x)
...
For all x ∈ R,
g0 (x) = f 0 (x + 1) − f 0 (x) = 0, so g(x) = c identically,
and f 0 (x) = f (x+1)− f (x) = g(x) = c, so f (x) = cx+d
identically as desired
...
Pick
any point (a0 , b0 ) ∈ R2 , and let L be the line given by
the parametric equation L(t) = (a0 , b0 ) + (a, b)t for t ∈
R
...
If we write f = h ◦ L : R → R, then
f 0 (t) = f (t) for all t
...
Since | f (t)| ≤ M for all t, we must have
C = 0
...

A–4 Put
10n

N = 1010

n

+ 1010 + 10n − 1
...
For any nonnegative integer j,
mj

102

≡ (−1) j

m

(mod 102 + 1)
...
Assume by way of contradiction that there exist a, b ∈ G with a × b 6= 0
...
Let e be the identity element of G
...
Since a, b, c span R3 , e×x = 0
for all x ∈ R3 , so e = 0
...

Hence b ∗ c = c ∗ b, contradicting Lemma 3 because b ×
c 6= 0
...

A–6 First solution
...

Rewrite the integral as

Z ∞
f (x + 1)
1−
dx,
f (x)
0

2
If there exist arbitrarily large values of y for which
f (y) > 2 f (y + 1), we deduce that the original integral is
greater than any multiple of 1/7, and so diverges
...
For n ≥ 0, define the Lebesgue measurable set
In = {x ∈ [0, 1] : 1 −

f (x + n + 1)
≤ 1/2}
...
In particular, there exists a nonnegative integer
N for which ∑∞
n=N (1 − µ(In )) < 1; the intersection

I=

∞
[

In = [0, 1] −

n=N

∞
\

as in the above solution, and again get divergence using
a telescoping sum
...
(Communicated by Paul Allen
...
Then

([0, 1] − In )

n=N

Z b
f (x) − f (x + 1)

then has positive Lebesgue measure
...

f (x + n)
I

For each x ∈ I, log f (x + N)/ f (x + n) is a strictly
increasing unbounded function of n
...
Thus the original integral diverges, as
desired
...
This solution is motivated by the commonlyused fact that an infinite product (1 + x1 )(1 + x2 ) · · ·
converges absolutely if and only if the sum x1 + x2 + · · ·
converges absolutely
...

Greg Martin suggests a variant solution that avoids use
of Lebesgue measure
...

f (x)
2
7
y−1/2
2

f (x + k) − f (x + k + 1)
dx
f (x + k)

Z 1 b−1
f (x + k) − f (x + k + 1)

∑

f (x + k)

0 k=a

≥

= t + 2t 2 ≤ 2t
...

f (x + a)

0

Now since f (x) → 0, given a, we can choose an integer l(a) > a for which f (l(a)) < f (a + 1)/2; then
(l(a))
f (x+a)− f (x+l(a))
≥ 1 − ff (a+1)
> 1/2 for all x ∈ [0, 1]
...

Third solution
...
) If the original integral converges, then
on one hand the integrand ( f (x) − f (x + 1))/ f (x) = 1 −
f (x + 1)/ f (x) cannot tend to 1 as x → ∞
...
Hence by
the squeeze theorem, f (a + 1)/ f (a) → 0 as a → ∞, a
contradiction
...
No such sequence exists
...

Second solution
...
)
Suppose that such a sequence exists
...
There thus exists a positive integer k for
which a2k ≥ 1
...

2
Third solution
...
of complex numbers to satisfy the
given conditions in case the series ak1 + ak2 + · · · converges absolutely
...

k
Since the sum ∑∞
i=1 |ai | converges by hypothesis, we
k
can find a positive integer n such that ∑∞
i=n+1 |ai | < 1
...


 i=n+1
i=1

We thus cannot have |a1 |,
...
But if we put r = max{|a1 |,
...



d→∞
i=1
For instance, this follows from applying the root test to
the rational function
!
n
n
∞
1
kd
∑ 1 − ak z = ∑ ∑ ai zd ,
i=1
d=0 i=1
i
which has a pole within the circle |z| ≤ r−1/k
...
)
Fourth solution
...
)
Since ∑k a2k = 2, for each positive integer k we have
a2k ≤ 2 and so a4k ≤ 2a2k , with equality only for a2k ∈
{0, 2}
...
But then ∑k a2m
k = 2 6= 2m for any positive integer
m > 2
...
Manjul Bhargava points out it is easy to construct sequences of complex numbers with the desired
property if we drop the condition of absolute convergence
...
For n = 1, 2,
...
, n − 1
...
Moreover, any partial sum of j-th powers is bounded in absolute value by n/|z| j
...

Suppose that we have a finite sequence which has the
correct sum of j-th powers for j = 1,
...
(For instance, for m = 1, we may start with the singleton
sequence 1
...
, m + 1, by appending k copies of sm+1,z for
suitable choices of a positive integer k and a complex
number z with |z| < m−2
...
is such that
m
for each positive integer m, the series am
1 + a2 + · · · is
convergent (though not absolutely convergent)
...

B–2 The smallest distance is 3, achieved by A = (0, 0), B =
(3, 0), C = (0, 4)
...
(It cannot equal 0 because
if two of the points were to coincide, the three points
would be collinear
...
If AB =
1, we may assume without loss of generality that A =
(0, 0), B = (1, 0)
...
(One can also treat this case by scaling
by a factor of 2 to reduce to the case AB = 2, treated in
the next paragraph
...
The triangle inequality implies |AC − BC| ∈ {0, 1}
...
Hence c = (1, y) for
some y ∈ R, so y2 and y2 + 1 = BC2 are consecutive
perfect squares
...

Remark
...

The original problem follows from this because a triangle whose vertices have integer coordinates has area

4
equal to half an integer (by Pick’s formula or the explicit formula for the area as a determinant)
...
Since
1 + · · · + 2009 =

2009 × 2010
= 2010 × 1004
...
From such a distribution, no
moves are possible, so we cannot reach the desired final
distribution
...
By the pigeonhole principle, at any time, there exists at least one index i for
which the box Bi contains at least i balls
...
The following
sequence of operations then has the desired effect
...
If i = 1, proceed
to (b)
...

(b) At this point, only the index i = 1 can be eligible (so it must be)
...
If j = 1, proceed to (c)
...
Then
repeat (b)
...
For p and q of this form,
p(x)q(x + 1) − p(x + 1)q(x) = bc − ad,
so we get a solution if and only if bc − ad = 1, as
claimed
...
(Communicated by Catalin Zara
...
Write
p(x) = p0 + p1 x + · · · + pm xm
q(x) = q0 + q1 x + · · · + qn xn
with pm , qn 6= 0, so that m = deg(p), n = deg(q)
...

Put R(x) = p(x)q(x+1)− p(x+1)q(x)
...
By easy algebra, this coefficient equals (m −
n)pm qn , so we must have m = n > 1
...
, 2m − 2, the coefficient of xk in R(x) is

 

j
i
−
(pi q j − p j qi )
∑
k−i
k− j
i+ j>k, j>i

(c) At this point, all of the balls are in B1
...
, 2010, move one ball from B1 to Bi n times
...
For k = 2m − 2, the only summand is
for (i, j) = (m − 1, m), so pm−1 qm = pm qm−1
...


Suppose now that h ≥ 1 and that pi q j = p j qi is known to
vanish whenever j > i ≥ h
...
) Take k = m + h − 2
and note that the conditions i + j > h, j ≤ m force i ≥
h − 1
...
Hence ph−1 qm = pm qh−1 ;
since pm , qm 6= 0, this implies ph−1 q j = p j qh−1 whenever j > h − 1
...
The pairs (p, q) satisfying the given
equation are those of the form p(x) = ax + b, q(x) =
cx + d for a, b, c, d ∈ R such that bc − ad = 1
...

Suppose p and q satisfy the given equation; note that
neither p nor q can be identically zero
...

The original equation implies that p(x) and q(x) have
no common nonconstant factor, so p(x) divides p(x +
1) + p(x − 1)
...

If we define the polynomials r(x) = p(x + 1) − p(x),
s(x) = q(x + 1) − q(x), we have r(x + 1) = r(x), and
similarly s(x + 1) = s(x)
...


By descending induction, we deduce that pi q j = p j qi
whenever j > i ≥ 0
...

Third solution
...
)
As in the second solution, we note that there are no solutions where m = deg(p), n = deg(q) are distinct and
m+n ≥ 2
...

The desired identity asserts that the matrix


p(x) p(x + 1)
q(x) q(x + 1)
has determinant 1
...
In
particular, we can choose t so that deg(q(x) − t p(x)) <
m; we then obtain a contradiction
...
The answer is no
...

For the condition to make sense, f must be differentiable
...
Also, the function f 0 (x) is strictly
increasing: if y > x then f 0 (y) = f ( f (y)) > f ( f (x)) =
f 0 (x)
...

For any x0 ≥ −1, if f (x0 ) = b and f 0 (x0 ) = a > 0, then
f 0 (x) > a for x > x0 and thus f (x) ≥ a(x − x0 ) + b for
x ≥ x0
...
In the latter case, b ≤ a(x0 +
1)/(a + 1) ≤ x0 + 1
...

It must then be the case that f ( f (x)) = f 0 (x) ≤ 1 for
all x, since otherwise f (x) > x + 1 for large x
...
Thus for
x > max{0, −b0 /a0 }, we have f (x) > 0 and f ( f (x)) >
a0 x + b0
...

Second solution
...
)
Suppose such a function exists
...
In
particular, f is twice differentiable; also, f 00 (x) =
f 0 ( f (x)) f 0 (x) is the product of two strictly increasing
nonnegative functions, so it is also strictly increasing
and nonnegative
...
Then
for all x ≥ M,
f (x) ≥ f (M) + f 0 (M)(x − M) + 2α(x − M)2
...

Pick T > 0 so that αT 2 > M 0
...
Now
1
1
−
=
f (T ) f (2T )

Z 2T 0
f (t)
T

f (t)2

dt ≥

Z 2T

α dt;
T

however, as T → ∞, the left side of this inequality tends
to 0 while the right side tends to +∞, a contradiction
...
(Communicated by Noam Elkies
...
Then

x = g( f (x)), and we may differentiate to find that
1 = g0 ( f (x)) f 0 (x) = g0 ( f (x)) f ( f (x))
...
One then
gets a contradiction from any reasonable lower bound
on f (y) for y large, e
...
, the bound f (x) ≥ αx2 from the
second solution
...
)
B–6 For any polynomial p(x), let [p(x)]A denote the n × n
matrix obtained by replacing each entry Ai j of A by
p(Ai j ); thus A[k] = [xk ]A
...
By
the Cayley-Hamilton theorem,
0 = A · P(A)
= An+1 + an−1 An + · · · + a0 A
= A[n+1] + an−1 A[n] + · · · + a0 A[1]
= [xp(x)]A
...

Now suppose m ≥ n + 1
...
On the
other hand,
0 = Am+1−n · P(A)
= Am+1 + an−1 Am + · · · + a0 Am+1−n
...
The desired result follows by induction
on m
...
David Feldman points out that the result is
best possible in the following sense: there exist examples of n × n matrices A for which Ak = A[k] for
k = 1,
...




---