The 74th William Lowell Putnam Mathematical Competition
Saturday, December 7, 2013
A1 Recall that a regular icosahedron is a convex polyhe- b
dron having 12 vertices and 20 faces; the faces are con- w(a, b)
-2 -1 0 1 2
gruent equilateral triangles. On each face of a regular
-2 -1 -2 2 -2 -1
icosahedron is written a nonnegative integer such that
the sum of all 20 integers is 39. Show that there are -1 -2 4 -4 4 -2
two faces that share a vertex and have the same integer a 0 2 -4 12 -4 2
written on them. 1 -2 4 -4 4 -2
A2 Let S be the set of all positive integers that are not 2 -1 -2 2 -2 -1
perfect squares. For n in S, consider choices of inte-
gers a1 , a2 , . . . , ar such that n < a1 < a2 < · · · < ar and For every finite subset S of Z × Z, define
n · a1 · a2 · · · ar is a perfect square, and let f (n) be the
minumum of ar over all such choices. For example, A(S) = ∑ w(s − s0 ).
(s,s0 )∈S×S
2 · 3 · 6 is a perfect square, while 2 · 3, 2 · 4, 2 · 5, 2 · 3 · 4,
2 · 3 · 5, 2 · 4 · 5, and 2 · 3 · 4 · 5 are not, and so f (2) = 6. Prove that if S is any finite nonempty subset of
Show that the function f from S to the integers is one- Z × Z, then A(S) > 0. (For example, if S =
to-one. {(0, 1), (0, 2), (2, 0), (3, 1)}, then the terms in A(S) are
A3 Suppose that the real numbers a0 , a1 , . . . , an and x, with 12, 12, 12, 12, 4, 4, 0, 0, 0, 0, −1, −1, −2, −2, −4, −4.)
0 < x < 1, satisfy B1 For positive integers n, let the numbers c(n) be de-
a0 a1 an termined by the rules c(1) = 1, c(2n) = c(n), and
+ +···+ = 0. c(2n + 1) = (−1)n c(n). Find the value of
1 − x 1 − x2 1 − xn+1
Prove that there exists a real number y with 0 < y < 1 2013
such that ∑ c(n)c(n + 2).
n=1
a0 + a1 y + · · · + an yn = 0.
B2 Let C = ∞
S
N=1 CN , where CN denotes the set of those
‘cosine polynomials’ of the form
A4 A finite collection of digits 0 and 1 is written around a
circle. An arc of length L ≥ 0 consists of L consecutive N
digits around the circle. For each arc w, let Z(w) and f (x) = 1 + ∑ an cos(2πnx)
N(w) denote the number of 0’s in w and the number of n=1
1’s in w, respectively. Assume that |Z(w) − Z(w0 )| ≤ 1
for any two arcs w, w0 of the same length. Suppose that for which:
some arcs w1 , . . . , wk have the property that (i) f (x) ≥ 0 for all real x, and
1 k
1 k (ii) an = 0 whenever n is a multiple of 3.
Z= ∑ Z(w j ) and N = k ∑ N(w j )
k j=1 j=1 Determine the maximum value of f (0) as f ranges
through C, and prove that this maximum is attained.
are both integers. Prove that there exists an arc w with
Z(w) = Z and N(w) = N. B3 Let P be a nonempty collection of subsets of {1, . . . , n}
such that:
A5 For m ≥ 3, a list of m3 real numbers ai jk (1 ≤ i << j <
k ≤ m) is said to be area definite for Rn if the inequality (i) if S, S0 ∈ P, then S ∪ S0 ∈ P and S ∩ S0 ∈ P, and
(ii) if S ∈ P and S 6= 0,
/ then there is a subset T ⊂ S
∑ ai jk · Area(∆Ai A j Ak ) ≥ 0 such that T ∈ P and T contains exactly one fewer
1≤i< j<k≤m
element than S.
holds for every choice of m points A1 , . . . , Am in Rn . For Suppose that f : P → R is a function such that f (0)
/ =0
example, the list of four numbers a123 = a124 = a134 = and
1, a234 = −1 is area definite for R2 . Prove that if a list
of m3 numbers is area definite for R2 , then it is area f (S ∪ S0 ) = f (S) + f (S0 ) − f (S ∩ S0 ) for all S, S0 ∈ P.
definite for R3 .
Must there exist real numbers f1 , . . . , fn such that
A6 Define a function w : Z × Z → Z as follows. For
|a| , |b| ≤ 2, let w(a, b) be as in the table shown; oth- f (S) = ∑ fi
erwise, let w(a, b) = 0. i∈S
for every S ∈ P?
, 2
B4 For any continuous real-valued function f defined on ing first. The playing area consists of n spaces, arranged
the interval [0, 1], let in a line. Initially all spaces are empty. At each turn, a
Z 1 Z 1 player either
µ( f ) = f (x) dx, Var( f ) = ( f (x) − µ( f ))2 dx, – places a stone in an empty space, or
0 0
M( f ) = max | f (x)| . – removes a stone from a nonempty space s, places
0≤x≤1 a stone in the nearest empty space to the left of
s (if such a space exists), and places a stone in
Show that if f and g are continuous real-valued func-
the nearest empty space to the right of s (if such a
tions defined on the interval [0, 1], then
space exists).
Var( f g) ≤ 2Var( f )M(g)2 + 2Var(g)M( f )2 . Furthermore, a move is permitted only if the resulting
position has not occurred previously in the game. A
B5 Let X = {1, 2, . . . , n}, and let k ∈ X. Show that there player loses if he or she is unable to move. Assuming
are exactly k · nn−1 functions f : X → X such that for that both players play optimally throughout the game,
every x ∈ X there is a j ≥ 0 such that f ( j) (x) ≤ k. [Here what moves may Alice make on her first turn?
f ( j) denotes the jth iterate of f , so that f (0) (x) = x and
f ( j+1) (x) = f ( f ( j) (x)).]
B6 Let n ≥ 1 be an odd integer. Alice and Bob play the fol-
lowing game, taking alternating turns, with Alice play-
Saturday, December 7, 2013
A1 Recall that a regular icosahedron is a convex polyhe- b
dron having 12 vertices and 20 faces; the faces are con- w(a, b)
-2 -1 0 1 2
gruent equilateral triangles. On each face of a regular
-2 -1 -2 2 -2 -1
icosahedron is written a nonnegative integer such that
the sum of all 20 integers is 39. Show that there are -1 -2 4 -4 4 -2
two faces that share a vertex and have the same integer a 0 2 -4 12 -4 2
written on them. 1 -2 4 -4 4 -2
A2 Let S be the set of all positive integers that are not 2 -1 -2 2 -2 -1
perfect squares. For n in S, consider choices of inte-
gers a1 , a2 , . . . , ar such that n < a1 < a2 < · · · < ar and For every finite subset S of Z × Z, define
n · a1 · a2 · · · ar is a perfect square, and let f (n) be the
minumum of ar over all such choices. For example, A(S) = ∑ w(s − s0 ).
(s,s0 )∈S×S
2 · 3 · 6 is a perfect square, while 2 · 3, 2 · 4, 2 · 5, 2 · 3 · 4,
2 · 3 · 5, 2 · 4 · 5, and 2 · 3 · 4 · 5 are not, and so f (2) = 6. Prove that if S is any finite nonempty subset of
Show that the function f from S to the integers is one- Z × Z, then A(S) > 0. (For example, if S =
to-one. {(0, 1), (0, 2), (2, 0), (3, 1)}, then the terms in A(S) are
A3 Suppose that the real numbers a0 , a1 , . . . , an and x, with 12, 12, 12, 12, 4, 4, 0, 0, 0, 0, −1, −1, −2, −2, −4, −4.)
0 < x < 1, satisfy B1 For positive integers n, let the numbers c(n) be de-
a0 a1 an termined by the rules c(1) = 1, c(2n) = c(n), and
+ +···+ = 0. c(2n + 1) = (−1)n c(n). Find the value of
1 − x 1 − x2 1 − xn+1
Prove that there exists a real number y with 0 < y < 1 2013
such that ∑ c(n)c(n + 2).
n=1
a0 + a1 y + · · · + an yn = 0.
B2 Let C = ∞
S
N=1 CN , where CN denotes the set of those
‘cosine polynomials’ of the form
A4 A finite collection of digits 0 and 1 is written around a
circle. An arc of length L ≥ 0 consists of L consecutive N
digits around the circle. For each arc w, let Z(w) and f (x) = 1 + ∑ an cos(2πnx)
N(w) denote the number of 0’s in w and the number of n=1
1’s in w, respectively. Assume that |Z(w) − Z(w0 )| ≤ 1
for any two arcs w, w0 of the same length. Suppose that for which:
some arcs w1 , . . . , wk have the property that (i) f (x) ≥ 0 for all real x, and
1 k
1 k (ii) an = 0 whenever n is a multiple of 3.
Z= ∑ Z(w j ) and N = k ∑ N(w j )
k j=1 j=1 Determine the maximum value of f (0) as f ranges
through C, and prove that this maximum is attained.
are both integers. Prove that there exists an arc w with
Z(w) = Z and N(w) = N. B3 Let P be a nonempty collection of subsets of {1, . . . , n}
such that:
A5 For m ≥ 3, a list of m3 real numbers ai jk (1 ≤ i << j <
k ≤ m) is said to be area definite for Rn if the inequality (i) if S, S0 ∈ P, then S ∪ S0 ∈ P and S ∩ S0 ∈ P, and
(ii) if S ∈ P and S 6= 0,
/ then there is a subset T ⊂ S
∑ ai jk · Area(∆Ai A j Ak ) ≥ 0 such that T ∈ P and T contains exactly one fewer
1≤i< j<k≤m
element than S.
holds for every choice of m points A1 , . . . , Am in Rn . For Suppose that f : P → R is a function such that f (0)
/ =0
example, the list of four numbers a123 = a124 = a134 = and
1, a234 = −1 is area definite for R2 . Prove that if a list
of m3 numbers is area definite for R2 , then it is area f (S ∪ S0 ) = f (S) + f (S0 ) − f (S ∩ S0 ) for all S, S0 ∈ P.
definite for R3 .
Must there exist real numbers f1 , . . . , fn such that
A6 Define a function w : Z × Z → Z as follows. For
|a| , |b| ≤ 2, let w(a, b) be as in the table shown; oth- f (S) = ∑ fi
erwise, let w(a, b) = 0. i∈S
for every S ∈ P?
, 2
B4 For any continuous real-valued function f defined on ing first. The playing area consists of n spaces, arranged
the interval [0, 1], let in a line. Initially all spaces are empty. At each turn, a
Z 1 Z 1 player either
µ( f ) = f (x) dx, Var( f ) = ( f (x) − µ( f ))2 dx, – places a stone in an empty space, or
0 0
M( f ) = max | f (x)| . – removes a stone from a nonempty space s, places
0≤x≤1 a stone in the nearest empty space to the left of
s (if such a space exists), and places a stone in
Show that if f and g are continuous real-valued func-
the nearest empty space to the right of s (if such a
tions defined on the interval [0, 1], then
space exists).
Var( f g) ≤ 2Var( f )M(g)2 + 2Var(g)M( f )2 . Furthermore, a move is permitted only if the resulting
position has not occurred previously in the game. A
B5 Let X = {1, 2, . . . , n}, and let k ∈ X. Show that there player loses if he or she is unable to move. Assuming
are exactly k · nn−1 functions f : X → X such that for that both players play optimally throughout the game,
every x ∈ X there is a j ≥ 0 such that f ( j) (x) ≤ k. [Here what moves may Alice make on her first turn?
f ( j) denotes the jth iterate of f , so that f (0) (x) = x and
f ( j+1) (x) = f ( f ( j) (x)).]
B6 Let n ≥ 1 be an odd integer. Alice and Bob play the fol-
lowing game, taking alternating turns, with Alice play-
