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 67th William Lowell Putnam Mathematical Competition
Saturday, December 2, 2006

A–1 Find the volume of the region of points (x, y, z) such that
(x2 + y2 + z2 + 8)2 ≤ 36(x2 + y2 )
...

The number of stones removed at each turn must be one
less than a prime number
...
Alice plays first
...
(For example, if n = 17, then Alice might take 6
leaving 11; then Bob might take 1 leaving 10; then Alice can take the remaining stones to win
...
, 2005, 2006, 2007, 2009, 2012, 2016,
...
, 2006
and xk+1 = xk + xk−2005 for k ≥ 2006
...

A–4 Let S = {1, 2,
...
Say a permutation π of S has a local maximum at k ∈ S if
(i) π(k) > π(k + 1) for k = 1;
(ii) π(k − 1) < π(k) and π(k) > π(k + 1) for 1 < k <
n;
(iii) π(k − 1) < π(k) for k = n
...
) What is the
average number of local maxima of a permutation of S,
averaging over all permutations of S?
A–5 Let n be a positive odd integer and let θ be a real number such that θ /π is irrational
...
, n
...

A–6 Four points are chosen uniformly and independently at
random in the interior of a given circle
...


B–1 Show that the curve x3 + 3xy + y3 = 1 contains only one
set of three distinct points, A, B, and C, which are vertices of an equilateral triangle, and find its area
...
, xn } of n real
numbers, there exists a non-empty subset S of X and an
integer m such that




1



...
A linear partition of S is an unordered pair {A, B} of subsets of S such
that A ∪ B = S, A ∩ B = 0,
/ and A and B lie on opposite
sides of some straight line disjoint from S (A or B may
be empty)
...
For each positive integer n, find the maximum of LS
over all sets S of n points
...
(Thus Z has 2n elements, which are the vertices of a unit hypercube in Rn
...
Let k be given, 0 ≤ k ≤ n
...
[Editorial note:
the proposers probably intended to write Z(V ) instead
of “the number of points in V ∩ Z”, but this changes
nothing
...
Find the maximum value of I( f ) − J( f ) over all such functions f
...
Suppose a0 > 0, and
define
1
an+1 = an + √
k a
n
for n > 0
...

n→∞ nk
lim

Solutions to the 67th William Lowell Putnam Mathematical Competition
Saturday, December 2, 2006
Kiran Kedlaya and Lenny Ng

A–1 We
p change to cylindrical coordinates, i
...
, we put r =
x2 + y2
...

This defines a solid of revolution (a solid torus); the
area being rotated is the disc (x − 3)2 + z2 ≤ 1 in the
xz-plane
...
That is, the total volume is 6π 2
...
, bm }
...

That is, every nonnegative integer not in B can be written as b+ p−1 for some b ∈ B and some prime p
...

First solution: Let t be any integer bigger than all of
the b ∈ B
...
g
...
, (t +1)!+t +1
...

Second solution: Let p1 ,
...

x − bn ≡ −1

(mod p1 pm+1 )
(mod pm p2m )
...

Third solution: (by Catalin Zara) Put b1 = 0, and take
n = (b2 − 1) · · · (bm − 1); then n is composite because
3, 8 ∈ B, and for any nonzero b ∈ B, n − bi + 1 is divisible by but not equal to bi − 1
...
)
A–3 We first observe that given any sequence of integers
x1 , x2 ,
...
, xk−n )

(k > n),

where n is fixed and f is a fixed polynomial of n variables with integer coefficients, for any positive integer
N, the sequence modulo N is eventually periodic
...

We next observe that if one can rewrite the same recursion as
xk−n = g(xk−n+1 ,
...
, x−1 , x0 , x1 ,
...
That is the case in the situation at hand,
because we can rewrite the given recursion as
xk−2005 = xk+1 − xk
...
Running the recursion
backwards, we easily find
x1 = x0 = · · · = x−2004 = 1
x−2005 = · · · = x−4009 = 0,
yielding the desired result
...
, n
...
Similarly, for k = n, the probability is
1/2
...
Thus the average number of
local maxima is
2·

1
1 n+1
+ (n − 2) · =

...
, n} occurs as a local maximum
...
, n, ∗ written in a circle
in some order
...
, i − 1}
...

3
One can obtain a similar (if slightly more intricate) solution inductively, by removing the known local maximum n and splitting into two shorter sequences
...
The complete distribution for the number of peaks is known; Richard Stanley suggests the reference: F
...
David and D
...
Barton, Combinatorial
Chance, Hafner, New York, 1962, p
...

A–5 Since the desired expression involves symmetric functions of a1 ,
...
, an as roots
...

Consequently, if we put ω = e2inθ , then the polynomial
Qn (x) = (1 + ix)n − ω(1 − ix)n

