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 74th William Lowell Putnam Mathematical Competition
Saturday, December 7, 2013

A1 Recall that a regular icosahedron is a convex polyhedron having 12 vertices and 20 faces; the faces are congruent equilateral triangles
...
Show that there are
two faces that share a vertex and have the same integer
written on them
...
For n in S, consider choices of integers a1 , a2 ,
...
For example,
2 · 3 · 6 is a perfect square, while 2 · 3, 2 · 4, 2 · 5, 2 · 3 · 4,
2 · 3 · 5, 2 · 4 · 5, and 2 · 3 · 4 · 5 are not, and so f (2) = 6
...

A3 Suppose that the real numbers a0 , a1 ,
...

1 − x 1 − x2
1 − xn+1

w(a, b)

-2
-2 -1
-1 -2
a 0 2
1 -2
2 -1

A4 A finite collection of digits 0 and 1 is written around a
circle
...
For each arc w, let Z(w) and
N(w) denote the number of 0’s in w and the number of
1’s in w, respectively
...
Suppose that
some arcs w1 ,
...
Prove that there exists an arc w with
Z(w) = Z and N(w) = N
...
, Am in Rn
...
Prove that if a list
of m3 numbers is area definite for R2 , then it is area
definite for R3
...
For
|a| , |b| ≤ 2, let w(a, b) be as in the table shown; otherwise, let w(a, b) = 0
...


(s,s0 )∈S×S

Prove that if S is any finite nonempty subset of
Z × Z, then A(S) > 0
...
)
B1 For positive integers n, let the numbers c(n) be determined by the rules c(1) = 1, c(2n) = c(n), and
c(2n + 1) = (−1)n c(n)
...


-1
-2
4
-4
4
-2

∑ c(n)c(n + 2)
...

Determine the maximum value of f (0) as f ranges
through C, and prove that this maximum is attained
...
, n}
such that:
(i) if S, S0 ∈ P, then S ∪ S0 ∈ P and S ∩ S0 ∈ P, and
(ii) if S ∈ P and S 6= 0,
/ then there is a subset T ⊂ S
such that T ∈ P and T contains exactly one fewer
element than S
...

Must there exist real numbers f1 ,
...

0≤x≤1

Show that if f and g are continuous real-valued functions defined on the interval [0, 1], then
Var( f g) ≤ 2Var( f )M(g)2 + 2Var(g)M( f )2
...
, n}, and let k ∈ X
...
[Here
f ( j) denotes the jth iterate of f , so that f (0) (x) = x and
f ( j+1) (x) = f ( f ( j) (x))
...
Alice and Bob play the following game, taking alternating turns, with Alice play-

ing first
...
Initially all spaces are empty
...

Furthermore, a move is permitted only if the resulting
position has not occurred previously in the game
...
Assuming
that both players play optimally throughout the game,
what moves may Alice make on her first turn?

Solutions to the 74th William Lowell Putnam Mathematical Competition
Saturday, December 7, 2013
Kiran Kedlaya and Lenny Ng

A1 Suppose otherwise
...
Adding this sum over all vertices
v gives 3 × 39 = 117, since each face’s label is counted
three times
...

Remark: One can also obtain the desired result by
showing that any collection of five faces must contain
two faces that share a vertex; it then follows that each
label can appear at most 4 times, and so the sum of all
labels is at least 4(0 + 1 + 2 + 3 + 4) = 40 > 39, contradiction
...
Then (n · a1 · · · ar ) · (m · b1 · · · bs ) is also a
perfect square
...
e
...
The product of what
remains must also be a perfect square, but this is now a
product of distinct integers, the smallest of which is n
and the largest of which is strictly smaller than ar = bs
...

Remark: Sequences whose product is a perfect square
occur naturally in the quadratic sieve algorithm for factoring large integers
...
Karl Mahlburg
points out the upper bound f (n) ≤ 2n for n ≥ 5, which
holds because the interval (n, 2n) contains an integer of
the form 2m2
...
For n = p prime,
the bounds agree and we have f (p) = 2p
...
org/A006255
...
By the intermediate value theorem, this is only possible if a0 + a1 y + · · · + an yn has the
same sign for 0 < y < 1; without loss of generality, we
may assume that a0 + a1 y + · · · + an yn > 0 for 0 < y < 1
...
, with strict inequality for m > 0
...


A4 Let w01 ,
...
e
...
Since w j has length Z(w j ) + N(w j ), the
sum of the lengths of w1 ,
...
, w0k is a string of k(Z + N) consecutive digits around the circle
...
) Break this
string into k arcs w001 ,
...
(Note that if the number of digits around the circle is m, then Z + N ≤ m
since Z(w j ) + N(w j ) ≤ m for all j, and thus each of
w001 ,
...
)
We claim that for some j = 1,
...
Otherwise,
since all of the Z(w00j ) differ by at most 1, either
Z(w00j ) ≤ Z − 1 for all j or Z(w00j ) ≥ Z + 1 for all j
...
But since w1 = w01 , we have |kZ − ∑ j Z(w0j )| =
| ∑kj=1 (Z(w j ) − Z(w0j ))| = | ∑kj=2 (Z(w j ) − Z(w0j ))| ≤
∑kj=2 |Z(w j ) − Z(w0j )| ≤ k − 1, contradiction
...
, Am be points in R3 , and let nˆ i jk denote a
unit vector normal to ∆Ai A j Ak (unless Ai , A j , Ak are
collinear, there are two possible choices for nˆ i jk )
...

