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 73rd William Lowell Putnam Mathematical Competition
Saturday, December 1, 2012

A1 Let d1 , d2 ,
...
Show that there exist distinct indices i, j, k such
that di , d j , dk are the side lengths of an acute triangle
...
Assume that for every x and y in S, there
exists z in S such that x ∗ z = y
...
) Show that if a, b, c are in S and a ∗ c = b ∗ c,
then a = b
...


Prove that f is unique, and express f (x) in closed form
...
Let T be the set of all b + mq
where b and m are integers with b in B, and let S be
the set of all integers a in A such that ra is in T
...

A5 Let F p denote the field of integers modulo a prime p,
and let n be a positive integer
...
Let G(k)
denote the k-fold composition of G with itself, that is,
G(1) (x) = G(x) and G(k+1) (x) = G(G(k) (x))
...
, pn are distinct
...

Suppose that, for every rectangular region R of area 1,
the double integral of f (x, y) over R equals 0
...

Prove that if f (x) and g(x) are in S, then the function
f (x)g(x) is also in S
...
Prove
that there is a constant c(P) > 0 with the following
property: If a collection of n balls whose volumes sum
to V contains the entire surface of P, then n > c(P)/V 2
...
On each day, every team played one
game against another team, with one team winning and
one team losing in each of the n games
...
Can one necessarily choose one winning
team from each day without choosing any team more
than once?
B4 Suppose that a0 = 1 and that an+1 = an + e−an for n =
0, 1, 2,
...
)
B5 Prove that, for any two bounded functions g1 , g2 : R →
[1, ∞), there exist functions h1 , h2 : R → R such that, for
every x ∈ R,
sup(g1 (s)x g2 (s)) = max(xh1 (t) + h2 (t))
...

Define a permutation π of the residue classes modulo p
by π(x) ≡ x3 (mod p)
...


Solutions to the 73rd William Lowell Putnam Mathematical Competition
Saturday, December 1, 2012
Kiran Kedlaya and Lenny Ng

A1 Without loss of generality, assume d1 ≤ d2 ≤ · · · ≤ d12
...
Thus
case di2 < di+1
i
i+2
i+1
i+2
2 ≥ d2 + d2
we may assume di+2
i
i+1 for all i
...
Setting i = 12 now gives
2 ≥ 144d 2 , contradicting d > 1 and d < 12
...
A materially equivalent problem appeared on
the 2012 USA Mathematical Olympiad and USA Junior
Mathematical Olympiad
...
For some e ∈ S, d ∗ e = a,
and thus for f = c ∗ e, a ∗ f = a ∗ c ∗ e = d ∗ e = a and
b ∗ f = b ∗ c ∗ e = d ∗ e = a
...

Remark
...

√
all x ∈ [−1, 1]
...
Plug√
2
ging f (x) = g(x) 1 − x into equation (i) and simplifying yields
 2 
x
g(x) = g
(1)
2 − x2
for all x ∈ (−1, 1)
...

2−a2n

Then

an ∈ (−1, 1) and thus |an+1 | ≤ |an for all n
...
Since g(an ) = g(x) for
all n by (1) and g is continuous at 0, we conclude that
g(x) = g(0) = f (0) = 1
...
The result
follows
...
As pointed out by Noam Elkies, condition
(iii) is unnecessary
...


Proof
...
Let a1 , a2 be the smallest and secondsmallest elements of S, respectively, and put d = a2 − a1
...
Suppose that there exists an integer n contained in S but not in
{a1 , a1 + d,
...

By the hypothesis applied with (a, b, c) = (a1 , a2 , n), we see
that n − d also has the property, a contradiction
...
By dividing
B, q, r by gcd(q, r) if necessary, we may reduce to the
case where gcd(q, r) = 1
...
Let
a1 , a2 , a3 be any three distinct elements of S, labeled
so that a1 < a2 < a3 , and write rai = bi + mi q with
bi , mi ∈ Z and bi ∈ B
...
If bi − b j and bk − bl have the same sign, then we
must have
(ai − a j )(bk − bl ) = (bi − b j )(ak − al )
because both sides are of the same sign, of absolute
value less than q, and congruent to each other modulo
q
...
It follows that a4 = a1 + a3 − a2
also belongs to S (by taking b4 = b1 + b3 − b2 ), so S
satisfies the conditions of the lemma
...

Reinterpretations
...

Remark
...
Under that interpretation, however, the problem becomes false; for instance, for
q = 5, r = 1, A = [1, 3], B = [0, 2],
we have

A4 We begin with an easy lemma
...
}, S = {1, 2}
...
Let S be a finite set of integers with the following
property: for all a, b, c ∈ S with a ≤ b ≤ c, we also have a +
c − b ∈ S
...


A5 The pairs (p, n) with the specified property are those
pairs with n = 1, together with the single pair (2, 2)
...
For n = 1, it is clear
that taking v = (1) and M = (0) has the desired effect
...