expected value of a random variable over all choices of
P, Q, R
...

If P, Q, R, S are the four points, we may ignore the case
where three of them are collinear, as this occurs with
probability zero
...

There are four such configurations, depending on which
point lies inside the triangle, and they are mutually exclusive
...

That latter probability is simply E([PQR]) divided by
the area of the disc
...
We
can write
[PQR] = ±[OPQ] ± [OQR] ± [ORP]
for a suitable choice of signs, determined as follows
...
If P0 , Q0 , R0 lie on a semicircle
in that order and Q lies inside the triangle OPR, then
the sign on [OPR] is positive and the others are negative
...

We first calculate
E([OPQ] + [OQR] + [ORP]) = 3E([OPQ])
...

2

has among its roots a1 ,
...
Since these are distinct
and Qn has degree n, these must be exactly the roots
...
g
...
The distribution of θ is uniform on
[0, π]
...
By inspection,

E([OPQ])
Z 1
2  Z π

1
1
2r2 dr
sin(θ ) dθ
=
2 0
π 0
4
=
,
9π

cn−1 = nin−1 − ωn(−i)n−1 = nin−1 (1 − ω)
c0 = 1 − ω
so
a1 + · · · + an
=
a1 · · · an

(
n
n≡1
−n n ≡ 3

(mod 4)
(mod 4)
...
, an is independent of θ
...
We start with some notation and simplifications
...
Let E denote the

and
E([OPQ] + [OQR] + [ORP]) =

4

...
Put θ1 = ∠POQ and θ2 = ∠QOR; then
the distribution of θ1 , θ2 is uniform on the region
0 ≤ θ1 ,

0 ≤ θ2 ,

θ1 + θ2 ≤ π
...
Put rP = OP, rQ = OQ, rR = OR
...
Write E 0 (X) for
the expectation of a random variable X restricted to this
part of the domain
...
We now compute
E 0 ([OPR])

Z 1
2 Z π
1
2θ
2
sin(θ ) dθ
=
2r dr
2
2 0
0 π
4
=
9π
E 0 (χ[OPR])
= E 0 (2[OPR]2 /θ )

Z 1
2 Z π
1
2θ −1 2
θ
sin
(θ
)
dθ
=
2r3 dr
2
2 0
0 π
1
=

...

Let χ be the random variable with value 1 if Q is inside
triangle OPR and 0 otherwise
...

3
36π
Finally, note that the case when P0 , Q0 , R0 lie on a semicircle in some order occurs with probability 3/4
...
) Hence
E([PQR])
= E([OPQ] + [OQR] + [ORP])
3
− E 0 ([OPQ] + [OQR] + [ORP] − [PQR])
4
4
29
35
=
−
=
,
3π 48π
48π
so the original probability is
1−

4E([PQR])
35
= 1−

...
Draw

the lines PQ, QR, RP, which with probability 1 divide
the interior of the circle into seven regions
...
Put A =
E(a), B = E(b1 ), C = E(c1 ), so that A + 3B + 3C = π
...
By comparing expectations, we have 3C + A = 4A, so A = C and 4A + 3B = π
...
Let h be
the distance from the center O of the circle to the line
DE
...

Put r = OD; the distribution of r is 2r on [0, 1]
...
For fixed r, the distribution of
h runs over [0, r], and can be computed as the area of
the infinitesimal region in which E can be chosen so the
chord through DE has distance to O between h and h +
dh, divided by π
...

The angle between these is dθ = dh/(r2 − h2 )
...
Since
{L1 , L2 } =

p

1 − h2 ±

p

r2 − h2 ,

the area we are seeking (after doubling) is
1 + r2 − 2h2
2 √

...

3π

