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 69th William Lowell Putnam Mathematical Competition
Saturday, December 6, 2008
A1 Let f : R2 → R be a function such that f (x, y)+ f (y, z)+
f (z, x) = 0 for all real numbers x, y, and z
...

A2 Alan and Barbara play a game in which they take turns
filling entries of an initially empty 2008 × 2008 array
...
At each turn, a player chooses a real
number and places it in a vacant entry
...
Alan wins if the determinant of the resulting matrix is nonzero; Barbara wins if
it is zero
...
, an of positive integers
...
Prove that if this process
is repeated, it must eventually stop and the final sequence does not depend on the choices made
...
)
A4 Define f : R → R by
(
x
if x ≤ e
f (x) =
x f (ln x) if x > e
...
Let f (x) and g(x) be polynomials with real coefficients such that the points
( f (1), g(1)), ( f (2), g(2)),
...

Prove that at least one of f (x) and g(x) has degree
greater than or equal to n − 1
...


(The elements of G in the sequence are not required to
be distinct
...
)
B1 What is the maximum number of rational points that can
lie on a circle in R2 whose center is not a rational point?
(A rational point is a point both of whose coordinates
are rational numbers
...
For n ≥ 0 and x > 0, let Fn+1 (x) =
x
0 Fn (t) dt
...

ln n
B3 What is the largest possible radius of a circle contained
in a 4-dimensional hypercube of side length 1?
n→∞

B4 Let p be a prime number
...
, h(p2 − 1)
are distinct modulo p2
...
, h(p3 −
1) are distinct modulo p3
...
(The
denominator of a rational number q is the unique positive integer b such that q = a/b for some integer a with
gcd(a, b) = 1
...
)
B6 Let n and k be positive integers
...
, n} is k-limited if |σ (i) − i| ≤ k for all
i
...
, n} is odd if and only if n ≡ 0 or 1 (mod 2k +1)
...

Substituting
(x, y, z) = (0, 0, 0) into the given functional equation yields f (0, 0) = 0, whence substituting (x, y, z) =
(x, 0, 0) yields f (x, 0) + f (0, x) = 0
...

Remark: A similar argument shows that the possible
functions g are precisely those of the form f (x, 0) + c
for some c
...

First solution: Pair each entry of the first row with the
entry directly below it in the second row
...
If
Alan writes a number anywhere other than the first two
rows, Barbara does likewise
...

Second solution: (by Manjul Bhargava) Whenever
Alan writes a number x in an entry in some row, Barbara writes −x in some other entry in the same row
...

A–3 We first prove that the process stops
...
Moreover, the last number in
the sequence can never decrease, because it is always
replaced by its least common multiple with another
number
...
After this happens, the next-to-last
number will never decrease, so it eventually becomes
constant, and so on
...
This only happens when a j divides ak
for all pairs j < k
...
For p a prime and m a nonnegative integer, we
claim that the number of integers in the list divisible
by pm never changes
...
If neither of a j , ak is
divisible by pm , then neither of gcd(a j , ak ), lcm(a j , ak )
is either
...

gcd(a j , ak ), lcm(a j , ak ) are as well
...
, a0n , the numbers a0h+1 ,
...
, a0h are not
...
, an ,
we can determine the exact prime factorization of each
of a01 ,
...
This proves that the final sequence is
unique
...
One is to observe that ∏ j a jj is strictly increasing at each step, and
bounded above by (a1 · · · an )n
...

Reinterpretation: For each p, consider the sequence
consisting of the exponents of p in the prime factorizations of a1 ,
...
At each step, we pick two positions
i and j such that the exponents of some prime p are in
the wrong order at positions i and j
...

It is clear that this can only terminate with all sequences being sorted into the correct order
...

This can be done as in the first solution
...