0
1
0
1
We next check that no other pairs work, keeping in mind
that the desired condition means that G acts on Fnp as a
cyclic permutation
...
In particular, we have n ≥ 2
...
Decompose Fnp as a direct sum of two subspaces V,W such that
M − I is nilpotent on V and invertible on W
...
Split v as v1 +v2 with v1 ∈ V , v2 ∈ W
...
Then G(k) (w) − w ∈ V for
all nonnegative integers k
...

This gives a contradiction and thus forces W = 0
...
For any positive integer k, we have
G(k) (0) = v + Mv + · · · + M k−1 v
k−1 n−1  
j i
=∑∑
Nv
j=0 i=0 i

n−1 
k
=∑
N i v
...
This contradiction completes the proof
...
Yes, f (x, y) must be identically 0
...

Lemma 1
...
Then
f (A) + f (C) = f (B) + f (D)
...
By the fundamental
theorem of calculus, we may differentiate both sides of this
identity with respect to y to deduce that g(x, y + 1/c) = g(x, y)
...

√
Lemma 2
...
Then f (A) +
f (B) = f (A0 ) + f (B0 )
...
By continuity, it suffices to check the case where α =
arcsin d22 is an irrational multiple of 2π
...
By
Lemma 1, the claim holds when β = α
...
Since α is an irrational multiple of 2π, the positive
multiples of α fill out a dense subset of the real numbers modulo 2π, so by continuity the claim holds for all β
...
Let R be a rectangular region of arbitrary (positive) area with corners A, B,C, D labeled in counterclockwise
order
...

Proof
...
By
Lemma 2,
f (A) + f (F) = f (D) + f (E)
f (C) + f (E) = f (B) + f (F),
yielding the claim
...
The restriction of f to any straight line is constant
...
We may choose coordinates so that the line in question
is the x-axis
...

By Lemma 3, for all x ∈ R,
f (x, y) = f (x, 0) + g(y)
...
We may choose coordinates so that for some c > 0,

0=

f (u, v) du dv
x

A = (0, 0), B = (c, 0),C = (c, 1/c), D = (0, 1/c)
...

y

R

For any x, y ∈ R,

x

1
c

y
x+c

In particular, the function F(x) = xx+c f (u, 0) du is constant
...
Since c
was also arbitrary, we deduce the claim
...

0

h(x, y + 1/c) − h(x, y) =

y

3
P, as otherwise the vanishing of the zero over any rectangle would force f to vanish identically
...
Choose a rectangle R of area 1 with sides
parallel to the coordinate axes with one horizontal edge
contained in U
...
Take
P to be the vertical projection of Q onto the edge of R
contained in U
...
This constant equals the integral of f over
any rectangular region of area 1, and hence must be 0
as desired
...
In this solution, we fix coordinates and
assume only that the double integral vanishes on each
rectangular region of area 1 with sides parallel to the
coordinate axes, and still conclude that f must be identically 0
...
For s sufficiently
small, f is positive on the square of side length 2s centered at P, which we call S, and negative on the square
of side length 2s centered at Q, which we call S0
...


Lemma
...
Then the averages of f over
any two adjacent sides of R are equal
...
Without loss of generality, we may take R to have corners (0, 0), (c, 0), (c, 1/c), (0, 1/c) and consider the two sides
adjacent to (c, 1/c)
...

x



1 − 4s2
,
2s

2s
2s
≤
y
≤
−s
+
(i
+
1)
s+i

...


S ∪ A0 , An ∪ S0 , Ai ∪ Bi , Bi ∪ Ai+1
Returning to the original problem, given any c > 0, we
can tile the plane with rectangles of area 1 whose vertices lie in the lattice {(mc, n/c) : m, n ∈ Z}
...

nc

are all rectangles of area 1 with sides parallel to the coordinate axes, so the integral over f over each of these
rectangles is zero
...
But this forces the integral over S0
to be positive whereas f is negative everywhere on S0 , a
contradiction
...


f (u, 0) du =
0

c

Fixing c and taking the limit as n → ∞ yields f (0, 0) =
f (c, 0)
...

Third solution
...
Assume by
way of contradiction that f is not identically zero
...
It cannot be the case that f (P) ≤ 0 for all

B1 Each of the following functions belongs to S for the reasons indicated
...
Suppose F
is completely covered by balls of radii r1 ,
...
Put bn = ean , so that bn+1 = bn e1/bn
...


volumes sum to V
...


i=1

On the other hand, the intersection of a ball of radius r
with the plane containing F is a disc of radius at most r,
which covers a piece of F of area at most πr2 ; therefore

∑

bn+1 = bn + 1 + Rn
where 0 ≤ Rn ≤ c/bn for some absolute constant c > 0
...


i=1

n−1