We now return to computing B + 2A
...
The chance that the third point
is in the smaller (resp
...

1 − A(h)/π), and then the area we are trying to compute is π − A(h) (resp
...
Using the distribution on
h, and the fact that
A(h) = 2

Z 1p

1 − h2 dh

h

=

p
π
− arcsin(h) − h 1 − h2 ,
2

4
√
(−1, −1) to (1/2, 1/2), or 3 2/2
...


we find
B + 2A
16
2 1
A(h)(π − A(h)) (1 − h2 )3/2 dh
π 0
3π
35 + 24π 2
=

...


35
48π

x3 + y3 + z3 − 3xyz
as in the

Third solution: (by Noam Elkies) Again, we reduce
to computing the average area of a triangle formed by
three random points A, B,C inside a unit circle
...

Given c, the expectation of [ABC] is equal to c2 times X,
the expected area of a triangle formed by two random
points P, Q in a circle and a fixed point R on the boundary
...

The distribution of a random point in that circle is
1
π r dr dθ over θ ∈ [0, π] and r ∈ [0, 2 sin θ ]
...

Performing the integrals over r and r0 first, we find
32 π π 3
sin θ sin3 θ 0 sin |θ − θ 0 | dθ 0 dθ
9π 2 0 0
Z Z
64 π θ 3
= 2
sin θ sin3 θ 0 sin(θ − θ 0 ) dθ 0 dθ
...

Remark: This is one of the oldest problems in geometric probability; it is an instance of Sylvester’s fourpoint problem, which nowadays is usually solved using a device known as Crofton’s formula
...
wolfram
...

B–1 The “curve” x3 + 3xy + y3 − 1 = 0 is actually reducible,
because the left side factors as
(x + y − 1)(x2 − xy + y2 + x + y + 1)
...
Thus the curve in question consists of the single point (−1, −1) together with
the line x + y = 1
...

The other two vertices lie on the line x + y = 1, so the
length of the altitude from (−1, −1) is the distance from

= (x + y + z)(x + ωy + ω 2 z)(x + ω 2 y + ωz),
where ω denotes a primitive cube root of unity
...

B–2 Let {x} = x − bxc denote the fractional part of x
...
, n, put si = x1 + · · · + xi (so that s0 = 0)
...
, {sn } into ascending order, and
call the result t0 ,
...
Since 0 = t0 ≤ · · · ≤ tn < 1,
the differences
t1 − t0 ,
...
Hence (as in the pigeonhole principle) one of these differences is no more
than 1/(n + 1); if it is anything other than 1 − tn , it
equals ±({si } − {s j }) for some 0 ≤ i < j ≤ n
...
, x j } and m = bsi c − bs j c; then






m + ∑ s = |m + s j − si |


s∈S
= |{s j } − {si }|
1
≤
,
n+1
as desired
...
, xn } and m = −dsn e, and again obtain the desired conclusion
...



First solution: We will prove that LS = n2 + 1 in any
configuration in which no two of the lines joining points
of S are parallel
...
For
convenience, we assume n ≥ 3, as the cases n = 1, 2 are
easy
...
e
...
Remove the directions corresponding

to lines through two points of S; this leaves
behind n2 intervals
...
Note that the resulting collection of partitions
depends only on the interval
...

The trivial partition that puts all of S on one side is in every such collection
...

For (a), note that if `1 , `2 are nonparallel lines achieving
the same partition, then we can rotate around their point
of intersection to achieve all of the intermediate directions on one side or the other
...

It follows now that that each linear partition, except for
the trivial one, occurs in exactly one place as the partition associated to some interval but not to its immediate
counterclockwise neighbor
...

Second solution: We prove the upper bound by induction on n
...
Put
S0 = S \ {P};
there are at

by the induction hypothesis,
0
...

Moreover, if two linear partitions of S restrict to the
same linear partition of S0 , then that partition of S0 is
achieved by a line through P
...
This yields
the desired result
...
This turns the rest of S into a set S0 of n − 1 lines
in the dual projective plane
...

Let ` be a line in the original plane, corresponding to a
point P in the dual plane
...
If we consider the dual affine plane
as being divided into regions by the lines of S0 , then the

lines of S0 crossing the segment O0 P are determined by
which region P lies in
...
By
induction on n, this number is easily seen to
be 1 + n2
...
We claim
that the nontrivial linear partitions of S are in natural bijection with pairs (`, {X,Y }) consisting of an S-line `
and a nontrivial linear partition {X,Y } of ` ∩ S
...

