Putnam 2000

P∞
A1. Let A be a positive real number. WhatPare the possible values of j=0 x2j , given that
x0 , x1 , x2 ,. . . are positive numbers for which ∞
j=0 xj = A?

Solution. Since 0 < xj < A,

∞
X ∞
X
x2j < Axj = A2 .
j=0 j=0
P
Thus, the possible values of ∞ 2 2 2
j=0 xj belong to (0, A ). We show that each point in (0, A ) is
a possible value using the following argument due to Ken Rogers. Let xi = ay i for y ∈ (0, 1)
and a constant a > 0. Then
∞
X a X ∞
xj = A ⇔ = ay j = A ⇔ a = A (1 − y) .
j=0
1−y j=0

We have ∞
X ∞
X ¡ ¢j a2 A2 (1 − y)2 1−y 2
x2j = a y2 =
2
2
= 2
= A.
j=0 j=0
1−y 1−y 1+y
1−y
Then, as y varies from 1 to 0, we have that 1+y
varies from 0 to 1.

A2. Prove that there exist infinitely many integers n such that n, n+1, and n+2 are each
the sum of two squares of integers. [Example: 0 = 02 + 02 , 12 = 02 + 12 , and 2 = 12 + 12 .]

Solution. Note that for any integer a

(a + 1)2 − 1 = a2 + 2a, (a + 1)2 + 02 , (a + 1)2 + 12

will be a triple of such numbers if 2a is a square. Thus choose a = 2m2 , m = 0, 1, · · · .

A3. The octagon P1 P2 P3 P4 P5 P6 P7 P8 is inscribed in a circle, with the vertices around the
circumference in the given order. Given that the polygon P1 P3 P5 P7 is a square of area 5
and the polygon P2 P4 P6 P8 is a rectangle of area 4, find the maximum possible area of the
octagon.
√ √
Solution. A square of area 5, has edge length 5, and diagonal length 10 which is
the diameter of the circle. If x and y (say 0 < x < y) are the dimensions of the rectangle
P2 P4 P6 P8 , then
x2 + y 2 = 10 and xy = 4,
√ √ ¡ √ ¢
and the relevant solution is x = 2, y = 2 2. We may assume that P1 = 12 10, 0 , and
³ √ √ ´
1 1
P2 = 2 10 cos θ, 2 10 sin θ

1
 ¡ ¢ √
for some θ ∈ 0, π2 , and P2 P4 = 2 (otherwise rotate all by 90◦ ). Then
³ √ √ ´
P2 = 12 10 cos (θ + α) , 12 10 sin (θ + α)
¡ ¢
where α is the angle subtended by the side P2 P4 . Since y = 2x, α = 2 arctan 12 . Thus,
¡ ¡ ¢¢ ¡ ¡ ¢¢ ¡ ¡ ¢¢
cos α = cos 2 arctan 12 = cos2 arctan 12 − sin2 arctan 12
³ ´2 ³ ´2 3
= √2 − √15 = and
5 5
4
sin α = .
5
The area of an isosceles triangle with equal sides r at an angle β is 12 r2 sin β. Thus, the area
of the octagon is
³ √ ´2 ¡ ¡ ¢ ¡ ¢ ¢
A (θ) := 2 · 12 · 12 10 sin θ + sin π2 − θ + sin α + θ − π2 + sin (π − (α + θ))
= 52 (sin θ + cos θ − cos (α + θ) + sin (α + θ))
= 52 (sin θ + cos θ − (cos α cos θ − sin α sin θ) + (sin α cos θ + cos α sin θ))
= 52 ((1 + sin α + cos α) sin θ + (1 + sin α − cos α) cos θ)
¡¡ ¢ ¡ ¢ ¢
= 52 1 + 45 + 35 sin θ + 1 + 45 − 35 cos θ
= 6 sin θ + 3 cos θ.

There is a further restriction on θ, namely θ ≥ π2 − α, or else P4 will come before P3 . For

