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 70th William Lowell Putnam Mathematical Competition
Saturday, December 5, 2009

A1 Let f be a real-valued function on the plane such that for
every square ABCD in the plane, f (A) + f (B) + f (C) +
f (D) = 0
...

fg
Find an explicit formula for f (x), valid in some open
interval around 0
...
, cos n2
...

cos 7 cos 8 cos 9
The argument of cos is always in radians, not degrees
...

A4 Let S be a set of rational numbers such that
(a) 0 ∈ S;
(b) If x ∈ S then x + 1 ∈ S and x − 1 ∈ S; and
(c) If x ∈ S and x 6∈ {0, 1}, then

1
x(x−1)

∈ S
...
Let a = 01 f (0, y) dy,
R
R
R
b = 01 f (1, y) dy, c = 01 f (x, 0) dx, d = 01 f (x, 1) dx
...

∂y

B1 Show that every positive rational number can be written
as a quotient of products of factorials of (not necessarily
distinct) primes
...

9
3! · 3! · 3!
B2 A game involves jumping to the right on the real number
line
...
For what real numbers
c can one travel from 0 to 1 in a finite number of jumps
with total cost exactly c?
B3 Call a subset S of {1, 2,
...
Let A(n) be the number of mediocre subsets
of {1, 2,
...
[For instance, every subset of {1, 2, 3}
except {1, 3} is mediocre, so A(3) = 7
...

B4 Say that a polynomial with real coefficients in two variables, x, y, is balanced if the average value of the polynomial on each circle centered at the origin is 0
...
Find the dimension of V
...


Prove that limx→∞ f (x) = ∞
...
, a2009 with a0 = 0 and
a2009 = n such that each term after a0 is either an earlier term plus 2k for some nonnegative integer k, or of
the form b mod c for some earlier positive terms b and c
...
]

Solutions to the 70th William Lowell Putnam Mathematical Competition
Saturday, December 5, 2009
Kiran Kedlaya and Lenny Ng

A–1 Yes, it does follow
...
Let
ABCD be any square with center P
...
The function f must satisfy the equations
0=
0=
0=
0=
0=
0=

f (A) + f (B) + f (C) + f (D)
f (E) + f (F) + f (G) + f (H)
f (A) + f (E) + f (P) + f (H)
f (B) + f (F) + f (P) + f (E)
f (C) + f (G) + f (P) + f (F)
f (D) + f (H) + f (P) + f (G)
...

Remark
...

A–2 Multiplying the first differential equation by gh, the second by f h, and the third by f g, and summing gives
( f gh)0 = 6( f gh)2 + 6
...
One solution for this differential equation with this
initial condition is k(x) = tan(6x + π/4); by standard
uniqueness, this must necessarily hold for x in some
open interval around 0
...

Substituting
2 (6x+π/4)

ln( f (x)) =

f (0) = 1 gives ec = 2−1/12 and thus f (x) =


sin(6x+π/4) 1/6
2−1/12 cos

...
The answer can be put in alternate forms
using trigonometric identities
...


A–3 The limit is 0; we will show this by checking that
dn = 0 for all n ≥ 3
...
However, thanks to the identity
x−y
cos x+cos y = 2 cos x+y
2 cos 2 , the resulting matrix has
the form


2 cos 2 cos 1
cos 2
···
 2 cos(n + 2) cos 1 cos(n + 2) · · ·
2 cos(2n + 2) cos 1 2 cos(2n + 2) · · ·



...


...


...

with the first column being a multiple of the second
...

Remark
...

One can also use the matrices A jk = ei(( j−1)n+k) , B jk =
e−i( j−1)n+k
...
Clearly S satisfies (a) and
(b); we need only check that it satisfies (c)
...
Suppose otherwise; then
(5n + 2)p(p − q) = 5q2
...
On the
other hand, p − q and q are also relatively prime, so
p − q divides 5 as well, and p − q must be ±1 or
±5
...
The
first three are impossible, while the final five lead to
5n + 2 = 16, −20, −36, 16, −36 respectively, none of
which holds for integral n
...
More generally, no rational number of the
form m/n, where m, n are relatively prime and neither
of ±m is a quadratic residue mod n, need be in S
...

A–5 No, there is no such group
...
If any of these factors has
odd order, then G has an element of odd order, so the

2
product of the orders of all of its elements cannot be a
power of 2
...

For such a group G, the product of the orders of all of
its elements has the form 2k(G) for some nonnegative
integer G, and we must show that it is impossible to
achieve k(G) = 2009
...
, all but finitely
many of which are 0
...


∞

k(G) = ∑ i(2si − 2si−1 )
...

In particular, k(G) = 2009 forces s1 ≤ 1
...
The right side is a strictly increasing function
of i which equals 1793 for i = 8 and 4097 for i = 9, so
it can never equal 2009
...

Remark
...
For h > 0, an element of order
2h belongs to an equivalence class of size 2h−1 , so the
products of the orders of the elements of this equivalence class is 2 j for j = h2h−1
...
However, there are exactly 2e − 1
such elements, for e the number of cyclic factors of G
...


Moreover, the partial derivatives
∂f
(x0 , y0 ) = 3(1 + y0 )(8x0 − 4)
∂x
∂f
(x0 , y0 ) = 3(2x0 − 1)2 − 1
...
Namely, for the first
partial to vanish, we must have x0 = 1/2 since 1 + y0 is
nowhere zero, but for x0 = 1/2 the second partial cannot
vanish
...
This problem amounts to refuting a potential
generalization of the Mean Value Theorem to bivariate
functions
...
Kent
Merryfield suggests y sin(2πx), for which all four of the
boundary integrals vanish; here the partial derivatives
are 2πy cos(2πx) and sin(2πx)
...
Qingchun Ren suggests xy(1 − y)
...
We
prove the statement in the problem by induction on the
largest prime dividing either a or b (where this is considered to be 1 if a = b = 1)
...
For a general a/b, let p be the
largest prime dividing either a or b; then a/b = pk a0 /b0
for some k 6= 0 and positive integers a0 , b0 whose largest
prime factors are strictly less than p
...
By the induction asa0
sumption, (p−1)!
k b0 can be written as a quotient of prod0

a
ucts of prime factorials, and so a/b = (p!)k (p−1)!
k b0 can
as well
...


Remark
...

B–2 The desired real numbers c are precisely those for which
1/3 < c ≤ 1
...
Since
m

m

1 = ∑ (xi − xi−1 ) ≥ ∑ (xi − xi−1 )xi2
i=1
m Z xi−1

i=1

>∑

A–6 We disprove the assertion using the example
f (x, y) = 3(1 + y)(2x − 1)2 − y
...


=

t 2 dt

i=1 xi
Z 1
2
0

1
t dt = ,
3

we can only achieve costs c for which 1/3 < c ≤ 1
...

Suppose 0 = x0 < · · · < xm = 1 is a sequence with m ≥
1
...
, m, let ci be the cost of the sequence
0, xi , xi+1 ,
...
For i > 1 and 0 < y ≤ xi−1 , the cost of
the sequence 0, y, xi ,
...
By
continuity, for i = 2,
...


endpoints by subtracting 2k−1 from each element
...
Thus
S = {1,
...


To show that all costs c with 1/3 < c ≤ 1 can be
achieved, it now suffices to check that for every ε > 0,
there exists a sequence with cost at most 1/3 + ε
...
, m, the cost
becomes

Remark
...
, n} is mediocre if and only if
it is an arithmetic progression with odd common difference
...
, n + 2} containing the endpoints is seen to be
the number of odd factors of n + 1, from which the desired result is evident
...
)