ˆ Thus if {ai jk } is area
definite for R2 , then for any n,
ˆ

∑ ai jk Area(∆Ai A j Ak )|nˆi jk · n|ˆ ≥ 0
...

Thus integrating the above inequality over nˆ gives
c ∑ ai jk Area(∆Ai A j Ak ) ≥ 0
...

Remark: It is not hard to check (e
...
, by integration
in spherical coordinates) that the constant c occurring
above is equal to 2π
...

More generally, let C be a convex body in Rn
...

ˆ Then the average over nˆ of the

2
Now suppose that f = 1 + ∑Nn=1 an cos(2πnx) ∈ C
...
Thus an cos(2πn/3) = −an /2 for all
n, and f (1/3) = 1 − ∑Nn=1 (an /2)
...


volume of the projection of C onto Πnˆ equals a constant
(depending only on n) times the (n − 1)-dimensional
surface area of C
...
This field has important applications in imaging
and tomography
...


(a,b)∈Z2

Then A(S) is the constant coefficient of the Laurent
polynomial h(x, y) = f (x, y) f (x−1 , y−1 )g(x, y)
...
For any i ∈ {1,
...

Proof
...
By (ii), there must be a subset T ⊂ S containing P
with exactly one fewer element than S
...

Lemma 2
...
, n}, S1 is the disjoint union of T1 with {i}
and S2 is the disjoint union of T2 with {i}
...


0

Z 2π Z 2π 
0

B3 Yes, such numbers must exist
...



 f (eis , eit )2 g(eis , eit ) dt ds
...
By (i) we have
f (T1 ∪ T2 ∪ {i}) = f (S1 ) + f (T2 ) − f (T1 ∩ T2 )
f (T1 ∪ T2 ∪ {i}) = f (T1 ) + f (S2 ) − f (T1 ∩ T2 ),

Consequently, it is enough to check that g(eis , eit ) is a
nonnegative real number for all s,t ∈ R
...

G(z, w) = zw + z2 + w2 − z2 w − zw2 − z2 w2
...
, fn as follows
...
Otherwise, by
Lemma 1, we can find S, T ∈ P such that S is the disjoint
union of T with {i}
...


If z, w ∈ [−1, 1] and zw ≥ 0, then
G(z, w) = zw(1 − zw) + z2 (1 − w) + w2 (1 − z) ≥ 0
...
This provides the base case for an induction
on the cardinality of S; for any nonempty S ∈ P, we may
apply (ii) to find T ⊂ S such that S is the disjoint union
of T and some singleton set { j}
...


2

G(z, w) = (z + w) − zw(1 + z)(1 + w) ≥ 0
...

B1 Note that
c(2k + 1)c(2k + 3) = (−1)k c(k)(−1)k+1 c(k + 1)
= −c(k)c(k + 1)
= −c(2k)c(2k + 2)
...