θ = π2 − α, sin θ = cos α = 3/5 and cos θ = 4/5, and
¡ ¢
A π2 − α = 6 · 35 + 3 · 45 = 6, while
¡ ¢
A π2 = 6 · 1 + 3 · 0 = 6.

Now

A0 (θ) = d
(6 sin θ + 3 cos θ) = 6 cos θ − 3 sin θ = 0 ⇒ θ = arctan 2, and
dθ
√
A (arctan 2) = 6 sin (arctan 2) + 3 cos (arctan 2) = 6 √25 + 3 √15 = 3 5 > 6.
√
As θ = arctan 2, the rectangle is “vertical” and the maximum area is 3 5.

A4. Show that the improper integral

Z B
lim sin(x) sin(x2 ) dx
B→∞ 0

converges.

Solution. We use
sin a sin b = 12 (cos (a − b) − cos (a + b))

2
to get
¡ ¡ ¢ ¡ ¢¢
sin(x) sin(x2 ) = cos x − x2 − cos x + x2
1
2
¡ ¡ 2 ¢ ¡ ¢¢
= cos x − x − cos x2 + x
1
2
³ ³¡ ¢2 ´ ³¡ ¢2 ´´
= 12 cos x − 12 − 14 − cos x + 12 − 14
³ ³¡ ¢2 ´ ³¡ ¢2 ´´
= 12 cos x − 12 − 14 − cos x + 12 − 14
 ³¡ ¢´ ³¡ ¢´ 
1 1 2 1 1 2
cos 4 cos x − 2 + sin 4 sin x − 2
= 12  ³ ³¡ ¢ 2
´ ³¡ ¢2 ´´ 
− cos 14 cos x + 12 + sin 14 sin x + 12

Note that
Z ³¡ ´ Z 1
B ¢
1 2
B±
2 ¡ ¢
cos x± 2
dx = cos u2 du, and
1
0 ±
2
Z ³¡ ´ Z 1
B ¢
1 2
B±
2 ¡ ¢
sin x± 2
dx = sin u2 du.
1
0 ±
2

Thus, it suffices to show the existence of improper integrals of the form

Z B Z B
2
lim sin(x ) dx and lim cos(x2 ) dx.
B→∞ 0 B→∞ 0

Consider the parametric curve

µZ u Z u ¶
2 2
r (u) = (x (u) , y (u)) = cos(t ) dt, sin(t ) dt .
0 0

The components are integrals of Fresnel type. Note that

¡ ¢
r0 (u) = (x0 (u) , y 0 (u)) = cos(u2 ), sin(u2 ) and kr0 (u)k = 1.
The curvature is given by
κ (u) = x0 (u) y 00 (u) − y 0 (u) x00 (u) = cos(u2 ) cos(u2 )2u + sin(u2 ) sin(u2 )2u
¡ ¢
= 2u sin2 (u2 ) + cos2 (u2 ) = 2u.
Since the curvature increases with arc length, the curve spirals inward to a limit point and
the integrals then converge. Indeed, the center of curvature of r at r (u) is
1
c (u) = r (u) + (−y 0 (u) , x0 (u))
µZ u 2u Z u ¶
2 2 1 ¡ ¢
= cos(t ) dt, sin(t ) dt + − sin(u2 ), cos(u2 ) , and
0 0 2u
¡ ¢ ¡ ¢ 1 ¡ ¢
c0 (u) = cos(u2 ), sin(u2 ) + − cos(u2 ), − sin(u2 ) + 2 − sin(u2 ), cos(u2 )
2u
1 ¡ 2 2
¢
= − sin(u ), cos(u ) .
2u2
3
Thus, Z Z
∞ ∞
0 1 1
kc (u)k du ≤ du = <∞
1 1 2u2 2
and the length of the curve c| [1, ∞) is finite, implying that L := limu→∞ c (u) exists. Now
1
kr (u) − Lk ≤ kr (u) − c (u)k + kL − c (u)k = + kL − c (u)k → 0
2u
as u → ∞. Thus, limu→∞ r (u) = L, as desired.