Let P be the line at infinity in the real projective plane
...
(It is proper because it has to omit
directions of S-lines that pass through both parts of the
partition and open because we can vary the separating
line
...
) Among
all S-lines that intersect both A and B choose a line `
whose direction is minimal (in the clockwise direction)
with respect to the interval I; also, pick an arbitrary line
`0 that induces {A, B}
...
(We can’t hit any
point of S during the rotation because of the minimality
property of `
...
To define the
above bijection we send {A, B} to (`, {A ∩ `, B ∩ `})
...
Pick any
point p ∈ ` that induces the partition {X,Y }
...
(It
is obtained from the partition of S − ` induced by ` by
adjoining X to one part and Y to the other
...

By construction these two maps are inverse to each
other, and this proves the claim
...
Radon’s
theorem states that if #S ≥ n + 2, then not every (A, B)
is a non-Radon partition
...
Richard
Stanley suggests the following references: T
...
Brylawski, A combinatorial perspective on the Radon convexity theorem, Geom
...
5 (1976), 459-466; and T
...

N
...
Acad
...
440 (1985), 69-87
...
We have
Z 1

achieved for instance by the sub-

Suppose that V is a k-plane in Rn
...
If V ∩ V0 and V ∩ V1 are each at most (k − 1)dimensional, then V ∩ V0 ∩ Z and V ∩ V1 ∩ Z each have
cardinality at most 2k−1 by the induction assumption,
and hence V ∩ Z has at most 2k elements
...

Second solution: Let S be a subset of Z contained in
a k-dimensional subspace of V
...
,tk+1 ∈ S satisfy a nontrivial linear
dependence c1t1 +· · ·+ck+1tk+1 = 0 with c1 ,
...
Since t1 ,
...
, ck+1 ∈ Q;
then by clearing denominators, we can find one with
c1 ,
...

Let F2 denote the field of two elements, and let S ⊆ Fn2
be the reductions modulo 2 of the points of S
...
,tk+1 ∈ S satisfy a nontrivial linear dependence,
because we can take the dependence from the end of
the previous paragraph and reduce modulo 2
...
Thus S has at most 2k
elements, as does S
...
The lift of that minor back to R would also not
vanish, so S would contain k + 1 linearly independent
elements
...
Form the matrix whose rows are
the elements of V ∩ Z; by construction, it has row rank
at most k
...
Since each coordinate of a point in Z can only
take two values, V ∩ Z can have at most 2k elements
...
artofproblemsolving
...
php?t=105991
...
)

Z 1

0

x f (x)2 dx

0

Z 1

=

{(x1 ,
...

First solution: More generally, we show that any affine
k-dimensional plane in Rn can contain at most 2k points
in Z
...


x2 f (x) dx −

(x3 /4 − x( f (x) − x/2)2 ) dx

0

≤

Z 1

x3 /4 dx = 1/16,

0

with equality when f (x) = x/2
...
We write O( f (n)) and Ω( f (n))
for functions g(n) such that f (n)/g(n) and g(n)/ f (n),
respectively, are bounded above
...
That means an
= Ω(n−1/k ), so
!
n

an = Ω

∑ i−1/k

= Ω(n(k−1)/k )
...

By Taylor’s theorem with remainder, for 1 < m < 2 and
x > 0,
|(1 + x)m − 1 − mx| ≤

m(m − 1) 2
x
...

−
 n+1 − an
k 
2k2

,

In particular,
(k+1)/k

lim an+1

n→∞

(k+1)/k

− an

=

k+1

...
Explicitly, for any ε > 0, we can
find N such that |xn − c| ≤ ε/2 for n ≥ N, and then






1 n  n − N ε N  N


+  ∑ (c − xi ) ;
c − ∑ xi  ≤


n i=1 
n 2 n i=1
for n large, the right side is smaller than ε
...


and this completes the proof
...
Write bn = an − Lnk/(k+1) , for a value of L to
be determined later
...

n→∞ bn
lim

−1/k

e1 = bn + an

Second solution: In this solution, rather than applying
Taylor’s theorem with remainder to (1 + x)m for 1 <
m < 2 and x > 0, we only apply convexity to deduce
that (1 + x)m ≥ 1 + mx
...

We first estimate e1
...


and so
(k+1)/k

an

≥

k+1
n+c
k

Hence
1
− L−(k+1)/k n−1 bn ≤ e1 − bn
k
1
−(k+1)/k
≤ − bn an

...
In particular,
(k+1)/k

lim inf

an

n→∞

≥

n

k+1
k

and so
lim inf
n→∞

an
nk/(k+1)


≥

k+1
k

k/(k+1)

...
Consequently, for n large,
|e1 | ≤ |bn |
...
By Taylor’s theorem with remainder applied to (1 + x)m for x > 0 and 0 < m < 1,

an+1 − an
−1/k

= an


k + 1 −1/(k+1) −1/(k+1)
(1 + o(1)),
≤
n
k
where o(1) denotes a function tending to 0 as n → ∞,
yields
an

k + 1 −1/(k+1) n −1/(k+1)
(1 + o(1))
∑i
k
i=1


k + 1 k + 1 −1/(k+1) k/(k+1)
=
n
(1 + o(1))
k
k


k + 1 k/(k+1) k/(k+1)
n
(1 + o(1)),
=
k

1 + mx ≥ (1 + x)m
≥ 1 + mx +

The “main term” of L((n + 1)k/(k+1) − nk/(k+1) )
k −1/(k+1)
is L k+1
n

...

2


L=

k+1
k

k/(k+1)

...
Hence
!
n

|bn | = O

∑ i−2

i=1

= O(1),

8
termining the asymptotic behavior of sequences of this
type: replace the given recursion

and so
ak+1
n
= Lk+1 =
n→∞ nk
lim



k+1
k

k

...

Remark: One can make a similar argument for any sequence given by an+1 = an + f (an ), when f is a decreasing function
...




---