The 2017 Putnam Competition Problems and Solutions
A1. Let S be the smallest set of positive integers such that
a) 2 is in S,
b) n is in S whenever n2 is in S, and
c) (n + 5)2 is in S whenever n is in S.
Which positive integers are not in S?
(The set S is “smallest” in the sense that S is contained in any other such set.)
Answer. The positive integers that are not in S are 1 and the multiples of 5.
Solution. First note that by combining conditions c) and b), n ∈ S implies n+5 ∈ S.
Also, because 2 ∈ S, we have 72 = 49 ∈ S and therefore (49 + 5)2 = 542 ∈ S. Thus,
because 542 ≡ 1 (mod 5), all sufficiently large positive integers that are ≡ 1 (mod 5)
are in S.
Now let a > 1 be an integer that is not a multiple of 5. Then the sequence
a, a2 , a4 , a8 , a16 , . . . grows without bound, and by Fermat’s little theorem (or by a
check of cases mod 5) all the terms of the sequence starting with a4 are ≡ 1 (mod 5).
Thus the sequence contains elements of S, and by repeated application of condition
b) it follows that a ∈ S.
On the other hand, it is easy to check that the set of all integers greater than 1
that are not multiples of 5 satisfies conditions a), b), and c), so this is the set S, and
the complement of S consists of the integers listed in the answer.
A2. Let Q0 (x) = 1, Q1 (x) = x, and
(Qn−1 (x))2 − 1
Qn (x) =
Qn−2 (x)
for all n ≥ 2. Show that, whenever n is a positive integer, Qn (x) is equal to a
polynomial with integer coefficients.
Solution 1. Let a sequence of polynomials be defined by P−1 (x) = 0, P0 (x) = 1, and
Pn (x) = xPn−1 (x) − Pn−2 (x) for all n ≥ 1. Clearly, these polynomials have integer
coefficients, so it will be enough to show that Qn (x) = Pn (x) for all n ≥ 0. Note that
for all n ≥ 2,
Pn (x) −Pn−1 (x) x −1 Pn−1 (x) −Pn−2 (x)
= = ···
Pn−1 (x) −Pn−2 (x) 1 0 Pn−2 (x) −Pn−3 (x)
n−1
x −1 P1 (x) −P0 (x)
=
1 0 P0 (x) −P−1 (x)
n
x −1
= .
1 0
Taking determinants of both sides, we see that
(Pn−1 (x))2 − 1
−Pn (x)Pn−2 (x) + (Pn−1 (x))2 = 1n = 1, which implies Pn (x) = .
Pn−2 (x)
But this is precisely the defining recurrence relation for Qn (x), and since
P0 (x) = Q0 (x) and P1 (x) = Q1 (x), we are done.
, Solution 2. To show that the Qn (x) are polynomials with integer coefficients, we
will show that they also satisfy the simpler recurrence Qn (x) = x Qn−1 (x) − Qn−2 (x).
The proof is by induction on n ≥ 2; for n = 2 we check directly that
(Q1 (x))2 − 1
Q2 (x) = = x2 − 1 = x Q1 (x) − Q0 (x).
Q0 (x)
Assuming that Qn (x) = x Qn−1 (x) − Qn−2 (x) for n = N − 1, define
RN (x) = x QN −1 (x) − QN −2 (x). Then
RN (x)QN −2 (x) = xQN −1 (x)QN −2 (x) − (QN −2 (x))2
(QN −2 (x))2 − 1
= xQN −1 (x)QN −2 (x) − · QN −3 (x) + 1
QN −3 (x)
= xQN −1 (x)QN −2 (x) − QN −1 (x)QN −3 (x) − 1
= QN −1 (x) xQN −2 (x) − QN −3 (x) − 1
= (QN −1 (x))2 − 1 by induction hypothesis, so
(QN −1 (x))2 − 1
RN (x) = = QN (x), and we are done.
QN −2 (x)
A3. Let a and b be real numbers with R b a < b, and R b let f and g be continuous functions
from [a, b] to (0, ∞) such that a f (x) dx = a g(x) dx but f 6= g. For every positive
integer n, define
Z b
(f (x))n+1
In = dx .
a (g(x))n
Show that I1 , I2 , I3 , . . . is an increasing sequence with lim In = ∞.
n→∞
Solution. First consider
Z b Z b
(f (x))n+1 (f (x))n
In − In−1 = dx − dx
a (g(x))n a (g(x))
n−1
Z b
(f (x))n+1 − g(x)(f (x))n
= dx
a (g(x))n
(f (x))n − (g(x))n f (x) − g(x)
Z b
= n
+ f (x) − g(x) dx
a (g(x))
(f (x)) − (g(x))n f (x) − g(x)
n
Z b Z b
= dx + f (x) − g(x) dx.
a (g(x))n a
The first integral is positive, because the integrand is nonnegative, continuous, and
not everywhere zero (given f 6= g). The second integral is zero, because the integrals
of f and g over the interval are equal. Thus In − In−1 is positive for all n ≥ 2, so the
sequence (In ) is increasing.
Next, we claim that there exist a subinterval I ⊆ [a, b] of positive length L and
f (x)
a constant M > 1 so that ≥ M for all x ∈ I. Proof: Because f (x) 6= g(x)
g(x)
for some x ∈ [a, b] and f − g is continuous, there is a subinterval on which either
f − g > 0 or f − g < 0. But in the latter case there must also be a point x ∈ [a, b]
(and hence a subinterval of [a, b]) where f (x) > g(x), otherwise we would have
A1. Let S be the smallest set of positive integers such that
a) 2 is in S,
b) n is in S whenever n2 is in S, and
c) (n + 5)2 is in S whenever n is in S.
Which positive integers are not in S?
(The set S is “smallest” in the sense that S is contained in any other such set.)
Answer. The positive integers that are not in S are 1 and the multiples of 5.
Solution. First note that by combining conditions c) and b), n ∈ S implies n+5 ∈ S.
Also, because 2 ∈ S, we have 72 = 49 ∈ S and therefore (49 + 5)2 = 542 ∈ S. Thus,
because 542 ≡ 1 (mod 5), all sufficiently large positive integers that are ≡ 1 (mod 5)
are in S.
Now let a > 1 be an integer that is not a multiple of 5. Then the sequence
a, a2 , a4 , a8 , a16 , . . . grows without bound, and by Fermat’s little theorem (or by a
check of cases mod 5) all the terms of the sequence starting with a4 are ≡ 1 (mod 5).
Thus the sequence contains elements of S, and by repeated application of condition
b) it follows that a ∈ S.
On the other hand, it is easy to check that the set of all integers greater than 1
that are not multiples of 5 satisfies conditions a), b), and c), so this is the set S, and
the complement of S consists of the integers listed in the answer.
A2. Let Q0 (x) = 1, Q1 (x) = x, and
(Qn−1 (x))2 − 1
Qn (x) =
Qn−2 (x)
for all n ≥ 2. Show that, whenever n is a positive integer, Qn (x) is equal to a
polynomial with integer coefficients.
Solution 1. Let a sequence of polynomials be defined by P−1 (x) = 0, P0 (x) = 1, and
Pn (x) = xPn−1 (x) − Pn−2 (x) for all n ≥ 1. Clearly, these polynomials have integer
coefficients, so it will be enough to show that Qn (x) = Pn (x) for all n ≥ 0. Note that
for all n ≥ 2,
Pn (x) −Pn−1 (x) x −1 Pn−1 (x) −Pn−2 (x)
= = ···
Pn−1 (x) −Pn−2 (x) 1 0 Pn−2 (x) −Pn−3 (x)
n−1
x −1 P1 (x) −P0 (x)
=
1 0 P0 (x) −P−1 (x)
n
x −1
= .
1 0
Taking determinants of both sides, we see that
(Pn−1 (x))2 − 1
−Pn (x)Pn−2 (x) + (Pn−1 (x))2 = 1n = 1, which implies Pn (x) = .
Pn−2 (x)
But this is precisely the defining recurrence relation for Qn (x), and since
P0 (x) = Q0 (x) and P1 (x) = Q1 (x), we are done.
, Solution 2. To show that the Qn (x) are polynomials with integer coefficients, we
will show that they also satisfy the simpler recurrence Qn (x) = x Qn−1 (x) − Qn−2 (x).
The proof is by induction on n ≥ 2; for n = 2 we check directly that
(Q1 (x))2 − 1
Q2 (x) = = x2 − 1 = x Q1 (x) − Q0 (x).
Q0 (x)
Assuming that Qn (x) = x Qn−1 (x) − Qn−2 (x) for n = N − 1, define
RN (x) = x QN −1 (x) − QN −2 (x). Then
RN (x)QN −2 (x) = xQN −1 (x)QN −2 (x) − (QN −2 (x))2
(QN −2 (x))2 − 1
= xQN −1 (x)QN −2 (x) − · QN −3 (x) + 1
QN −3 (x)
= xQN −1 (x)QN −2 (x) − QN −1 (x)QN −3 (x) − 1
= QN −1 (x) xQN −2 (x) − QN −3 (x) − 1
= (QN −1 (x))2 − 1 by induction hypothesis, so
(QN −1 (x))2 − 1
RN (x) = = QN (x), and we are done.
QN −2 (x)
A3. Let a and b be real numbers with R b a < b, and R b let f and g be continuous functions
from [a, b] to (0, ∞) such that a f (x) dx = a g(x) dx but f 6= g. For every positive
integer n, define
Z b
(f (x))n+1
In = dx .
a (g(x))n
Show that I1 , I2 , I3 , . . . is an increasing sequence with lim In = ∞.
n→∞
Solution. First consider
Z b Z b
(f (x))n+1 (f (x))n
In − In−1 = dx − dx
a (g(x))n a (g(x))
n−1
Z b
(f (x))n+1 − g(x)(f (x))n
= dx
a (g(x))n
(f (x))n − (g(x))n f (x) − g(x)
Z b
= n
+ f (x) − g(x) dx
a (g(x))
(f (x)) − (g(x))n f (x) − g(x)
n
Z b Z b
= dx + f (x) − g(x) dx.
a (g(x))n a
The first integral is positive, because the integrand is nonnegative, continuous, and
not everywhere zero (given f 6= g). The second integral is zero, because the integrals
of f and g over the interval are equal. Thus In − In−1 is positive for all n ≥ 2, so the
sequence (In ) is increasing.
Next, we claim that there exist a subinterval I ⊆ [a, b] of positive length L and
f (x)
a constant M > 1 so that ≥ M for all x ∈ I. Proof: Because f (x) 6= g(x)
g(x)
for some x ∈ [a, b] and f − g is continuous, there is a subinterval on which either
f − g > 0 or f − g < 0. But in the latter case there must also be a point x ∈ [a, b]
(and hence a subinterval of [a, b]) where f (x) > g(x), otherwise we would have