Remark: Karl Mahlburg points out the general formula
c(n) = (−1)b0 b1 +b1 b2 +···+bk−1 bk for n having binary representation bk · · · b0
...
This
is attained for N = 2, a1 = 34 , a2 = 32 : in this case
f (x) = 1+ 43 cos(2πx)+ 23 cos(4πx) = 1+ 34 cos(2πx)+
2
1
2
2
3 (2 cos (2πx)−1) = 3 (2 cos(2πx)+1) is always nonnegative
...
Now since |g(x)| ≤
R
M(g) for all x, 0 ≤ 01 f0 (x)2 (M(g)2 − g(x)2 ) dx =
R
Var( f )M(g)2 − 01 f0 (x)2 g(x)2 dx, and similarly 0 ≤
R
Var(g)M( f )2 − 01 f (x)2 g0 (x)2 dx
...

(1)

Now
Z 1
0

( f0 (x)2 g(x)2 + f (x)2 g0 (x)2 ) dx − Var( f g)

Z 1

=
0

( f0 (x)2 g(x)2 + f (x)2 g0 (x)2 − ( f (x)g(x) −

Z 1
0

f (y)g(y) dy)2 ) dx;

3
substituting f0 (x) + µ( f ) for f (x) everywhere and
g0 (x) + µ(g) for g(x) everywhere, and using the fact
R
R
that 01 f0 (x) dx = 01 g0 (x) dx = 0, we can expand and
simplify the right hand side of this equation to obtain
Z 1
0

2

2

2

the induction hypothesis, we compute the number of
functions which iterate X into {1,
...
, k} to be
n−k

∑ (n − k − 1) · · · (n − k − ` + 1)(k + `)nn−`−1

2

( f0 (x) g(x) + f (x) g0 (x) ) dx − Var( f g)

Z 1

=
0

`=1

By rewriting this as a telescoping sum, we get

f0 (x)2 g0 (x)2 dx

− 2µ( f )µ(g)

Z 1
0

≥ −2µ( f )µ(g)

n−k

Z 1

f0 (x)g0 (x) dx + (

0

∑ (n − k − 1) · · · (n − k − ` + 1)(n)nn−`−1

2

f0 (x)g0 (x) dx)

`=1
n−k

Z 1
0

− ∑ (n − k − 1) · · · (n − k − ` + 1)(n − k − `)nn−`−1

f0 (x)g0 (x) dx
...


(µ(g)2 f0 (x)2 + µ( f )2 g0 (x)2 )dx

= Var( f )µ(g)2 + Var(g)µ( f )2
≤ Var( f )M(g)2 + Var(g)M( f )2 ,
establishing (2) and completing the proof
...
For T a set and S1 , S2 two subsets of T , we say
that a function f : T → T iterates S1 into S2 if for each
x ∈ S1 , there is a j ≥ 0 such that f ( j) (x) ∈ S2
...
Fix k ∈ X
...
, k} and f (x) = g(x) for x ∈ {k +
1,
...
Then g also iterates X into {1,
...

Proof
...
, k}
...
, n} for 0 ≤ i < j
...
, j, so
in particular g( j) (x) ∈ {1,
...
This proves the claim
...


(2)
Now since (µ(g) f0 (x) − µ( f )g0 (x))2 ≥ 0 for all x, we
have
2µ( f )µ(g)

∑

as desired
...


Lemma 2
...

Proof
...
If ` = n then there is nothing to check
...
The
contraction g of f at {∗}∪S is then a function on {∗}∪(X −S)
with f −1 (∗) = {∗} ∪ T which iterates X − S into {∗}
...
Summing over T and invoking the induction
hypothesis, we see that the number of functions f is
n−` 

We proceed by induction on n−k, the case n−k = 0 being trivial
...
, k + 1} but not into {1,
...
These are precisely the functions for which
there is a unique cycle C containing only numbers in
{k + 1,
...
Suppose C
has length ` ∈ {1,
...
For a fixed choice

of `,
we may choose the underlying set of C in n−k−1
ways
`−1
and the cycle structure in (` − 1)! ways
...
, k} ∪C
...
, k} ∪ C
...

