The 68th William Lowell Putnam Mathematical Competition
Saturday, December 1, 2007
A–1 Find all values of α for which the curves y = αx2 + f ( f (n) + 1) if and only if n = 1. [Editor’s note: one
1 1
αx+ 24 and x = αy2 +αy+ 24 are tangent to each other. must assume f is nonconstant.]
A–2 Find the least possible area of a convex set in the plane B–2 Suppose that f : [0, 1] → R has a continuous derivative
that intersects both branches of the hyperbola xy = 1 and that 01 f (x) dx = 0. Prove that for every α ∈ (0, 1),
R
and both branches of the hyperbola xy = −1. (A set S
in the plane is called convex if for any two points in S 1
Z α
the line segment connecting them is contained in S.) f (x) dx ≤ max | f 0 (x)|.
0 8 0≤x≤1
A–3 Let k be a positive integer. Suppose that the integers √
1, 2, 3, . . . , 3k + 1 are written down in random order. B–3 Let x0 = 1 and for n ≥ 0, let xn+1 = 3xn + bxn 5c. In
What is the probability that at no time during this pro- particular, x1 = 5, x2 = 26, x3 = 136, x4 = 712. Find a
cess, the sum of the integers that have been written up closed-form expression for x2007 . (bac means the largest
to that time is a positive integer divisible by 3? Your integer ≤ a.)
answer should be in closed form, but may include fac-
B–4 Let n be a positive integer. Find the number of pairs
torials.
P, Q of polynomials with real coefficients such that
A–4 A repunit is a positive integer whose digits in base 10
are all ones. Find all polynomials f with real coeffi- (P(X))2 + (Q(X))2 = X 2n + 1
cients such that if n is a repunit, then so is f (n).
and deg P > deg Q.
A–5 Suppose that a finite group has exactly n elements of B–5 Let k be a positive integer. Prove that there exist polyno-
order p, where p is a prime. Prove that either n = 0 or mials P0 (n), P1 (n), . . . , Pk−1 (n) (which may depend on
p divides n + 1. k) such that for any integer n,
A–6 A triangulation T of a polygon P is a finite collection j n kk jnk j n kk−1
= P0 (n) + P1 (n) + · · · + Pk−1 (n) .
of triangles whose union is P, and such that the inter- k k k
section of any two triangles is either empty, or a shared
vertex, or a shared side. Moreover, each side is a side (bac means the largest integer ≤ a.)
of exactly one triangle in T . Say that T is admissible
B–6 For each positive integer n, let f (n) be the number of
if every internal vertex is shared by 6 or more triangles.
ways to make n! cents using an unordered collection of
For example, [figure omitted.] Prove that there is an in-
coins, each worth k! cents for some k, 1 ≤ k ≤ n. Prove
teger Mn , depending only on n, such that any admissible
that for some constant C, independent of n,
triangulation of a polygon P with n sides has at most Mn
triangles. 2 /2−Cn 2 /4 2 /2+Cn 2 /4
nn e−n ≤ f (n) ≤ nn e−n .
B–1 Let f be a polynomial with positive integer coefficients.
Prove that if n is a positive integer, then f (n) divides
, Solutions to the 68th William Lowell Putnam Mathematical Competition
Saturday, December 1, 2007
Manjul Bhargava, Kiran Kedlaya, and Lenny Ng
√
A–1 The only such α are 2/3, 3/2, (13 ± 601)/12. Second solution: For any nonzero value of α, the two
First solution: Let C1 and C2 be the curves y = αx2 + conics will intersect in four points in the complex pro-
αx + 241 1
and x = αy2 + αy + 24 , respectively, and let L jective plane P2 (C). To determine the y-coordinates of
be the line y = x. We consider three cases. these intersection points, subtract the two equations to
obtain
If C1 is tangent to L, then the point of tangency (x, x)
satisfies (y − x) = α(x − y)(x + y) + α(x − y).
1
2αx + α = 1, x = αx2 + αx + ; Therefore, at a point of intersection we have either x =
24 y, or x = −1/α − (y + 1). Substituting these two pos-
by symmetry, C2 is tangent to L there, so C1 and C2 are sible linear conditions into the second equation shows
tangent. Writing α = 1/(2x + 1) in the first equation that the y-coordinate of a point of intersection is a root
and substituting into the second, we must have of either Q1 (y) = αy2 + (α − 1)y + 1/24 or Q2 (y) =
αy2 + (α + 1)y + 25/24 + 1/α.
x2 + x 1 If two curves are tangent, then the y-coordinates of at
x= + ,
2x + 1 24 least two of the intersection points will coincide; the
converse is also true because one of the curves is the
which simplifies to 0 = 24x2 − 2x − 1 = (6x + 1)(4x − graph of a function in x. The coincidence occurs pre-
1), or x ∈ {1/4, −1/6}. This yields α = 1/(2x + 1) ∈ cisely when either the discriminant of at least one of
{2/3, 3/2}. Q1 or Q2 is zero, or there is a common root of Q1
If C1 does not intersect L, then C1 and C2 are separated and Q2 . Computing the discriminants of Q1 and Q2
by L and so cannot be tangent. yields (up to constant factors) f1 (α) = 6α 2 − 13α + 6
and f2 (α) = 6α 2 − 13α − 18, respectively. If on the
If C1 intersects L in two distinct points P1 , P2 , then it
other hand Q1 and Q2 have a common root, it must be
is not tangent to L at either point. Suppose at one of
also a root of Q2 (y) − Q1 (y) = 2y + 1 + 1/α, yielding
these points, say P1 , the tangent to C1 is perpendicular
y = −(1 + α)/(2α) and 0 = Q1 (y) = − f2 (α)/(24α).
to L; then by symmetry, the same will be true of C2 , so
C1 and C2 will be tangent at P1 . In this case, the point Thus the values of α for which the two curves are tan-
P1 = (x, x) satisfies gent must be contained in the
√set of zeros of f1 and f2 ,
namely 2/3, 3/2, and (13 ± 601)/12.
1
2αx + α = −1, x = αx2 + αx + ; Remark: The fact that the two conics in P2 (C) meet in
24 four points, counted with multiplicities, is a special case
writing α = −1/(2x + 1) in the first equation and sub- of Bézout’s theorem: two curves in P2 (C) of degrees
stituting into the second, we have m, n and not sharing any common component meet in
exactly mn points when counted with multiplicity.
x2 + x 1 Many solvers were surprised that the proposers chose
x=− + ,
2x + 1 24 the parameter 1/24 to give two rational roots and two
√ nonrational roots. In fact, they had no choice in the
√± 601)/72. This yields α = −1/(2x +
or x = (−23 matter: attempting to make all four roots rational by
1) = (13 ± 601)/12. replacing 1/24 by β amounts to asking for β 2 + β and
If instead the tangents to C1 at P1 , P2 are not perpen- β 2 + β + 1 to be perfect squares. This cannot happen
dicular to L, then we claim there cannot be any point outside of trivial cases (β = 0, −1) ultimately because
where C1 and C2 are tangent. Indeed, if we count in- the elliptic curve 24A1 (in Cremona’s notation) over Q
tersections of C1 and C2 (by using C1 to substitute for y has rank 0. (Thanks to Noam Elkies for providing this
in C2 , then solving for y), we get at most four solutions computation.)
counting multiplicity. Two of these are P1 and P2 , and However, there are choices that make the radical milder,
any point of tangency counts for two more. However, e.g., β = 1/3 gives β 2 + β = 4/9 and β 2 + β + 1 =
off of L, any point of tangency would have a mirror im- 13/9, while β = 3/5 gives β 2 + β = 24/25 and β 2 +
age which is also a point of tangency, and there cannot β + 1 = 49/25.
be six solutions. Hence we have now found all possible
α. A–2 The minimum is 4, achieved by the square with vertices
(±1, ±1).
Saturday, December 1, 2007
A–1 Find all values of α for which the curves y = αx2 + f ( f (n) + 1) if and only if n = 1. [Editor’s note: one
1 1
αx+ 24 and x = αy2 +αy+ 24 are tangent to each other. must assume f is nonconstant.]
A–2 Find the least possible area of a convex set in the plane B–2 Suppose that f : [0, 1] → R has a continuous derivative
that intersects both branches of the hyperbola xy = 1 and that 01 f (x) dx = 0. Prove that for every α ∈ (0, 1),
R
and both branches of the hyperbola xy = −1. (A set S
in the plane is called convex if for any two points in S 1
Z α
the line segment connecting them is contained in S.) f (x) dx ≤ max | f 0 (x)|.
0 8 0≤x≤1
A–3 Let k be a positive integer. Suppose that the integers √
1, 2, 3, . . . , 3k + 1 are written down in random order. B–3 Let x0 = 1 and for n ≥ 0, let xn+1 = 3xn + bxn 5c. In
What is the probability that at no time during this pro- particular, x1 = 5, x2 = 26, x3 = 136, x4 = 712. Find a
cess, the sum of the integers that have been written up closed-form expression for x2007 . (bac means the largest
to that time is a positive integer divisible by 3? Your integer ≤ a.)
answer should be in closed form, but may include fac-
B–4 Let n be a positive integer. Find the number of pairs
torials.
P, Q of polynomials with real coefficients such that
A–4 A repunit is a positive integer whose digits in base 10
are all ones. Find all polynomials f with real coeffi- (P(X))2 + (Q(X))2 = X 2n + 1
cients such that if n is a repunit, then so is f (n).
and deg P > deg Q.
A–5 Suppose that a finite group has exactly n elements of B–5 Let k be a positive integer. Prove that there exist polyno-
order p, where p is a prime. Prove that either n = 0 or mials P0 (n), P1 (n), . . . , Pk−1 (n) (which may depend on
p divides n + 1. k) such that for any integer n,
A–6 A triangulation T of a polygon P is a finite collection j n kk jnk j n kk−1
= P0 (n) + P1 (n) + · · · + Pk−1 (n) .
of triangles whose union is P, and such that the inter- k k k
section of any two triangles is either empty, or a shared
vertex, or a shared side. Moreover, each side is a side (bac means the largest integer ≤ a.)
of exactly one triangle in T . Say that T is admissible
B–6 For each positive integer n, let f (n) be the number of
if every internal vertex is shared by 6 or more triangles.
ways to make n! cents using an unordered collection of
For example, [figure omitted.] Prove that there is an in-
coins, each worth k! cents for some k, 1 ≤ k ≤ n. Prove
teger Mn , depending only on n, such that any admissible
that for some constant C, independent of n,
triangulation of a polygon P with n sides has at most Mn
triangles. 2 /2−Cn 2 /4 2 /2+Cn 2 /4
nn e−n ≤ f (n) ≤ nn e−n .
B–1 Let f be a polynomial with positive integer coefficients.
Prove that if n is a positive integer, then f (n) divides
, Solutions to the 68th William Lowell Putnam Mathematical Competition
Saturday, December 1, 2007
Manjul Bhargava, Kiran Kedlaya, and Lenny Ng
√
A–1 The only such α are 2/3, 3/2, (13 ± 601)/12. Second solution: For any nonzero value of α, the two
First solution: Let C1 and C2 be the curves y = αx2 + conics will intersect in four points in the complex pro-
αx + 241 1
and x = αy2 + αy + 24 , respectively, and let L jective plane P2 (C). To determine the y-coordinates of
be the line y = x. We consider three cases. these intersection points, subtract the two equations to
obtain
If C1 is tangent to L, then the point of tangency (x, x)
satisfies (y − x) = α(x − y)(x + y) + α(x − y).
1
2αx + α = 1, x = αx2 + αx + ; Therefore, at a point of intersection we have either x =
24 y, or x = −1/α − (y + 1). Substituting these two pos-
by symmetry, C2 is tangent to L there, so C1 and C2 are sible linear conditions into the second equation shows
tangent. Writing α = 1/(2x + 1) in the first equation that the y-coordinate of a point of intersection is a root
and substituting into the second, we must have of either Q1 (y) = αy2 + (α − 1)y + 1/24 or Q2 (y) =
αy2 + (α + 1)y + 25/24 + 1/α.
x2 + x 1 If two curves are tangent, then the y-coordinates of at
x= + ,
2x + 1 24 least two of the intersection points will coincide; the
converse is also true because one of the curves is the
which simplifies to 0 = 24x2 − 2x − 1 = (6x + 1)(4x − graph of a function in x. The coincidence occurs pre-
1), or x ∈ {1/4, −1/6}. This yields α = 1/(2x + 1) ∈ cisely when either the discriminant of at least one of
{2/3, 3/2}. Q1 or Q2 is zero, or there is a common root of Q1
If C1 does not intersect L, then C1 and C2 are separated and Q2 . Computing the discriminants of Q1 and Q2
by L and so cannot be tangent. yields (up to constant factors) f1 (α) = 6α 2 − 13α + 6
and f2 (α) = 6α 2 − 13α − 18, respectively. If on the
If C1 intersects L in two distinct points P1 , P2 , then it
other hand Q1 and Q2 have a common root, it must be
is not tangent to L at either point. Suppose at one of
also a root of Q2 (y) − Q1 (y) = 2y + 1 + 1/α, yielding
these points, say P1 , the tangent to C1 is perpendicular
y = −(1 + α)/(2α) and 0 = Q1 (y) = − f2 (α)/(24α).
to L; then by symmetry, the same will be true of C2 , so
C1 and C2 will be tangent at P1 . In this case, the point Thus the values of α for which the two curves are tan-
P1 = (x, x) satisfies gent must be contained in the
√set of zeros of f1 and f2 ,
namely 2/3, 3/2, and (13 ± 601)/12.
1
2αx + α = −1, x = αx2 + αx + ; Remark: The fact that the two conics in P2 (C) meet in
24 four points, counted with multiplicities, is a special case
writing α = −1/(2x + 1) in the first equation and sub- of Bézout’s theorem: two curves in P2 (C) of degrees
stituting into the second, we have m, n and not sharing any common component meet in
exactly mn points when counted with multiplicity.
x2 + x 1 Many solvers were surprised that the proposers chose
x=− + ,
2x + 1 24 the parameter 1/24 to give two rational roots and two
√ nonrational roots. In fact, they had no choice in the
√± 601)/72. This yields α = −1/(2x +
or x = (−23 matter: attempting to make all four roots rational by
1) = (13 ± 601)/12. replacing 1/24 by β amounts to asking for β 2 + β and
If instead the tangents to C1 at P1 , P2 are not perpen- β 2 + β + 1 to be perfect squares. This cannot happen
dicular to L, then we claim there cannot be any point outside of trivial cases (β = 0, −1) ultimately because
where C1 and C2 are tangent. Indeed, if we count in- the elliptic curve 24A1 (in Cremona’s notation) over Q
tersections of C1 and C2 (by using C1 to substitute for y has rank 0. (Thanks to Noam Elkies for providing this
in C2 , then solving for y), we get at most four solutions computation.)
counting multiplicity. Two of these are P1 and P2 , and However, there are choices that make the radical milder,
any point of tangency counts for two more. However, e.g., β = 1/3 gives β 2 + β = 4/9 and β 2 + β + 1 =
off of L, any point of tangency would have a mirror im- 13/9, while β = 3/5 gives β 2 + β = 24/25 and β 2 +
age which is also a point of tangency, and there cannot β + 1 = 49/25.
be six solutions. Hence we have now found all possible
α. A–2 The minimum is 4, achieved by the square with vertices
(±1, ±1).