A5. Three distinct points with integer coordinates lie in the plane on a circle of radius
r > 0. Show that two of these points are separated by a distance of at least r1/3 .

Solution. Consider the triangle T with sides of length a, b, and c connecting these points.
We first show the standard (?) fact that the area A of T is given by
abc
A= ,
4r
where r is the radius of the circumcircle of T . Let α be the angle of T opposite a. Then
(from the cross product) we have A = 12 bc sin α. On the hand, the central angle opposite a
is known to be 2α and so a = 2r sin α. Thus,
1 abc
A = 12 bc sin α = 12 bc (2r sin α) = .
2r 4r
If d = max (a, b, c), then
d3 abc
≥ = A.
4r 4r
But, using the cross-product again, we know that 2A2 is a determinant
√ of a 2 × 2 integer
2
matrix, and hence a positive integer. Thus, 2A ≥ 1 or A ≥ 1/ 2. Hence,
√ √ ¡ ¢1/3
d3 ≥ 4r/ 2 = 2 2r ⇒ d ≥ 23/2 r = (2r)1/3 > r1/3 .

A6. Let f(x) be a polynomial with integer coefficients. Define a sequence a0 , a1 , ... of
integers such that a0 = 0 and an+1 = f (an ) for all n > 0. Prove that if there exists a positive
integer m for which am = 0 then either a1 = 0 or a2 = 0.

Solution. Assume that a1 6= 0. We must then show that a2 = 0. Note that a1 = f (a0 ) =
f (0) and so a1 is the nonzero constant term in f (x). We have f (am−1 ) = am = 0. Thus,
am−1 is an integer zero of f(x). Since f (x) = (x − am−1 ) g(x) for some g(x) with integer
coefficients, we have that am−1 divides the constant term of f (x), namely a1 . Since a1 is the
constant term of f , we know that a1 divides all the iterates (f ◦ · · · ◦ f ) (a1 ). In particular,
a1 divides am−1 , and we have already shown that am−1 divides a1 . Thus, am−1 = ±a1 . If
am−1 = a1 , then
a2 = f (a1 ) = f (am−1 ) = am = 0.

4
Thus, we are done in the case where an ≥ 0 for all n.
Let an0 = min0≤n≤m {an } and let

g(x) = f (x + an0 ) − an0 .

Defining b0 = 0 and bn+1 = g(bn ), we have

b1 = g(b0 ) = g(0) = f (0 + an0 ) − an0 = an0 +1 − an0 ≥ 0,

b2 = g(b1 ) = g(an0 +1 − an0 ) = f(an0 +1 ) − an0 = an0 +2 − an0 ≥ 0,
..
.
bn = an0 +n − an0 ≥ 0 for all n.

Since an0 +m − an0 = 0, we may then apply the case we have shown to deduce that if bm = 0
for some m > 0, then 0 = b1 = an0 +1 − an0 or 0 = b2 = an0 +2 − an0 = 0. If b1 = 0, then
g(0) = 0 and bn = an0 +n − an0 = 0 for all n, in which case an0 +n = an0 and {an } is a constant
sequence (necessarily zero). If 0 = b2 = an0 +2 − an0 = 0, then {bn } is periodic of period 2 in
n and so is an , in which case a2 = a0 = 0.

B1. Let aj , bj , cj , be integers for 1 ≤ j ≤ N. Assume, for each j, that at least one of aj ,
bj , cj is odd. Show that there exist integers r, s, t such that raj + sbj + tcj is odd for at least
4N/7 values of j, 1 ≤ j ≤ N.

Solution. Note that for fixed j, the evenness or oddness of raj + sbj + tcj depends on
the evenness or oddness of r, s, t and aj , bj , cj . Thus, it suffices to consider (r, s, t) ∈ S :=
{0, 1} × {0, 1} × {0, 1}, and we have a map

F : {(j; aj , bj , cj ) : j ∈ {1, . . . , N }} → S

