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 72nd William Lowell Putnam Mathematical Competition
Saturday, December 3, 2011

A1 Define a growing spiral in the plane to be a sequence
of points with integer coordinates P0 = (0, 0), P1 ,
...
, Pn−1 Pn
are in the successive coordinate directions east
(for P0 P1 ), north, west, south, east, etc
...

[Picture omitted
...
and b1 , b2 ,
...
Assume that the sequence (b j ) is
bounded
...
an

n=1

converges, and evaluate S
...


A4 For which positive integers n is there an n × n matrix
with integer entries such that every dot product of a row
with itself is even, while every dot product of two different rows is odd?
A5 Let F : R2 → R and g : R → R be twice continuously
differentiable functions with the following properties:
– F(u, u) = 0 for every u ∈ R;
– for every x ∈ R, g(x) > 0 and x2 g(x) ≤ 1;
– for every (u, v) ∈ R2 , the vector ∇F(u, v) is either
0 or parallel to the vector hg(u), −g(v)i
...

B1 Let h and k be positive integers
...

B2 Let S be the set of all ordered triples (p, q, r) of prime
numbers for which at least one rational number x satisfies px2 + qx + r = 0
...
If f g and f /g are differentiable at 0, must f
be differentiable at 0?
B4 In a tournament, 2011 players meet 2011 times to play
a multiplayer game
...
The standings are kept in two 2011×
2011 matrices, T = (Thk ) and W = (Whk )
...
After every game, for every (h, k) (including for
h = k), if players h and k tied (that is, both won or both
lost), the entry Thk is increased by 1, while if player h
won and player k lost, the entry Whk is increased by 1
and Wkh is decreased by 1
...

B5 Let a1 , a2 ,
...
Suppose that there is a
constant A such that for all n,
!2
Z ∞
n
1
dx ≤ An
...
, xn+1 ∈ R, we have
min |F(xi , x j )| ≤
i6= j

C

...
, gk } $ G
be a (not necessarily minimal) set of distinct generators
of G
...
, gk with equal probability, is rolled m
times and the selected elements are multiplied to produce an element g ∈ G
...


i, j=1

B6 Let p be an odd prime
...
, p − 1},
p−1

∑ k!nk
k=0