(This is a variant of the worst-case analysis of the bubble sort algorithm
...

At each step, we find one bad pair (i, j) and eliminate
it, and we do not touch any pairs that do not involve
either i or j
...
If k < i, then (k, i) can only become a bad pair if
ak divided ai but not a j , in which case (k, j) stops being
bad
...
Hence the number of bad
pairs goes

down by at least 1 each time; since it is at
most n2 to begin with, this is an upper bound for the
number of steps
...
Namely,
if a1 ,
...
, a0n are the sequences obtained
at two different steps in the process, then the abelian

2
groups Z/a1 Z × · · · × Z/an Z and Z/a01 Z × · · · × Z/a0n Z
are isomorphic
...

Remark: (by Tom Belulovich) A lattice is a partially
ordered set L in which for any two x, y ∈ L, there is a
unique minimal element z with z ≥ x and z ≥ y, called
the join and denoted x ∧ y, and there is a unique maximal element z with z ≤ x and z ≤ y, called the meet
and denoted x ∨ y
...
Start
with a1 ,
...
If i < j but ai 6≤ a j , it is permitted to replace ai , a j by ai ∨ a j , ai ∧ a j , respectively
...
The question is, under what
conditions on the lattice L is the final sequence uniquely
determined by the initial sequence?
It turns out that this holds if and only if L is distributive,
i
...
, for any x, y, z ∈ L,
x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z)
...
) For example, if L is a Boolean
algebra, i
...
, the set of subsets of a given set S under inclusion, then ∧ is union, ∨ is intersection, and the distributive law holds
...
The correspondence takes each x ∈ L to
the set of y ∈ L such that x ≥ y and y cannot be written
as a join of two elements of L \ {y}
...
Math
...
, 1967
...

