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 68th William Lowell Putnam Mathematical Competition
Saturday, December 1, 2007
A–1 Find all values of α for which the curves y = αx2 +
1
1
αx+ 24
and x = αy2 +αy+ 24
are tangent to each other
...
[Editor’s note: one
must assume f is nonconstant
...
(A set S
in the plane is called convex if for any two points in S
the line segment connecting them is contained in S
...
Prove that for every α ∈ (0, 1),

Z α
 1



max | f 0 (x)|
...
Suppose that the integers
1, 2, 3,
...

What is the probability that at no time during this process, the sum of the integers that have been written up
to that time is a positive integer divisible by 3? Your
answer should be in closed form, but may include factorials
...
In
particular, x1 = 5, x2 = 26, x3 = 136, x4 = 712
...
(bac means the largest
integer ≤ a
...
Find all polynomials f with real coefficients such that if n is a repunit, then so is f (n)
...
Prove that either n = 0 or
p divides n + 1
...
Moreover, each side is a side
of exactly one triangle in T
...

For example, [figure omitted
...

B–1 Let f be a polynomial with positive integer coefficients
...
Find the number of pairs
P, Q of polynomials with real coefficients such that
(P(X))2 + (Q(X))2 = X 2n + 1
and deg P > deg Q
...
Prove that there exist polynomials P0 (n), P1 (n),
...


(bac means the largest integer ≤ a
...
Prove
that for some constant C, independent of n,
2 /2−Cn

nn

2 /4

e−n

2 /2+Cn

≤ f (n) ≤ nn

2 /4

e−n


...

αx2 +

First solution: Let C1 and C2 be the curves y =
1
1
αx + 24
and x = αy2 + αy + 24
, respectively, and let L
be the line y = x
...


If C1 is tangent to L, then the point of tangency (x, x)
satisfies
x = αx2 + αx +

2αx + α = 1,

1
;
24

by symmetry, C2 is tangent to L there, so C1 and C2 are
tangent
...
This yields α = 1/(2x + 1) ∈
{2/3, 3/2}
...

If C1 intersects L in two distinct points P1 , P2 , then it
is not tangent to L at either point
...
In this case, the point
P1 = (x, x) satisfies
2αx + α = −1,

x = αx2 + αx +

1
;
24

writing α = −1/(2x + 1) in the first equation and substituting into the second, we have
x=−

x2 + x
1
+ ,
2x + 1 24

√
or x = (−23
ñ 601)/72
...

If instead the tangents to C1 at P1 , P2 are not perpendicular to L, then we claim there cannot be any point
where C1 and C2 are tangent
...
Two of these are P1 and P2 , and
any point of tangency counts for two more
...
Hence we have now found all possible
α
...
To determine the y-coordinates of
these intersection points, subtract the two equations to
obtain
(y − x) = α(x − y)(x + y) + α(x − y)
...
Substituting these two possible linear conditions into the second equation shows
that the y-coordinate of a point of intersection is a root
of either Q1 (y) = αy2 + (α − 1)y + 1/24 or Q2 (y) =
αy2 + (α + 1)y + 25/24 + 1/α
...
The coincidence occurs precisely when either the discriminant of at least one of
Q1 or Q2 is zero, or there is a common root of Q1
and Q2
...
If on the
other hand Q1 and Q2 have a common root, it must be
also a root of Q2 (y) − Q1 (y) = 2y + 1 + 1/α, yielding
y = −(1 + α)/(2α) and 0 = Q1 (y) = − f2 (α)/(24α)
...

Remark: The fact that the two conics in P2 (C) meet in
four points, counted with multiplicities, is a special case
of B´ezout’s theorem: two curves in P2 (C) of degrees
m, n and not sharing any common component meet in
exactly mn points when counted with multiplicity
...
In fact, they had no choice in the
matter: attempting to make all four roots rational by
replacing 1/24 by β amounts to asking for β 2 + β and
β 2 + β + 1 to be perfect squares
...
(Thanks to Noam Elkies for providing this
computation
...
g
...

A–2 The minimum is 4, achieved by the square with vertices
(±1, ±1)
...
Choose A, B,C, D ∈ S
lying on the branches of the two hyperbolas, with A in
the upper right quadrant, B in the upper left, C in the
lower left, D in the lower right
...

Write A = (a, 1/a), B = (−b, 1/b), C = (−c, −1/c),
D = (d, −1/d) with a, b, c, d > 0
...

Second solution: Choose A, B,C, D as in the first solution
...
For m small,
the counterclockwise angle from the line AC to the line
BD approaches 0; for m large, this angle approaches
π
...
The area of
ABCD is then AC · BD
...
This holds because if we draw the tangent lines to
the hyperbola xy = 1 at the points (1, 1) and (−1, −1),
then A and C lie outside the region between these lines
...

Third solution: (by Richard Stanley) Choose A, B,C, D
as in the first solution
...
This does not increase the area
of the quadrilateral ABCD (even if this quadrilateral is
not convex)
...
If we thus repeat the
procedure, fixing B and D and moving A and C to the
points where the tangents are parallel to BD, then A and
C must move to (x, 1/x) and (−x, −1/x), respectively,
forming a rectangle of area 4
...
An
example suggested by David Savitt (due to Chris
Brewer): note that AD and BC cross the positive and
negative x-axes, respectively, so the convex hull of
ABCD contains O
...

A–3 Assume that we have an ordering of 1, 2,
...
If we omit
the multiples of 3 from this ordering, then the remaining sequence mod 3 must look like 1, 1, −1, 1, −1,
...
Since there is one more integer
in the ordering congruent to 1 mod 3 than to −1, the
sequence mod 3 must look like 1, 1, −1, 1, −1,
...
The two conditions are independent,
and the probability of the first is (2k +1)/(3k
+1) while
2k+1

the probability of the second is 1/ k , since there


are 2k+1
ways to order (k + 1) 1’s and k −1’s
...

A–4 Note that n is a repunit if and only if 9n + 1 = 10m for
some power of 10 greater than 1
...
We will show that the only such functions g are those
of the form g(n) = 10c nd for d ≥ 0, c ≥ 1 − d (all of
which clearly work), which will mean that the desired
polynomials f are those of the form
1
f (n) = (10c (9n + 1)d − 1)
9
for the same c, d
...
With this convention, it suffices to check that the polynomials g taking powers of
10 greater than 1 to powers of 10 are of the form 10c nd
for any integers c, d with d ≥ 0
...
As x → ∞, we have
g(x)/xd → a; however, for x a power of 10 greater than
1, g(x)/xd is a power of 10
...
The polynomial g(x) − 10c xd has
infinitely many roots, so must be identically zero
...
If d = 0, we have g(n) = 10c for some c
...
Moreover, g takes each value only finitely many times, so the
sequence g(100 ), g(101 ),
...
Suppose that t 6= 0; then we can choose
a positive integer h such that the numerator of t is not
divisible by 10h
...

Consequently, t = 0, and we may apply the induction
hypothesis to g(n)/n to deduce the claim
...
By
contrast, the first solution uses the “∞-adic” topology,
i
...
, the usual real topology
...

First solution: By Lagrange’s theorem, if m is not divisible by p, then n = 0
...
, a p−1 ) ∈ G p such that a0 · · · a p−1 = e;
then S has cardinality m p−1 , which is divisible by p
...
, a p−1 ) ∈ S, then (a1 ,
...
The fixed points under this operation are the tuples
(a,
...
Consequently, the number of a ∈ G with a p = e
is divisible by p; since that number is n + 1 (only e has
order 1), this proves the claim
...
Let S
be the set of all elements of G \ H of order dividing p,
and let H act on G by conjugation
...
For each such g, g and H
generate an elementary abelian subgroup of G of order
p2
...
Hence the cardinality of S is divisible by p;
adding the p − 1 nontrivial elements of H gives n ≡ −1
(mod p) as desired
...
If |H| = 1, then we are
done
...
Let T ⊂ S denote the set of
fixed points of this action
...
On the
other hand, H ⊂ T , and if T contained an element not
in H, then that would contradict the maximality of H
...
e
...

Remark: This result is a theorem of Cauchy; the first
solution above is due to McKay
...

A–6 For an admissible triangulation T , number the vertices
of P consecutively v1 ,
...

We first claim that a1 + · · · + an ≤ 4n − 6
...

By Euler’s Formula, (F + 1) − E +V = 2 (one must add
1 to the face count for the region exterior to P)
...
On the
other hand, each edge has two endpoints, and each of
the V − n internal vertices is an endpoint of at least 6
edges; hence a1 + · · · + an + 6(V − n) ≤ 2E
...

Now set A3 = 1 and An = An−1 + 2n − 3 for n ≥ 4; we
will prove by induction on n that T has at most An triangles
...

Next assume that an admissible triangulation of an
(n − 1)-gon has at most An−1 triangles, and let T be
an admissible triangulation of an n-gon
...
Otherwise, all ai ≥ 3
...
, an is less than 4, and thus there
are more ai = 3 than ai ≥ 5
...
, 4, 3 in order, for some k with 2 ≤ k ≤ n − 1
(possibly k = 2, in which case there are no degree 4
vertices separating the degree 3 vertices)
...
It follows that there are at
most An−1 + 2k − 1 ≤ An−1 + 2n − 3 = An triangles in
T
...

Remark: We can refine the bound An somewhat
...
Thus there exist six
sequences with degrees 3, 4,
...
We may thus choose a sequence of length
k ≤ b 6n c + 1, so we may improve the upper bound to
An = An−1 + 2b 6n c + 1, or asymptotically 61 n2
...

B–1 The problem fails if f is allowed to be constant, e
...
,
take f (n) = 1
...

Write f (n) = ∑di=0 ai ni with ai > 0
...

If n = 1, then this implies that f ( f (n) + 1) is divisible
by f (n)
...


4
B–2 Put B = max0≤x≤1 | f 0 (x)| and g(x) = 0x f (y) dy
...
We may thus take α = y hereafter
...
By then substituting
− f (x) for f (x) if
R
needed, we may assume that 0α f (x) dx ≥ 0
...
Therein, the sequence is described as
the case S(1, 5) of the sequence S(a0 , a1 ) in which an+2
is the least integer for which an+2 /an+1 > an+1 /an
...
W
...

Press, New York, 1993, p
...

B–4 The number of pairs is 2n+1
...

Factor both sides:
(P(X) + Q(X)i)(P(X) − Q(X)i)

α2
1
=
B≤ B
2
8

n−1

= ∏ (X − exp(2πi(2 j + 1)/(4n)))
j=0

as desired
...
Thus we claim
that xn =
√
n−1
2√
2n+3 − α −(2n+3) ), where α = 1+ 5 , to make the
(α
2
5
answer x2007 =

2006
2√
(α 3997 − α −3997 )
...
Indeed,
√
3+ 5
2
since α = 2 , we have
√
2n−1
xn+1 − (3 + 5)xn = √ (2(α 2n+5 − α −(2n+5) )
5
√
− (3 + 5)(α 2n+3 − α −(2n+3) ))
= 2n α −(2n+3)
...


Second solution:√(by Catalin
√ Zara) Since xn is rational,
we have 0 < xn 5 − bxn 5c < 1
...

√
√
Since 0 < 3 − 5 < 1, this yields bxn+1 5c = 3xn+1 −
4xn , so we can rewrite the recursion as xn+1 = 6xn −
4xn−1 for n ≥ 2
...

Remark:
With an initial 1 prepended, this
becomes sequence A018903 in Sloane’s OnLine
Encyclopedia
of
Integer
Sequences:
(http://www
...
att
...

j=0

Then each choice of P, Q corresponds to equating
P(X) + Q(X)i with the product of some n factors on
the right, in which we choose exactly of the two factors for each j = 0,
...
(We must take exactly n
factors because as a polynomial in X with complex coefficients, P(X) + Q(X)i has degree exactly n
...
) Thus there are 2n such pairs; multiplying by 2 to allow P to have leading coefficient −1
yields the desired result
...

 
B–5 For n an integer, we have nk = n−k j for j the unique
integer in {0,
...


By expanding this out, we obtain the desired polynomials P0 (n),
...

Remark: Variants of this solution are possible that construct the Pi less explicitly, using Lagrange interpolation
or Vandermonde determinants
...
Throughout this proof, any Ci
will be a positive constant whose exact value is immaterial
...
This gives
2 /2−C n
1

nn

2 /4

e−n

≤ 11+c 22+c · · · nn+c
2 /2+C n
2

≤ nn

2 /4

e−n


...
, an ) of nonnegative integers such that

For a lower bound on f (n), we note that if 0 ≤ ai <
(n − 1)!/i! for i = 2,
...

Hence
f (n) ≥

(n − 1)!
(n − 1)!
···
2!
(n − 1)!

= 31 42 · · · (n − 1)n−3

a1 1! + · · · + an n! = n!
...
Hence
n!
n!
···
1!
n!
= 2n 21 32 · · · nn−1

f (n) ≤ 2n

2 /2+C n
3

≤ nn

2 /4

e−n


...




---