For (r, s, t) ∈ S, let

(r, s, t)1 := {(ρ, σ, τ ) ∈ S : (r, s, t) · (ρ, σ, τ ) = 1} .

Clearly, (0, 0, 0)1 is empty, and it is easy to check that each of the remaining 7 sets

(1, 0, 0)1 , (0, 1, 0)1 , (0, 0, 1)1 , (1, 1, 0)1 , (0, 1, 1)1 , (1, 0, 1)1 , (1, 1, 1)1

has exactly 4 elements and their union is S − {(0, 0, 0)}. Call these S1 , . . . , S7 . We need to
show that for some i ∈ {1, . . . , 7} , #F −1 (Si ) ≥ 4N/7. Suppose that for all i,

#F −1 (Si ) < 4N/7.

Then, adding we have

#F −1 (S1 ) + · · · + #F −1 (S7 ) < 4N. (∗)

Now ∪7i=1 F −1 (Si ) = F −1 (S), since F −1 ((0, 0, 0)) = φ by assumption. Each F ((aj , bj , cj ))
belongs to exactly 4 of the Si , namely those (r, s, t)1 such that (r, s, t) ∈ F ((aj , bj , cj ))1 .
Thus, the left side of (∗) is 4N, and we have a contradiction.

5
 B2. Prove that the expression µ ¶
gcd(m, n) n
n m
¡n¢ n!
is an integer for all pairs of integers n ≥ m ≥ 1. [Here m
= m!(n−m)!
, and gcd(m, n) is the
greatest common divisor of m and n.]

Solution. Note gcd(m, n) lcm(m, n) = mn. Thus,

µ ¶
n
n divides gcd(m, n)
m
µ ¶
mn n
⇔ n divides
lcm(m, n) m
µ ¶
n
⇔ lcm(m, n) divides m
m
µ ¶ µ ¶
n n
⇔ m divides m , and n divides m ,
m m
¡n¢
but certainly m divides m m while
µ ¶ µ ¶
n n! (n − 1)! n−1
m =m =n =n
m m! (n − m)! (m − 1)! (n − m)! m−1
¡n¢
and so n divides m m .
P
B3. Let f (t) = N j=1 aj sin(2πjt), where each aj is real and aN 6= 0. Let Nk denote the
k
number of zeros (including multiplicities) of dtd k f(t). Prove that

N0 ≤ N1 ≤ N2 ≤ . . . and lim Nk = 2N.

k→∞

Solution. Here, they must have meant to restrict the domain to [0, 1), or equivalently, to
the circle R/Z. By Rolle’s Theorem, between any two zeros of f (k) (t) there is at least one
zero of f (k+1) (t). Since f (k) is defined on a circle, we then have Nk ≤ Nk+1 . Note that

4k
N
X
(4k)
f (t) = (2π) j 4k aj sin(2πjt)
j=1

and eventually the maximum and minimum values of the term N 4k aN sin(2πN t) will domi-
nate the value of the sum of the lower terms, since
N−1
X N−1
X
j 4k |aj | ≤ (N − 1)4k |aj | ≤ N 4k |aN | ,
j=1 j=1

6
for k sufficiently large. Thus, f (4k) has at least 2N zeros for k sufficiently large. Also, for
z = e(2πt)i , we have

4k
N
X (z j − z −j )
(4k) 4k
f (t) = (2π) j aj
j=1
2i
¡ ¢
XN
z N+j
− z N−j
= (2π)4k j 4k aj
j=1
2iz N
p (z)
=
zN
for a polynomial p (z) of degree 2N . Thus, f (4k) also has at most 2N zeros.

B4. Let f(x) be a continuous function such that f (2x2 − 1) = 2xf(x) for all x. Show that
f (x) = 0 for −1 ≤ x ≤ 1.