For instance, this can be checked by forming the smallest subset L0 of L containing a1 ,
...
It can also be checked directly (as suggested by Nghi Nguyen) by showing that
for j = 1,
...
, an is invariant at each step
...
(For a
proof, see the Birkhoff reference given above
...

Consequently, the final sequence is determined by the
initial sequence if and only if L is distributive
...
From the definition, f (x) = x on
e
[1, e], x ln x on (e, ee ], x ln x ln ln x on (ee , ee ], and so
forth
...
Thus ∑∞
n=1 f (n) , if it converges, is
bounded below by
integral diverges
...

If we write y = lnk x, then
k
x = exp y and dx = (expk y)(expk−1 y) · · · (exp1 y)dy =
x(ln1 x) · · · (lnk−1 x)dy
...


dx
=
f (x)

Z 1

dy = 1
...
It suffices to prove that P has degree at
least n − 1, as then one of f , g must have degree at least
n − 1
...
, ζnn for ζn = exp(2πi/n)
...
, n
...
, m has degree
at least m − 1
...

First solution: If Q(z) has degree d and leading coefficient c, then R(z) = Q(z + 1) − tQ(z) has degree d and
leading coefficient (1 − t)c
...
, m − 1, so we must
have d ≥ m − 1
...
For
the base case m = 1, we have Q(1) = t 1 6= 0, so Q must
be nonzero, and so its degree is at least 0
...
, m, then
the polynomial R(z) = (t − 1)−1 (Q(z + 1) − Q(z)) has
degree one less than that of Q, and satisfies R(i) = t i
for i = 1,
...
Since R must have degree at least
m − 2 by the induction hypothesis, Q must have degree
at least m − 1
...


3
Namely, the (m − 1)-st finite difference of P evaluated
at 1 equals


m−1
j m−1
(−1)
Q(m − j) = t(1 − t)m−1 6= 0,
∑
j
j=0
which is impossible if Q has degree less than m − 1
...

A–6 For notational convenience, we will interpret the problem as allowing the empty subsequence, whose product
is the identity element of the group
...

First solution: Put n = |G|
...
Let H be the set of elements
produced by the sequence S
...
If at any point
the set H −1 H = {h1 h2 : h−1
1 , h2 ∈ H} fails to be all of G,
extend S by appending an element g of G not in H −1 H
...
Thus we can extend S by
one element and double the size of H
...
, ak for which H −1 H = G
...
, a1 , a1 ,
...

Second solution:
Put m = |H|
...
To see this, we compute

∑ |H ∪ Hg| = ∑ (|H| + |Hg| − |H ∩ Hg|)

g∈G

g∈G

= 2mn −

∑ |H ∩ Hg|

g∈G

= 2mn − |{(g, h) ∈ G2 : h ∈ H ∩ Hg}|
= 2mn −

∑ |{g ∈ G : h ∈ Hg}|
h∈H

= 2mn −

∑ |H −1 h|
h∈H
2

= 2mn − m
...

In other words, by extending the sequence by one element, we can replace the ratio s = 1−m/n (i
...
, the fraction of elements of G not generated by S) by a quantity

no greater than
1 − (2m − m2 /n)/n = s2
...
It is enough to prove that for
some c > 0, we can always find an integer k ≤ c ln n
such that

k
1 2
1
1−
< ,
n
n
as then we have n − m < 1 and hence H = G
...
From the facts that ln n ≤ ln 2 + (n −
2)/2 ≤ n/2 and ln(1 − 1/n) < −1/n for all n ≥ 2, we
have


1
n2
n
k
2 ln 1 −
< − = − < − ln n,
n
2n
2
yielding the desired inequality
...
e
...
This strategy is used in a
number of recent results of Bourgain, Tao, Helfgott, and
others on small doubling or small tripling of subsets of
finite groups
...
This is close to optimal: one cannot use fewer than log2 n terms because
the number of subsequences must be at least n
...
For example,
the points (0, 0) and (1, 0) lie on a circle with center
(1/2, x) for any real number x, not necessarily rational
...
The
midpoint M of the side PQ is ((a + c)/2, (b + d)/2),
which is again rational
...

Similarly, if N is the midpoint of QR, then N is a rational
point and the line through N perpendicular to QR has
rational slope
...
Moreover, these equations have a
unique solution
...
This proves the desired result
...
A shorter way to say this
is that any two distinct rational points determine a rational line (a line of the form ax + by + c = 0 with a, b, c
rational), while any two nonparallel rational lines intersect at a rational point
...

Remark: A more explicit argument is to show that
the equation of the circle through the rational points
(x1 , y1 ), (x2 , y2 ), (x3 , y3 ) is

 2
x1 + y21 x1 y1 1
x2 + y2 x2 y2 1
2
2

0 = det 
x2 + y2 x3 y3 1
3
3
x 2 + y2 x y 1
which has the form a(x2 + y2 ) + dx + ey + f = 0
for a, d, e, f rational
...

B–2 We claim that Fn (x) = (ln x − an )xn /n!, where an =
∑nk=1 1/k
...

Given the claim, we have Fn (1) = −an /n! and so we
need to evaluate − limn→∞ lnann
...
It follows that limn→∞ lnann = 1, and
the desired limit is −1
...
It will be convenient
to solve the problem for a hypercube of side length 2
instead, in which
√ case we are trying to show that the
largest radius is 2
...
Let C be a circle centered
at the point P
...
Consequently, if we translate C so
that its center moves to the point O = (0, 0, 0, 0) at the
center of H, then it remains entirely inside H
...
Let v1 = (v11 ,
...
, v24 ) be two points on C lying on radii perpendicular to each other
...
Then
C lies in H if and only if for each i, we have
|v1i cos θ + v2i sin θ | ≤ 1

(0 ≤ θ < 2π)
...
Since

this holds for the unit vector in the same direction as
(v1i , v2i ), we must have
v21i + v22i ≤ 1

(i = 1,
...


Conversely, if this holds, then the Cauchy-Schwarz inequality and the above analysis imply that C lies in H
...
Since this is achieved by the circle through
(1, 1, 0, 0) and (0, 0, 1, 1), it is the desired maximum
...

Daniel Kane gives the following argument
p to show that
the maximum radius in this case is 12 nk
...
)
We again scale up by a factor of 2, so that we are trying
to show that the maximum radius r of a k-dimensional
p
ball contained in the hypercube [−1, 1]n is nk
...
Let T : Rk → Rn be a similitude carrying the
unit ball to this embedded k-ball
...
, en the standard basis
of Rn , x · vi = T (x) · ei for all x ∈ Rk
...

i=1

Let M be the matrix with columns v1 ,
...
We then
have
kr2 = Trace(r2 Ik ) = Trace(MM T )
n

= Trace(M T M) = ∑ |vi |2
i=1

≤ n,
yielding the upper bound r ≤

pn

k
...
, vn )
...
Startw with any projection
...
, wn be the projections of e1 ,
...
If the desired
condition is not achieved, we can choose i, j such that
1
|wi |2 < (|w1 |2 + · · · + |wn |2 ) < |w j |2
...
We can thus choose
such a rotation to force one of |wi |2 , |w j |2 to become
equal to 1n (|w1 |2 + · · · + |wn |2 )
...

B–4 We use the identity given by Taylor’s theorem:
h(x + y) =

deg(h) (i)
h (x)

∑

i!

i=0

yi
...

For x = 0,
...

