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 B–1 Show that the curve x3 + 3xy + y3 = 1 contains only one
set of three distinct points, A, B, and C, which are ver-
(x2 + y2 + z2 + 8)2 ≤ 36(x2 + y2 ). tices of an equilateral triangle, and find its area.
B–2 Prove that, for every set X = {x1 , x2 , . . . , xn } of n real
A–2 Alice and Bob play a game in which they take turns
numbers, there exists a non-empty subset S of X and an
removing stones from a heap that initially has n stones.
integer m such that
The number of stones removed at each turn must be one
less than a prime number. The winner is the player who
takes the last stone. Alice plays first. Prove that there 1
m+ ∑s ≤ .
are infinitely many n such that Bob has a winning strat- s∈S n + 1
egy. (For example, if n = 17, then Alice might take 6 B–3 Let S be a finite set of points in the plane. A linear parti-
leaving 11; then Bob might take 1 leaving 10; then Al- tion of S is an unordered pair {A, B} of subsets of S such
ice can take the remaining stones to win.) 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
A–3 Let 1, 2, 3, . . . , 2005, 2006, 2007, 2009, 2012, 2016, . . . be empty). Let LS be the number of linear partitions of
be a sequence defined by xk = k for k = 1, 2, . . . , 2006 S. For each positive integer n, find the maximum of LS
and xk+1 = xk + xk−2005 for k ≥ 2006. Show that the over all sets S of n points.
sequence has 2005 consecutive terms each divisible by
2006. B–4 Let Z denote the set of points in Rn whose coordinates
are 0 or 1. (Thus Z has 2n elements, which are the ver-
A–4 Let S = {1, 2, . . . , n} for some integer n > 1. Say a per- tices of a unit hypercube in Rn .) Given a vector sub-
mutation π of S has a local maximum at k ∈ S if space V of Rn , let Z(V ) denote the number of members
of Z that lie in V . Let k be given, 0 ≤ k ≤ n. Find the
(i) π(k) > π(k + 1) for k = 1;
maximum, over all vector subspaces V ⊆ Rn of dimen-
(ii) π(k − 1) < π(k) and π(k) > π(k + 1) for 1 < k < sion k, of the number of points in V ∩ Z. [Editorial note:
n; the proposers probably intended to write Z(V ) instead
(iii) π(k − 1) < π(k) for k = n. of “the number of points in V ∩ Z”, but this changes
nothing.]
(For example, if n = 5 and π takes values at 1, 2, 3, 4, 5
of 2, 1, 4, 5, 3, then π has a local maximum of 2 at k = B–5 For each continuous function f : [0, 1] → R, let I( f ) =
R1 2 R1 2
1, and a local maximum of 5 at k = 4.) What is the 0 x f (x) dx and J(x) = 0 x ( f (x)) dx. Find the maxi-
average number of local maxima of a permutation of S, mum value of I( f ) − J( f ) over all such functions f .
averaging over all permutations of S?
B–6 Let k be an integer greater than 1. Suppose a0 > 0, and
A–5 Let n be a positive odd integer and let θ be a real num- define
ber such that θ /π is irrational. Set ak = tan(θ + kπ/n),
1
k = 1, 2, . . . , n. Prove that an+1 = an + √
k a
n
a1 + a2 + · · · + an
a1 a2 · · · an for n > 0. Evaluate
is an integer, and determine its value. ak+1
n
lim .
n→∞ nk
A–6 Four points are chosen uniformly and independently at
random in the interior of a given circle. Find the proba-
bility that they are the vertices of a convex quadrilateral.
, Solutions to the 67th William Lowell Putnam Mathematical Competition
Saturday, December 2, 2006
Kiran Kedlaya and Lenny Ng
p change to cylindrical coordinates, i.e., we put r =
A–1 We where n is fixed and f is a fixed polynomial of n vari-
x2 + y2 . Then the given inequality is equivalent to ables with integer coefficients, for any positive integer
N, the sequence modulo N is eventually periodic. This
r2 + z2 + 8 ≤ 6r, is simply because there are only finitely many possible
sequences of n consecutive values modulo N, and once
or such a sequence is repeated, every subsequent value is
repeated as well.
(r − 3)2 + z2 ≤ 1.
We next observe that if one can rewrite the same recur-
This defines a solid of revolution (a solid torus); the sion as
area being rotated is the disc (x − 3)2 + z2 ≤ 1 in the
xk−n = g(xk−n+1 , . . . , xk ) (k > n),
xz-plane. By Pappus’s theorem, the volume of this
equals the area of this disc, which is π, times the dis- where g is also a polynomial with integer coefficients,
tance through which the center of mass is being rotated, then the sequence extends uniquely to a doubly infi-
which is (2π)3. That is, the total volume is 6π 2 . nite sequence . . . , x−1 , x0 , x1 , . . . which is fully periodic
A–2 Suppose on the contrary that the set B of values of modulo any N. That is the case in the situation at hand,
n for which Bob has a winning strategy is finite; for because we can rewrite the given recursion as
convenience, we include n = 0 in B, and write B =
xk−2005 = xk+1 − xk .
{b1 , . . . , bm }. Then for every nonnegative integer n not
in B, Alice must have some move on a heap of n stones It thus suffices to find 2005 consecutive terms divisible
leading to a position in which the second player wins. by N in the doubly infinite sequence, for any fixed N
That is, every nonnegative integer not in B can be writ- (so in particular for N = 2006). Running the recursion
ten as b+ p−1 for some b ∈ B and some prime p. How- backwards, we easily find
ever, there are numerous ways to show that this cannot
happen. x1 = x0 = · · · = x−2004 = 1
First solution: Let t be any integer bigger than all of x−2005 = · · · = x−4009 = 0,
the b ∈ B. Then it is easy to write down t consecutive
composite integers, e.g., (t +1)!+2, . . . , (t +1)!+t +1. yielding the desired result.
Take n = (t + 1)! + t; then for each b ∈ B, n − b + 1 is
one of the composite integers we just wrote down. A–4 First solution: By the linearity of expectation, the av-
erage number of local maxima is equal to the sum of
Second solution: Let p1 , . . . , p2m be any prime num- the probability of having a local maximum at k over
bers; then by the Chinese remainder theorem, there ex- k = 1, . . . , n. For k = 1, this probability is 1/2: given
ists a positive integer x such that the pair {π(1), π(2)}, it is equally likely that π(1) or
π(2) is bigger. Similarly, for k = n, the probability is
x − b1 ≡ −1 (mod p1 pm+1 )
1/2. For 1 < k < n, the probability is 1/3: given the pair
... {π(k − 1), π(k), π(k + 1)}, it is equally likely that any
x − bn ≡ −1 (mod pm p2m ). of the three is the largest. Thus the average number of
local maxima is
For each b ∈ B, the unique integer p such that x = b +
p − 1 is divisible by at least two primes, and so cannot 1 1 n+1
2· + (n − 2) · = .
itself be prime. 2 3 3
Third solution: (by Catalin Zara) Put b1 = 0, and take
Second solution: Another way to apply the linear-
n = (b2 − 1) · · · (bm − 1); then n is composite because
ity of expectation is to compute the probability that
3, 8 ∈ B, and for any nonzero b ∈ B, n − bi + 1 is di-
i ∈ {1, . . . , n} occurs as a local maximum. The most
visible by but not equal to bi − 1. (One could also take
efficient way to do this is to imagine the permutation as
n = b2 · · · bm − 1, so that n − bi + 1 is divisible by bi .)
consisting of the symbols 1, . . . , n, ∗ written in a circle
A–3 We first observe that given any sequence of integers in some order. The number i occurs as a local maxi-
x1 , x2 , . . . satisfying a recursion mum if the two symbols it is adjacent to both belong to
the set {∗, 1, . . . , i − 1}. There are i(i − 1) pairs of such
xk = f (xk−1 , . . . , xk−n ) (k > n), symbols and n(n − 1) pairs in total, so the probability of
Saturday, December 2, 2006
A–1 Find the volume of the region of points (x, y, z) such that B–1 Show that the curve x3 + 3xy + y3 = 1 contains only one
set of three distinct points, A, B, and C, which are ver-
(x2 + y2 + z2 + 8)2 ≤ 36(x2 + y2 ). tices of an equilateral triangle, and find its area.
B–2 Prove that, for every set X = {x1 , x2 , . . . , xn } of n real
A–2 Alice and Bob play a game in which they take turns
numbers, there exists a non-empty subset S of X and an
removing stones from a heap that initially has n stones.
integer m such that
The number of stones removed at each turn must be one
less than a prime number. The winner is the player who
takes the last stone. Alice plays first. Prove that there 1
m+ ∑s ≤ .
are infinitely many n such that Bob has a winning strat- s∈S n + 1
egy. (For example, if n = 17, then Alice might take 6 B–3 Let S be a finite set of points in the plane. A linear parti-
leaving 11; then Bob might take 1 leaving 10; then Al- tion of S is an unordered pair {A, B} of subsets of S such
ice can take the remaining stones to win.) 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
A–3 Let 1, 2, 3, . . . , 2005, 2006, 2007, 2009, 2012, 2016, . . . be empty). Let LS be the number of linear partitions of
be a sequence defined by xk = k for k = 1, 2, . . . , 2006 S. For each positive integer n, find the maximum of LS
and xk+1 = xk + xk−2005 for k ≥ 2006. Show that the over all sets S of n points.
sequence has 2005 consecutive terms each divisible by
2006. B–4 Let Z denote the set of points in Rn whose coordinates
are 0 or 1. (Thus Z has 2n elements, which are the ver-
A–4 Let S = {1, 2, . . . , n} for some integer n > 1. Say a per- tices of a unit hypercube in Rn .) Given a vector sub-
mutation π of S has a local maximum at k ∈ S if space V of Rn , let Z(V ) denote the number of members
of Z that lie in V . Let k be given, 0 ≤ k ≤ n. Find the
(i) π(k) > π(k + 1) for k = 1;
maximum, over all vector subspaces V ⊆ Rn of dimen-
(ii) π(k − 1) < π(k) and π(k) > π(k + 1) for 1 < k < sion k, of the number of points in V ∩ Z. [Editorial note:
n; the proposers probably intended to write Z(V ) instead
(iii) π(k − 1) < π(k) for k = n. of “the number of points in V ∩ Z”, but this changes
nothing.]
(For example, if n = 5 and π takes values at 1, 2, 3, 4, 5
of 2, 1, 4, 5, 3, then π has a local maximum of 2 at k = B–5 For each continuous function f : [0, 1] → R, let I( f ) =
R1 2 R1 2
1, and a local maximum of 5 at k = 4.) What is the 0 x f (x) dx and J(x) = 0 x ( f (x)) dx. Find the maxi-
average number of local maxima of a permutation of S, mum value of I( f ) − J( f ) over all such functions f .
averaging over all permutations of S?
B–6 Let k be an integer greater than 1. Suppose a0 > 0, and
A–5 Let n be a positive odd integer and let θ be a real num- define
ber such that θ /π is irrational. Set ak = tan(θ + kπ/n),
1
k = 1, 2, . . . , n. Prove that an+1 = an + √
k a
n
a1 + a2 + · · · + an
a1 a2 · · · an for n > 0. Evaluate
is an integer, and determine its value. ak+1
n
lim .
n→∞ nk
A–6 Four points are chosen uniformly and independently at
random in the interior of a given circle. Find the proba-
bility that they are the vertices of a convex quadrilateral.
, Solutions to the 67th William Lowell Putnam Mathematical Competition
Saturday, December 2, 2006
Kiran Kedlaya and Lenny Ng
p change to cylindrical coordinates, i.e., we put r =
A–1 We where n is fixed and f is a fixed polynomial of n vari-
x2 + y2 . Then the given inequality is equivalent to ables with integer coefficients, for any positive integer
N, the sequence modulo N is eventually periodic. This
r2 + z2 + 8 ≤ 6r, is simply because there are only finitely many possible
sequences of n consecutive values modulo N, and once
or such a sequence is repeated, every subsequent value is
repeated as well.
(r − 3)2 + z2 ≤ 1.
We next observe that if one can rewrite the same recur-
This defines a solid of revolution (a solid torus); the sion as
area being rotated is the disc (x − 3)2 + z2 ≤ 1 in the
xk−n = g(xk−n+1 , . . . , xk ) (k > n),
xz-plane. By Pappus’s theorem, the volume of this
equals the area of this disc, which is π, times the dis- where g is also a polynomial with integer coefficients,
tance through which the center of mass is being rotated, then the sequence extends uniquely to a doubly infi-
which is (2π)3. That is, the total volume is 6π 2 . nite sequence . . . , x−1 , x0 , x1 , . . . which is fully periodic
A–2 Suppose on the contrary that the set B of values of modulo any N. That is the case in the situation at hand,
n for which Bob has a winning strategy is finite; for because we can rewrite the given recursion as
convenience, we include n = 0 in B, and write B =
xk−2005 = xk+1 − xk .
{b1 , . . . , bm }. Then for every nonnegative integer n not
in B, Alice must have some move on a heap of n stones It thus suffices to find 2005 consecutive terms divisible
leading to a position in which the second player wins. by N in the doubly infinite sequence, for any fixed N
That is, every nonnegative integer not in B can be writ- (so in particular for N = 2006). Running the recursion
ten as b+ p−1 for some b ∈ B and some prime p. How- backwards, we easily find
ever, there are numerous ways to show that this cannot
happen. x1 = x0 = · · · = x−2004 = 1
First solution: Let t be any integer bigger than all of x−2005 = · · · = x−4009 = 0,
the b ∈ B. Then it is easy to write down t consecutive
composite integers, e.g., (t +1)!+2, . . . , (t +1)!+t +1. yielding the desired result.
Take n = (t + 1)! + t; then for each b ∈ B, n − b + 1 is
one of the composite integers we just wrote down. A–4 First solution: By the linearity of expectation, the av-
erage number of local maxima is equal to the sum of
Second solution: Let p1 , . . . , p2m be any prime num- the probability of having a local maximum at k over
bers; then by the Chinese remainder theorem, there ex- k = 1, . . . , n. For k = 1, this probability is 1/2: given
ists a positive integer x such that the pair {π(1), π(2)}, it is equally likely that π(1) or
π(2) is bigger. Similarly, for k = n, the probability is
x − b1 ≡ −1 (mod p1 pm+1 )
1/2. For 1 < k < n, the probability is 1/3: given the pair
... {π(k − 1), π(k), π(k + 1)}, it is equally likely that any
x − bn ≡ −1 (mod pm p2m ). of the three is the largest. Thus the average number of
local maxima is
For each b ∈ B, the unique integer p such that x = b +
p − 1 is divisible by at least two primes, and so cannot 1 1 n+1
2· + (n − 2) · = .
itself be prime. 2 3 3
Third solution: (by Catalin Zara) Put b1 = 0, and take
Second solution: Another way to apply the linear-
n = (b2 − 1) · · · (bm − 1); then n is composite because
ity of expectation is to compute the probability that
3, 8 ∈ B, and for any nonzero b ∈ B, n − bi + 1 is di-
i ∈ {1, . . . , n} occurs as a local maximum. The most
visible by but not equal to bi − 1. (One could also take
efficient way to do this is to imagine the permutation as
n = b2 · · · bm − 1, so that n − bi + 1 is divisible by bi .)
consisting of the symbols 1, . . . , n, ∗ written in a circle
A–3 We first observe that given any sequence of integers in some order. The number i occurs as a local maxi-
x1 , x2 , . . . satisfying a recursion mum if the two symbols it is adjacent to both belong to
the set {∗, 1, . . . , i − 1}. There are i(i − 1) pairs of such
xk = f (xk−1 , . . . , xk−n ) (k > n), symbols and n(n − 1) pairs in total, so the probability of