We now count functions f : X → X which iterate X
into {1,
...
By Lemma 1 of the first
solution, this count equals nk times the number of
functions with f (1) = · · · = f (k) = 1 which iterate X
into {1,
...
For such a function f , put S = {k +
1,
...
, k}) and let g be the contraction
of f at {1,
...
By Lemma 2, for ` = #S, there are
`(n − k)n−k−`−1 such functions g
...
, k}
...


The desired count is this times nk , or knn−1 as desired
...
Such trees can be counted using Cayley’s
formula, a special case of Kirchoff’s matrix tree theorem
...
(One
can also use Pr¨ufer sequences for a more combinatorial
interpretation
...
We start with some
terminology
...
By the
extremal blocks, we mean the (possibly empty) maximal blocks adjacent to the left and right ends of the
playing area
...
For i = 0,
...
Define the
end zone as the union Z = Pn−1 ∪ Pn
...

– Any move of type 1 from Pi ends in Pi+1
...

– For i < n, any move of type 2 from Pi ends in Pi ∪
Pi+1
...

– For i < n − 1, if we start at a position in Pi where
the extremal blocks have length a, b, then the only
possible moves to Pi decrease one of a, b while
leaving the other unchanged (because they are
separated by at least two empty spaces)
...

– From any position in the end zone, the legal moves
are precisely to the other positions in the end

zone which have not previously occurred
...

– At this point, we may change the rules without
affecting the outcome by eliminating the rule on
repetitions and declaring that the first player to
move into the end zone loses (because #Z = n + 1
is even)
...
, n from left to right
...
For any given
position outside of the end zone, for each s = 1,
...
Otherwise, s inhabits a block running from i + 1 to j − 1 with
i and j empty (or equal to 0 or n+1), so the type 2 move
at i + j − s (which belongs to the same block) does the
job
...
We check this for positions in
Pi for i = n − 2,
...
For
positions in Pn−2 , the only safe moves are in the extremal blocks; we may thus analyze these positions
as two-pile Nim with pile sizes equal to the lengths
of the extremal blocks
...
In other words, a position is
a win for the player to move unless the empty spaces
are at s and n + 1 − s for some s ∈ {1,
...
Given the analysis of positions in Pi+1
for some i, it is clear that if a position in Pi has weight
s 6= (n+1)/2, there is a winning move of weight t where
s + t ≡ (n + 1)/2 (mod n), whereas if s = (n + 1)/2
then no move leads to a winning position
...

Remark: Despite the existence of a simple description
of the winning positions, it is nonetheless necessary to
go through the preliminary analysis in order to establish
the nature of the end zone and to ensure that the repetition clause does not affect the availability of moves
outside of the end zone
...

Remark: It is easy to see that Alice’s winning strategy
is to ensure that after each of her moves, the stones are
placed symmetrically and the central space is occupied
...


– The property of being balanced is invariant under
left-right symmetry
...


Remark: To resolve a mild ambiguity in the problem
statement, it should be clarified that the initial position
(with no stones placed) should be treated as having occurred previously once the first move has been made
...


– Every position in Pn−2 is unbalanced, because
a0 < a0 + a1 < a1 + (n + 1)
...
We give a partial analysis based on an argument from Art of Problem
Solving user gnayijoag, with some clarification from
Savitt
...
Define the sets Pi and the end zone Z as before
...

That is, every position in Pn−2 is a winning position for
the player to move
...

This suggests that if we want to introduce a numerical invariant that detects the difference between winning and losing positions for the player to move, we
must consider a formula that selectively discards some
information about some of the stones
...
, k − 1);
note that f (x, 0) > · · · > f (x, k − 1)
...
This
definition then has the following properties
...
We
must then have A(x) − t = 1 + · · · + n − (n + 1) =
(n/2 − 1)(n + 1), so x is balanced if and only if
f (x, n/2 − 1) = 0
...

– From every balanced position x ∈ Pn−k for k ≥ 3,
every move leads to an unbalanced position
...
Let y be the
result of a move from x
...
, n}
...
, at−1
and 0 < A(x) − A(y) < at ; consequently,
f (y,t − 1) = f (x,t − 1) − (A(x) − A(y))
≥ ( f (x,t) + at − at−1 + (n + 1)) − (at − 1)
= n + 2 − at−1 > 0
...
Since f (y,t) < 0 < f (y,t − 1), y is
unbalanced
...




---