(This can also be deduced more directly using the binomial theorem
...
Since h0 is a polynomial with integer coefficients, we have h0 (x) ≡ h0 (x + mp) (mod p) for any
integer m, and so h0 (x) 6≡ 0 (mod p) for all integers x
...
, p2 − 1 and y = 0,
...

Thus h(x), h(x+ p2 ),
...
Since the h(x) themselves cover all the residue
classes modulo p2 , this proves that h(0),
...

Remark: More generally, the same proof shows that
for any integers d, e > 1, h permutes the residue classes
modulo pd if and only if it permutes the residue classes
modulo pe
...

B–5 The functions f (x) = x + n and f (x) = −x + n for any
integer n clearly satisfy the condition of the problem;
we claim that these are the only possible f
...
For n any positive integer, we have
a
f ( an+1
bn ) − f ( b )
1
bn


= bn f


a
an + 1
− nb f
bn
b

is an integer by the property of f
...
It follows that for sufficiently large n, both sides must be

a
c
equal to some integer c = f 0 ( ab ): f ( an+1
bn ) = f ( b ) + bn
...

Similarly, |c| cannot be greater than 1: otherwise if we
take n = k|c| for k a sufficiently large positive integer,
c
then f ( ab ) + bn
has denominator bk, contradicting the
an+1
fact that f ( bn ) has denominator bn
...


Thus the derivative of f at any rational number is ±1
...
Since
f (0) must be an integer (a rational number with denominator 1), f (x) = x+n or f (x) = −x+n for some integer
n
...

One can then write f (x) = ax + b and check that b ∈ Z
by evaluation at a = 0, and that a = ±1 by evaluation at
x = 1/a
...
, n}
...
Consequently, the number of k-limited permutations of {1,
...
, n}
...
, n} is odd if n = 0, 1 and even otherwise
...

For n ≤ k + 1, all involutions are k-limited
...
, k + 1
...
, n
...
, k + 1} which map into A under σ depends
only on C, not on σ
...
Consequently, |C| is even unless S(C) has at most one element
...
Hence if S(C) has
one element and σ ∈ C, we must have σ (1) = 1
...
By induction, for i = 3,
...

If n < 2k + 1, this shows that no class C of odd cardinality can exist, so Fn,k must be even
...
, n}, so Fn,k has the
same parity as Fn−2k−1,k
...


6
Second solution: (by Yufei Zhao) Let Mn,k be the n × n
matrix with
(
1 |i − j| ≤ k
(Mn,k )i j =
0 otherwise
...
, n} of (Mn,k )1σ (1) · · · (Mn,k )nσ (n) times the signature of σ
...
We conclude that
det(Mn,k ) ≡ Fn,k

(mod 2)
...
We compute its determinant using linear algebra modulo 2
...
We do this by computing det(Mn,k ) using row and column operations
...

To begin with, Mn,k has the following form
...
The symbol 0/ indicates that the unseen entries are all zeroes, while the
symbol ? indicates that they are not
...

We will preserve the unseen structure of the matrix by
only adding the first k + 1 rows or columns to any of the
others
...
, k + 1
...
, k + 1
...
, 2k + 1 for which the
( j, k + i)-entry is nonzero, add row i to row j
...
, k + 1 in succession
...
That is, for i = 2,
...
, 2k +1 for which the ( j, k +i)-entry
is nonzero, add row i to row j
...
We conclude that
det(Mn,k ) ≡ det(Mn−2k−1,k ) (mod 2),
proving the desired congruence
...
, F2k,k are even
...
, k + 1, the matrix Mn,k consists of all ones, so its
determinant is 1 if n = 0, 1 and 0 otherwise
...
, k + 1, since
every permutation of {1,
...
) For n =
k + 2,
...

Third solution: (by Tom Belulovich) Define Mn,k as
in the second solution
...

Let ri denote row i of Mn,k
...
, 2k (mod 2k + 1), then Mn,k is not invertible
...
Put j = (n + a + b)/(2k +
1)
...


i=0

Hence Mn,k is not invertible
...
Suppose that a1 ,
...
The m-th coordinate of this vector equals am−k + · · · + am+k , where
we regard ai as zero if i ∈
/ {1,
...
By comparing
consecutive coordinates, we obtain
am−k = am+k+1

(1 ≤ m < n)
...
Taking
m = 1,
...
, n − 1 yields
an−2k = · · · = an−1−k = 0
...

In either case, since we also have
a1 + · · · + a2k+1 = 0
from the (k + 1)-st coordinate, we deduce that all of the
ai must be zero, and so Mn,k must be invertible
...
They are also examples of
Toeplitz matrices

---