Solution. Note that cos (2u) = cos2 (u) − sin2 (u) = 2 cos2 u − 1. Thus,
f(cos (2u)) = 2 cos (u) f (cos (u))
and
sin (v)
f (cos v) = 2 cos (v/2) f (cos (v/2)) = f(cos (v/2))
sin (v/2)
sin (v) sin (v/2)
= f(cos (v/4))
sin (v/2) sin (v/4)
sin (v) ¡ k¢
= ··· = f (cos v/2 )
sin (v/2k )
Also − cos (2u) = sin2 (u) − cos2 (u) = 2 sin2 u − 1, so that
f (− cos (2u)) = 2 sin (u) f (sin (u))
Note that f is odd since 2xf(x) = f (2x2 − 1) is even. Thus,
2 sin (u) f(sin (u)) = f (− cos (2u)) = −f(cos (2u)) = −2 cos (u) f (cos (u)) or
sin (u)
f(cos (u)) = − f (sin (u)) if cos (u) 6= 0.
cos (u)
Hence, as k → ∞ and f (0) = 0 due to the oddness of f, we have
sin (v) ¡ k¢ sin (v) ¡ k¢
f (cos v) = f (cos v/2 ) = − f(sin v/2 ) → 0.
sin (v/2k ) cos (v/2k )

B5. Let S0 be a finite set of positive integers. We define finite sets S1 , S2 , ... of positive
integers as follows:
Integer a is in Sn+1 , if and only if exactly one of a − 1 or a is in Sn .

7
Show that there exist infinitely many integers N for which SN = S0 ∪ {N + a : a ∈ S0 }.

Solution. Let pn (x) be a polynomial with coefficients in Z2 , such that the coefficient
ak (n) of xk in pn (x) is 1 when k ∈ Sk and 0 otherwise. Note that the coefficient ak (n + 1)
of pn+1 (x) is given by
½
0 if ak (n) + ak−1 (n) = 1
ak (n + 1) =
1 if ak (n) + ak−1 (n) = 0.
This is also the coefficient of xk for the polynomial pn (x) + xpn (x) = (1 + x) pn (x) . Thus,
pn+1 (x) = (x + 1) pn (x) and pn (x) = (1 + x)n p0 (x) .
We must show that there are infinitely many N, such that
¡ ¢
pN (x) = p0 (x) + xN p0 (x) = 1 + xN p0 (x) .
In other words, that there are infinitely many n, such that
(1 + x)N = 1 + xN
This, is true for N = 2 and note that if it is true for N , then it is true for 2N, since
³ ´2 ¡ ¢2
(1 + x)2N = (1 + x)N = 1 + xN = 1 + 2xN + x2N = 1 + x2N .

Thus, SN = S0 ∪ {N + a : a ∈ S0 } for N equal to a power of 2.

B6. Let B be a set of more than 2n+1 /n distinct points with coordinates of the form
(±1, ±1, ..., ±1) in n-dimensional space, with n ≥ 3. Show that there are three distinct
points in B which are the vertices of an equilateral triangle.

Solution. Let
C = {(x1 , x2 , ..., xn ) : xi = ±1}
For a fixed point p ∈ C, let Sp be the set of points in C of minimal distance (namely 2) from
p. A point q ∈ Sp if q differs from p in one coordinate. Note that two points q1 , q2 ∈ Sp
agree in all but two√coordinates, namely the distinct coordinates in which they differ from p.
Thus, kq1 − q2 k = 8, and hence all points in Sp are equidistant from each other. It suffices
to show that there is some p ∈ C, with # (B ∩ Sp ) ≥ 3. Consider the set
A = {(q, p) : q ∈ B ∩ Sp }
Note that for each q ∈ B, there are n points p1 (q) , . . . , pn (q) with q ∈ Spi (q) . Thus,
#A = n · # (B) .
Also, for each p, the number of q ∈ B with (q, p) ∈ A is # (Sp ∩ B). Thus,
X
# (B ∩ Sp ) = #A = n · # (B) > n · 2n+1 /n = 2n+1 = 2 · 2n
p∈C

Since there are 2n terms on the left side, one of them must be bigger than 2.