is not divisible by p
...
Since
3/2(1 − ( B+2

A1 We claim that the set of points with 0 ≤ x ≤ 2011 and
0 ≤ y ≤ 2011 that cannot be the last point of a growing
spiral are as follows: (0, y) for 0 ≤ y ≤ 2011; (x, 0) and
(x, 1) for 1 ≤ x ≤ 2011; (x, 2) for 2 ≤ x ≤ 2011; and
(x, 3) for 3 ≤ x ≤ 2011
...

A3 We claim that (c, L) = (−1, 2/π) works
...
Then
0

excluded points
...
Clearly the
former set is achievable as P2 in a growing spiral, while
a point (x, y) in the latter set is P6 in a growing spiral
with successive lengths 1, 2, 3, x + 1, x + 2, and x + y −
1
...
Write x1 <
y1 < x2 < y2 <
...
Any point beyond P0
has x-coordinate of the form x1 − x2 + · · · + (−1)n−1 xn
for n ≥ 1; if n is odd, we can write this as x1 + (−x2 +
x3 ) + · · · + (−xn−1 + xn ) > 0, while if n is even, we can
write this as (x1 − x2 ) + · · · + (xn−1 − xn ) < 0
...

Next we claim that any point beyond P3 must have
y-coordinate either negative or ≥ 4
...

r+2

It follows that
 r+1
2
lim r
f (r) = 1,
r→∞
π
whence
lim

r→∞

r(2/π)r+1 f (r)
2(r + 1)
2
f (r)
= lim
·
=
...

r+1

Thus setting c = −1 in the given limit yields
y1 + (−y2 + y3 ) + · · · + (−yn−1 + yn ) ≥ y1 + 2 ≥ 4
if n ≥ 3 is odd
...
But none of them can be P3 =
(x1 − x2 , y1 ) since x1 − x2 < 0, and none of them can
be P2 = (x1 , y1 ) since they all have y-coordinate at most
equal to their x-coordinate
...

2
(b1 + 2) · · · (bm + 2)
Then S1 = 1 = 1/a1 and a quick calculation yields
Sm − Sm−1 =

1
b1 · · · bm−1
=
(b2 + 2) · · · (bm + 2) a1 · · · am

for m ≥ 2, since a j = (b j + 2)/b j−1 for j ≥ 2
...


lim

r→∞

(r + 1) f (r)
2
= ,
r f (r + 1)
π

as desired
...
Let I denote the n × n identity
matrix, and let A denote the n × n matrix all of whose
entries are 1
...

Conversely, suppose n is even, and suppose that the matrix M satisfied the conditions of the problem
...
Since the dot product
of a row with itself is equal mod 2 to the sum of the entries of the row, we have Mv = 0 where v is the vector
(1, 1,
...
On the other hand,
MM T = A − I; since
(A − I)2 = A2 − 2A + I = (n − 2)A + I = I,
we have (det M)2 = det(A − I) = 1 and det M = 1, contradicting the fact that M is singular
...
By assumption, G is a strictly increasing,
thrice continuously differentiable function
...
First suppose b = 0;
then
1=

χ∈Gˆ

dt/t 2 = 1,

1

and similarly, for x < −1, we have 0 > G(x) − G(−1) ≥
−1
...

Define H : (A, B) × (A, B) → R by H(x, y) =
F(G−1 (x), G−1 (y)); it is twice continuously differentiable since F and G−1 are
...

∂y
g(G−1 (y))
Therefore H is constant along any line parallel to the
vector (1, 1), or equivalently, H(x, y) depends only on
x − y
...
Since F(u, u) = 0, we have
h(0) = 0
...

Given x1 ,
...
, G(xn+1 ) all belong to (A, B), so we can
choose indices i and j so that |G(xi ) − G(x j )| ≤ (B −
A)/n ≤ (B − A)/2
...

A6 Choose some ordering h1 ,
...
Define an n × n matrix M by settting Mi j =
1/k if h j = hi g for some g ∈ {g1 ,
...
Let v denote the column vector (1, 0,
...

The probability that the product of m random elements
of {g1 ,
...

Let Gˆ denote the dual group of G, i
...
, the group
of complex-valued characters of G
...
For each χ ∈ G,
n
vχ = (χ(hi ))i=1 is an eigenvector of M with eigenvalue
λχ = (χ(g1 ) + · · · + χ(gk ))/k
...
Put
b = max{|λχ | : χ ∈ Gˆ − {e}};
ˆ

1

k

n

∑ λχ = k ∑ ∑ χ(gi ) = k
i=1 χ∈Gˆ

because ∑χ∈(G)
ˆ χ(gi ) equals n for i = 1 and 0 otherwise
...
, gk } is not all of G
...
Next suppose
b = 1, and choose χ ∈ Gˆ − {e}
ˆ with |λχ | = 1
...
, χ(gk ) is a complex number of norm
1, the triangle inequality forces them all to be equal
...
, gk
to 1, but this is impossible because χ is a nontrivial
character and g1 ,
...

This contradiction yields b < 1
...


ˆ e}
χ∈G−{
ˆ

Since the vectors vχ are pairwise orthogonal, the limit
we are interested in can be written as
lim

1

m→∞ b2m

1
1
(M m v − veˆ ) · (M m v − veˆ )
...


ˆ e}
χ∈G−{
ˆ

By construction, this last quantity is nonzero and finite
...
It is easy to see that the result fails if we do
not assume g1 = e: take G = Z/2Z, n = 1, and g1 = 1
...
Harm Derksen points out that a similar argument applies even if G is not assumed to be abelian,
provided that the operator g1 + · · · + gk in the group algebra Z[G] is normal, i
...
, it commutes with the op−1
erator g−1
1 + · · · + gk
...
, gk } is closed under taking inverses and
where it is a union of conjugacy classes (which in turn
includes the case of G abelian)
...
The matrix M used above has nonnegative
entries with row sums equal to 1 (i
...
, it corresponds to
a Markov chain), and there exists a positive integer m
such that M m has positive entries
...
(The intended interpretation in
case b = 0 is that M m v = w for all large m
...


3
B1 Since the rational numbers are dense in the reals, we
can find positive integers a, b such that

If f (0) = 0, then ( f /g)(0) = 0, so we have

3ε
b 4ε
< <
...
We then have
b
b
ε
<
<√
=
hk 3a
a2 + b + a
and
p

p

a2 + b − a

b
b
ε
a2 + b − a = √
≤
<2
...

B2 Only the primes 2 and 5 appear seven or more times
...

It remains to show that if either ` = 3 or ` is a prime
greater than 5, then ` occurs at most six times as an
element of a triple in S
...
In particular, q is odd,
as then is a, and so q2 ≡ a2 ≡ 1 (mod 8); consequently,
one of p, r must equal 2
...
Since they are also both even, we have q + a ∈
{2, 4, 2p, 4p} and so q ∈ {2p + 1, p + 2}
...
Consequently, ` occurs
at most twice as many times as there are prime numbers
in the list
2` + 1, ` + 2,

( f g) · ( f /g) with the square root function
...


`−1
, ` − 2
...
For ` ≥ 7, the numbers
` − 2, `, ` + 2 cannot all be prime, since one of them is
always a nontrivial multiple of 3
...
The above argument shows that the cases
listed for 5 are the only ones that can occur
...

B3 Yes, it follows that f is differentiable
...
Note first that at 0, f /g and g are both
continuous, as then is their product f
...
We can thus choose ε ∈ {±1} so
that ε f is the composition of the differentiable function

( f /g)0 (0) = lim

x→0

f (x)

...

Second solution
...
Define the following functions on N \
f (0)g(x)
{0}: h1 (x) = f (x)g(x)−x f (0)g(0) ; h2 (x) = f (x)g(0)−
;
xg(0)g(x)
1

...
On the other
hand,

f (x) − f (0)
= (h1 (x) + h2 (x)h3 (x))h4 (x),
x
and it follows that limx→0

f (x)− f (0)
x

exists, as desired
...
, 2011, and let A = (a jk ) be the
2011 × 2011 matrix
√ whose jk entry is 1 if player k wins
game j and i = −1 if player k loses game j
...
It follows that T + iW = A A
...
Thus we can write
det A = (1 − i)2010 (a + bi) for some integers a, b
...

B5 Define the function
dx

...

We thus have the lower bound
f (y) ≥

1
;
6(1 + y2 )

the same bound is valid for y ≤ 0 because f (y) = f (−y)
...

2
i, j=1 1 + (ai − a j )

∑

4
By the Cauchy-Schwarz inequality, this implies

and note that by Wilson’s theorem again,

n

p−1

∑ (1 + (ai − a j )2 ) ≥ Bn3

h0 (x) = 1 +

i, j=1

k=1

for B = 1/(6A)
...
One can also compute explicitly (using partial fractions, Fourier transforms, or contour integra2π
tion) that f (y) = 4+y
2
...
Praveen Venkataramana points out that the
lower bound can be improved to Bn4 as follows
...
, n} : ai ∈ [z, z + 1)}
and qz,n = #Qz,n
...

2
1
+
(a
−
a
)
i
j
i, j=1
z∈Z 2
∑z∈Z q2z,n

If exactly k of the qz,n are nonzero, then
≥
n2 /k by Jensen’s inequality (or various other methods),
so we must have k ≥ n/(6A)
...

≥n + −
6
3
6
3
2

If z ∈ F p is such that g(z) = 0, then z 6= 0 because g(0) =
1
...
Since h is a polynomial of
degree p, there can be at most (p − 1)/2 zeroes of g in
F p , as desired
...
(By Noam Elkies) Define the polynomial f over F p by
p−1

f (x) =

In the opposite direction, one can weaken the initial upper bound to An4/3 and still derive a lower bound of
Bn3
...

B6 In order to interpret the problem statement, one must
choose a convention for the value of 00 ; we will take it
to equal 1
...
)

Put t = (p − 1)/2; the problem statement is that f has
at most t roots modulo p
...
Denote these values by x1 ,
...


Replacing x with −1/x, we reduce the original problem
to showing that the polynomial
g(x) =

∑ Qk x k
...

This means that the power series expansions of f (x) and
P(x)/Q(x) coincide modulo x p−1 , so the coefficients of
xt ,
...
In other words, the
product of the square matrix

with the nonzero column vector (Qt−1 ,
...

However, by the following lemma, det(A) is nonzero
modulo p, a contradiction
...
For any nonnegative integer m and any integer n,
m

k=0

p−1

t−1

m

Q(x) = ∏ (x − xm ) =

A = ((i + j + 1)!)t−1
i, j=0

First solution
...

k=0

This is bounded below by Bn4 for some B > 0
...


p−1 k
x

∑ k!

det((i + j + n)!)m
i, j=0 = ∏ k!(k + n)!
...
Define the (m+1)×(m+1) matrix Am,n by (Am,n )i, j =
i+ j+n

; the desired result is then that det(Am,n ) = 1
...
To
see this, write
h(x) = x p − x + g(x)

that is, Am,n−1 can be obtained from Am,n by elementary row
operations
...
The claim now follows by observing that
A0,0 is the 1 × 1 matrix
 with entry
 1 and that Am,−1 has the
1
∗
block representation

...

Elkies has given a more detailed
discussion of the origins of this solution in
the theory of orthogonal polynomials;
see

http://mathoverflow
...




---