By writing n as ∑ni=1 1 and applying H¨older’s inequality,
we obtain
2/3 !3
n 
4
16 3
nV 2 ≥ ∑
≥
πri3
A
...
We then see that
bn
−1
n
e n−1 Ri
≤ +∑
n i=0 n

0≤

works
...
We first note that for any collection
of m days with 1 ≤ m ≤ 2n − 1, there are at least m
distinct teams that won a game on at least one of those
days
...

If we now construct a bipartite graph whose vertices are
the 2n teams and the 2n − 1 days, with an edge linking
a day to a team if that team won their game on that day,
then any collection of m days is connected to a total of at
least m teams
...

B4 First solution
...

First note that for all x > −1, ex ≥ 1 + x and thus
x ≥ log(1 + x)
...
For
n = 0 this follows from a0 = 1
...
This
completes the induction step
...

Thus {an − log n}∞
n=0 is a decreasing sequence of positive numbers, and so it has a limit as n → ∞
...

n
n

It follows that bn /n → 1 as n → ∞
...
This problem is an example of the general
principle that one can often predict the asymptotic behavior of a recursive sequence by studying solutions of
a sufficiently similar-looking differential equation
...

B5 Define the function
f (x) = sup{x log g1 (s) + log g2 (s)}
...
The function e f (x) is
then also convex, as may be checked directly from the
definition: for x1 , x2 ∈ R and t ∈ [0, 1], by the weighted
AM-GM inequality
te f (x1 ) + (1 − t)e f (x2 ) ≥ et f (x1 )+(1−t) f (x2 )
≥ e f (tx1 +(1−t)x2 )
...
For all x, we then have
sup{g1 (s)x g2 (s)} ≥ xh1 (t) + h2 (t)
s∈R

5
with equality for x = t
...

Remark
...

B6 First solution
...
These form a cyclic group of
order p − 1, so the signature of π is also the signature
of multiplication by 3 as a permutation σ of the residue
classes modulo p − 1
...
, p − 2, then the signature equals the
parity of the number of inversions: these are the pairs
(i, j) with 0 ≤ i < j ≤ p − 2 for which σ (i) > σ ( j)
...
In particular, we only obtain inless b p−1
versions when i < 2(p − 1)/3
...
, p − 2} for
which (i, j) is an inversion correspond to the elements
of {0,
...
This contributes a total of 0 + 2 + · · · +
2(p − 2)/3 = (p − 2)(p + 1)/9 inversions
...
, p−2} for which (i, j) is an inversion correspond
to the elements of {0,
...
This contributes a total of 1+· · ·+(p−2)/3 =
(p − 2)(p + 1)/18 inversions
...
This proves the claim
...
Recall that the sign
of π (which is +1 if π is even and −1 if π is odd) can
be computed as
π(x) − π(y)
x−y
0≤x
∏

(because composing π with a transposition changes the
sign of the product)
...

x
−
y
0≤x0≤x
∏

It thus suffices to count the number of times each possible value of x2 + xy + y2 occurs
...
Since p ≡ 2 (mod 3), by the law of quadratic reciprocity we have χ(−3) = +1, so χ(c/3) = χ(−c)
...

If p ≡ 3 (mod 4), this is easy: each factor is a quadratic
residue (this is clear if c is a residue, and otherwise
χ(−c) = +1 so p + χ(−c) is divisible by 4) and −1
is not, so we must get +1 modulo p
...

i=0

The sum of the exponents, split into sums over i odd
and i even, gives
(p−3)/2 

∑

j=0

(2 j + 1)(p − 1)
j(p + 1) +
2



which simplifies to
p−1
(p − 3)(p − 1)(p + 1) (p − 1)3
+
=
8
8
2




p2 − 1
−p
...

Third solution (by Mark van Hoeij)
...
For x a nonzero
residue class modulo p of multiplicative order d, the
elements of the orbit of x under π also have order d
(because d divides p − 1 and hence is coprime to 3)
...
The parity of π is then the parity of the sum
of ϕ(d)/ f (d) over all divisors d of p−1 for which f (d)
is even
...
It thus
suffices to consider those d divisible by 4
...

If p ≡ 1 (mod 4), then d = 4 contributes a summand
of ϕ(4)/ f (4) = 2/2 = 1
...
Hence
ϕ(d)/ f (d) is even, and so the overall sum is odd
...
Note that the second proof uses quadratic
reciprocity, whereas the first and third proofs are similar to several classical proofs of quadratic reciprocity
...
Math
...
uga
...


pdf)

---

Title: The 73th William Lowell Putnam Mathematical Competition, 2012
Description: The William Lowell Putnam Mathematics Competition Is a North American math contest for college students, organized by the Mathematical Association of America (MAA). Each year on the first Saturday in December, several thousands US and Canadian students spend 6 hours (in two sittings) trying to solve 12 problems. This past papers content problems and solutions.

Buy These NotesPreview