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

---