(m + 1)(2m + 1)
1 2
(1 + · · · + m2 ) =
,
m3
6m2
which converges to 1/3 as m → +∞
...
The cost of jumping along a particular sequence is an upper Riemann sum of the function
t 2
...
, xm is at most 1/3 + ε as
long as maxi {xi − xi−1 } < ε
...
)
B–3 The answer is n = 2k − 1 for some integer k ≥ 1
...
, n}
and mediocre subsets of {2,
...
, n + 1}
that contain 1
...
, n + 2} containing 1 and the number of
mediocre subsets of {1,
...
This
difference is precisely the number of mediocre subsets
of {1,
...
”
Since {1,
...
, n + 2} containing
the endpoints if and only if n = 2k − 1 for some k
...
In this case, the set {1 + mb | 0 ≤ m ≤
2a } is a mediocre subset of {1,
...

It remains to show that if n = 2k − 1, then the only
mediocre subset of {1,
...
This is readily seen by induction on
k
...
For general
k, any mediocre subset S of {1,
...
By the induction assumption, the only
mediocre subset of {1,
...
Similarly, a mediocre subset
of {2k−1 + 1,
...
, 2k−1 + 1} containing the

B–4 Any polynomial P(x, y) of degree at most 2009 can be
written uniquely as a sum ∑2009
i=0 Pi (x, y) in which Pi (x, y)
is a homogeneous polynomial of degree i
...
Put
λ (Pi ) = C1 Pi ; then for r > 0,
2009

I

P=
Cr

∑ ri λ (Pi )
...
In other words, P is balanced if and only if
λ (Pi ) = 0 for i = 0,
...

For i odd, we have Pi (−x, −y) = −Pi (x, y)
...
g
...

For i even, λ (Pi ) is a linear function of the coefficients
of Pi
...
g
...
The kernel of λ on the space of homogeneous polynomials of degree i is thus a subspace
of codimension 1
...

B–5 First solution
...
We may thus assume hereafter
that there exists x0 > 1 for which f (x0 ) < x0
...

x2 1 + f (x)2

Put c0 = min{0, f (x0 ) − 1/x0 }
...


In the other direction, we claim that f (x) < x for all
x ≥ x0
...
However, this forces
f 0 (x) = 0 < 1 and so f (x − ε) > x − ε for ε > 0 small,
contradicting the choice of x
...
For x ≥ x1 , we have | f (x)| < x
and so f 0 (x) > 0
...

Suppose that L < +∞; then limx→+∞ f 0 (x) = 1/(1 +
L2 ) > 0
...
But then
f (x) ≥ f (x2 ) + ε(x − x2 ), which contradicts L < +∞
...

Variant
...

x2
1 + f (x)2

Hence f 0 (x) − 1/(1 + f (x)2 ) tends to 0 as x → +∞, so
f (x) is bounded below,
R and tends to +∞ if and only if
the improper integral dx/(1 + f (x)2 ) diverges
...

Second solution
...

1 + x2 (g(x)/x − 1)2

This implies that g0 (x) > 0 for all x > 1, so the limit
L1 = limx→+∞ g(x) exists
...
Hence g(x) → +∞ as x → +∞
...

1 + x2 (h(x)/x − 1)2

This implies that h0 (x) ≥ 0 for all x, so the limit L2 =
limx→+∞ h(x) exists
...
Hence
h(x) → +∞ as x → +∞
...
For x ≥ x1 , we have | f (x)| < x and hence
f 0 (x) > 0, so the limit L = limx→+∞ f (x) exists
...
g
...
Hence
f (x) → +∞ as x → ∞, as desired
...
(by Noam Elkies) Consider the function g(x) = f (x) + 31 f (x)3 , for which
g0 (x) = f 0 (x)(1 + f (x)2 ) = 1 −

f (x)2
x2

for x > 1
...
As in the first solution, f (x) is
bounded below for x large, so 13 f (x)3 − x is bounded
above by some c > 0
...

Since f (x)/x → 0 as x → +∞, g0 (x) → 1 and so
g(x)/x → 1
...

(With a tiny bit of extra work, one shows that in fact
f (x)/(3x)1/3 → 1 as x → +∞
...
(based on work of Yufei Zhao) Since
any sequence of the desired form remains of the desired
form upon multiplying each term by 2, we may reduce
to the case where n is odd
...

We may pad the sequence to the desired length by taking a8 = · · · = a2009 = n
...
(by James Merryfield) Suppose first
that n is not divisible by 3
...
In particular, if we choose h
so that 32h > n, then there exists a positive integer c for
which 2c mod 32h = n
...

If n is divisible by 3, we can force a7 = n − 1 as in the
above construction, then put a8 = a7 + 1 = n
...

Remark
...
For n odd and x
as in the first solution, set
a0 = 0
a1 = 1
a2 = x + 1 = a1 + x
a3 = xn + x + 1 = a2 + xn
a4 = x(n−1)(φ (a3 )−1)
xn + 1
a5 =
= a4 mod a3
x+1
a6 = n = a5 mod a2
...




---