The 83rd William Lowell Putnam Mathematical Competition
Saturday, December 3, 2022
A1 Determine all ordered pairs of real numbers (a, b) such B2 Let × represent the cross product in R3 . For what posi-
that the line y = ax + b intersects the curve y = ln(1 + tive integers n does there exist a set S ⊂ R3 with exactly
x2 ) in exactly one point. n elements such that
A2 Let n be an integer with n ≥ 2. Over all real polynomials S = {v × w : v, w ∈ S}?
p(x) of degree n, what is the largest possible number of
negative coefficients of p(x)2 ? B3 Assign to each positive real number a color, either red
or blue. Let D be the set of all distances d > 0 such
A3 Let p be a prime number greater than 5. Let f (p) denote that there are two points of the same color at distance
the number of infinite sequences a1 , a2 , a3 , . . . such that d apart. Recolor the positive reals so that the numbers
an ∈ {1, 2, . . . , p − 1} and an an+2 ≡ 1 + an+1 (mod p) in D are red and the numbers not in D are blue. If we
for all n ≥ 1. Prove that f (p) is congruent to 0 or 2 iterate this recoloring process, will we always end up
(mod 5). with all the numbers red after a finite number of steps?
B4 Find all integers n with n ≥ 4 for which there exists a
A4 Suppose that X1 , X2 , . . . are real numbers between 0 and sequence of distinct real numbers x1 , . . . , xn such that
1 that are chosen independently and uniformly at ran- each of the sets
dom. Let S = ∑ki=1 Xi /2i , where k is the least positive
integer such that Xk < Xk+1 , or k = ∞ if there is no such {x1 , x2 , x3 }, {x2 , x3 , x4 }, . . . ,
integer. Find the expected value of S. {xn−2 , xn−1 , xn }, {xn−1 , xn , x1 }, and {xn , x1 , x2 }
A5 Alice and Bob play a game on a board consisting of forms a 3-term arithmetic progression when arranged in
one row of 2022 consecutive squares. They take turns increasing order.
placing tiles that cover two adjacent squares, with Alice
going first. By rule, a tile must not cover a square that B5 For 0 ≤ p ≤ 1/2, let X1 , X2 , . . . be independent random
is already covered by another tile. The game ends when variables such that
no tile can be placed according to this rule. Alice’s goal
is to maximize the number of uncovered squares when 1
with probability p,
the game ends; Bob’s goal is to minimize it. What is Xi = −1 with probability p,
the greatest number of uncovered squares that Alice can
0 with probability 1 − 2p,
ensure at the end of the game, no matter how Bob plays?
for all i ≥ 1. Given a positive integer n and integers
A6 Let n be a positive integer. Determine, in terms of n, b, a1 , . . . , an , let P(b, a1 , . . . , an ) denote the probability
the largest integer m with the following property: There that a1 X1 + · · · + an Xn = b. For which values of p is it
exist real numbers x1 , . . . , x2n with −1 < x1 < x2 < · · · < the case that
x2n < 1 such that the sum of the lengths of the n intervals
P(0, a1 , . . . , an ) ≥ P(b, a1 , . . . , an )
[x12k−1 , x22k−1 ], [x32k−1 , x42k−1 ], . . . , [x2n−1
2k−1 2k−1
, x2n ]
for all positive integers n and all integers b, a1 , . . . , an ?
is equal to 1 for all integers k with 1 ≤ k ≤ m. B6 Find all continuous functions f : R+ → R+ such that
B1 Suppose that P(x) = a1 x + a2 x2 + · · · + an xn is a poly- f (x f (y)) + f (y f (x)) = 1 + f (x + y)
nomial with integer coefficients, with a1 odd. Suppose
that eP(x) = b0 + b1 x + b2 x2 + · · · for all x. Prove that bk for all x, y > 0.
is nonzero for all k ≥ 0.
, Solutions to the 83rd William Lowell Putnam Mathematical Competition
Saturday, December 3, 2022
Manjul Bhargava, Kiran Kedlaya, and Lenny Ng
A1 Write f (x) = ln(1 + x2 ). We show that y = ax + b inter- A2 The answer is 2n−2. Write p(x) = an xn +· · ·+a1 x+a0
sects y = f (x) in exactly one point if and only if (a, b) and p(x)2 = b2n x2n + · · · + b1 x + b0 . Note that b0 = a20
lies in one of the following groups: and b2n = a2n . We claim that not all of the remain-
ing 2n − 1 coefficients b1 , . . . , b2n−1 can be negative,
– a=b=0
whence the largest possible number of negative coef-
– |a| ≥ 1, arbitrary b ficients is ≤ 2n − 2. Indeed, suppose bi < 0 for 1 ≤ i ≤
– 0 < |a| < 1, and b < ln(1 − r− )2 − |a|r− or b > 2n − 1. Since b1 = 2a0 a1 , we have a0 ̸= 0. Assume
ln(1 − r+ )2 − |a|r+ , where a0 > 0 (or else replace p(x) by −p(x)). We claim by
√ induction on i that ai < 0 for 1 ≤ i ≤ n. For i = 1, this
1 ± 1 − a2 follows from 2a0 a1 = b1 < 0. If ai < 0 for 1 ≤ i ≤ k − 1,
r± = .
a then
Since the graph of y = f (x) is symmetric under re- k−1
flection in the y-axis, it suffices to consider the case 2a0 ak = bk − ∑ ai ak−i < bk < 0
i=1
a ≥ 0: y = ax + b and y = −ax + b intersect y = f (x) the
same number of times. For a = 0, by the symmetry of and thus ak < 0, completing the induction step. But now
y = f (x) and the fact that f (x) > 0 for all x ̸= 0 implies b2n−1 = 2an−1 an > 0, contradiction.
that the only line y = b that intersects y = f (x) exactly
It remains to show that there is a polynomial p(x) such
once is the line y = 0.
that p(x)2 has 2n−2 negative coefficients. For example,
We next observe that on [0, ∞), f ′ (x) = 1+x2x
2 increases we may take
′ ′
on [0, 1] from f (0) = 0 to a maximum at f (1) = 1, and
then decreases on [1, ∞) with limx→∞ f ′ (x) = 0. In par- p(x) = n(xn + 1) − 2(xn−1 + · · · + x),
ticular, f ′ (x) ≤ 1 for all x (including x < 0 since then
f ′ (x) < 0) and f ′ (x) achieves each value in (0, 1) ex- so that
actly twice on [0, ∞).
p(x)2 = n2 (x2n + xn + 1) − 2n(xn + 1)(xn−1 + · · · + x)
For a ≥ 1, we claim that any line y = ax + b inter-
sects y = f (x) exactly once. They must intersect at + (xn−1 + · · · + x)2 .
least once by the intermediate value theorem: for x ≪ 0,
For i ∈ {1, . . . , n − 1, n + 1, . . . , n − 1}, the coefficient of
ax + b < 0 < f (x), while for x ≫ 0, ax + b > f (x) since
ln(1+x2 )
xi in p(x)2 is at most −2n (coming from the cross term)
limx→∞ x = 0. On the other hand, they cannot plus −2n + 2 (from expanding (xn−1 + · · · + x)2 ), and
intersect more than once: for a > 1, this follows from hence negative.
the mean value theorem, since f ′ (x) < a for all x. For
a = 1, suppose that they intersect at two points (x0 , y0 ) A3 First solution. We view the sequence a1 , a2 , . . . as
and (x1 , y1 ). Then lying in F×p ⊂ F p . Then the sequence is determined
R x1 ′ by the values of a1 and a2 , via the recurrence an+2 =
y1 − y0 x0 f (x) dx (1 + an+1 )/an . Using this recurrence, we compute
1= = <1
x1 − x0 x1 − x0
1 + a2 1 + a1 + a2
a3 = , a4 = ,
since f ′ (x) is continuous and f ′ (x) ≤ 1 with equality a1 a1 a2
only at one point. 1 + a1
a5 = , a6 = a1 , a7 = a2
Finally we consider 0 < a < 1. The equation f ′ (x) = a2
a has exactly two solutions, at x = r− and x = r+ for
r± as defined above. If we define g(x) = f (x) − ax, and thus the sequence is periodic with period 5. The
then g′ (r± ) = 0; g′ is strictly decreasing on (−∞, r− ), values for a1 and a2 may thus be any values in F× p pro-
strictly increasing on (r− , r+ ), and strictly decreasing vided that a1 ̸= p − 1, a2 ̸= p − 1, and a1 + a2 ̸= p − 1.
on (r+ , ∞); and limx→−∞ g(x) = ∞ while limx→∞ g(x) = The number of choices for a1 , a2 ∈ {1, . . . , p − 2} such
−∞. It follows that g(x) = b has exactly one solution that a1 + a2 ̸= p − 1 is thus (p − 2)2 − (p − 2) = (p −
for b < g(r− ) or b > g(r+ ), exactly three solutions for 2)(p − 3).
g(r− ) < b < g(r+ ), and exactly two solutions for b = Since p is not a multiple of 5, (p − 2)(p − 3) is a prod-
g(r± ). That is, y = ax + b intersects y = f (x) in exactly uct of two consecutive integers a, a + 1, where a ̸≡ 2
one point if and only if b < g(r− ) or b > g(r+ ). (mod 5). Now 0 · 1 ≡ 0, 1 · 2 ≡ 2, 3 · 4 ≡ 2, and
Saturday, December 3, 2022
A1 Determine all ordered pairs of real numbers (a, b) such B2 Let × represent the cross product in R3 . For what posi-
that the line y = ax + b intersects the curve y = ln(1 + tive integers n does there exist a set S ⊂ R3 with exactly
x2 ) in exactly one point. n elements such that
A2 Let n be an integer with n ≥ 2. Over all real polynomials S = {v × w : v, w ∈ S}?
p(x) of degree n, what is the largest possible number of
negative coefficients of p(x)2 ? B3 Assign to each positive real number a color, either red
or blue. Let D be the set of all distances d > 0 such
A3 Let p be a prime number greater than 5. Let f (p) denote that there are two points of the same color at distance
the number of infinite sequences a1 , a2 , a3 , . . . such that d apart. Recolor the positive reals so that the numbers
an ∈ {1, 2, . . . , p − 1} and an an+2 ≡ 1 + an+1 (mod p) in D are red and the numbers not in D are blue. If we
for all n ≥ 1. Prove that f (p) is congruent to 0 or 2 iterate this recoloring process, will we always end up
(mod 5). with all the numbers red after a finite number of steps?
B4 Find all integers n with n ≥ 4 for which there exists a
A4 Suppose that X1 , X2 , . . . are real numbers between 0 and sequence of distinct real numbers x1 , . . . , xn such that
1 that are chosen independently and uniformly at ran- each of the sets
dom. Let S = ∑ki=1 Xi /2i , where k is the least positive
integer such that Xk < Xk+1 , or k = ∞ if there is no such {x1 , x2 , x3 }, {x2 , x3 , x4 }, . . . ,
integer. Find the expected value of S. {xn−2 , xn−1 , xn }, {xn−1 , xn , x1 }, and {xn , x1 , x2 }
A5 Alice and Bob play a game on a board consisting of forms a 3-term arithmetic progression when arranged in
one row of 2022 consecutive squares. They take turns increasing order.
placing tiles that cover two adjacent squares, with Alice
going first. By rule, a tile must not cover a square that B5 For 0 ≤ p ≤ 1/2, let X1 , X2 , . . . be independent random
is already covered by another tile. The game ends when variables such that
no tile can be placed according to this rule. Alice’s goal
is to maximize the number of uncovered squares when 1
with probability p,
the game ends; Bob’s goal is to minimize it. What is Xi = −1 with probability p,
the greatest number of uncovered squares that Alice can
0 with probability 1 − 2p,
ensure at the end of the game, no matter how Bob plays?
for all i ≥ 1. Given a positive integer n and integers
A6 Let n be a positive integer. Determine, in terms of n, b, a1 , . . . , an , let P(b, a1 , . . . , an ) denote the probability
the largest integer m with the following property: There that a1 X1 + · · · + an Xn = b. For which values of p is it
exist real numbers x1 , . . . , x2n with −1 < x1 < x2 < · · · < the case that
x2n < 1 such that the sum of the lengths of the n intervals
P(0, a1 , . . . , an ) ≥ P(b, a1 , . . . , an )
[x12k−1 , x22k−1 ], [x32k−1 , x42k−1 ], . . . , [x2n−1
2k−1 2k−1
, x2n ]
for all positive integers n and all integers b, a1 , . . . , an ?
is equal to 1 for all integers k with 1 ≤ k ≤ m. B6 Find all continuous functions f : R+ → R+ such that
B1 Suppose that P(x) = a1 x + a2 x2 + · · · + an xn is a poly- f (x f (y)) + f (y f (x)) = 1 + f (x + y)
nomial with integer coefficients, with a1 odd. Suppose
that eP(x) = b0 + b1 x + b2 x2 + · · · for all x. Prove that bk for all x, y > 0.
is nonzero for all k ≥ 0.
, Solutions to the 83rd William Lowell Putnam Mathematical Competition
Saturday, December 3, 2022
Manjul Bhargava, Kiran Kedlaya, and Lenny Ng
A1 Write f (x) = ln(1 + x2 ). We show that y = ax + b inter- A2 The answer is 2n−2. Write p(x) = an xn +· · ·+a1 x+a0
sects y = f (x) in exactly one point if and only if (a, b) and p(x)2 = b2n x2n + · · · + b1 x + b0 . Note that b0 = a20
lies in one of the following groups: and b2n = a2n . We claim that not all of the remain-
ing 2n − 1 coefficients b1 , . . . , b2n−1 can be negative,
– a=b=0
whence the largest possible number of negative coef-
– |a| ≥ 1, arbitrary b ficients is ≤ 2n − 2. Indeed, suppose bi < 0 for 1 ≤ i ≤
– 0 < |a| < 1, and b < ln(1 − r− )2 − |a|r− or b > 2n − 1. Since b1 = 2a0 a1 , we have a0 ̸= 0. Assume
ln(1 − r+ )2 − |a|r+ , where a0 > 0 (or else replace p(x) by −p(x)). We claim by
√ induction on i that ai < 0 for 1 ≤ i ≤ n. For i = 1, this
1 ± 1 − a2 follows from 2a0 a1 = b1 < 0. If ai < 0 for 1 ≤ i ≤ k − 1,
r± = .
a then
Since the graph of y = f (x) is symmetric under re- k−1
flection in the y-axis, it suffices to consider the case 2a0 ak = bk − ∑ ai ak−i < bk < 0
i=1
a ≥ 0: y = ax + b and y = −ax + b intersect y = f (x) the
same number of times. For a = 0, by the symmetry of and thus ak < 0, completing the induction step. But now
y = f (x) and the fact that f (x) > 0 for all x ̸= 0 implies b2n−1 = 2an−1 an > 0, contradiction.
that the only line y = b that intersects y = f (x) exactly
It remains to show that there is a polynomial p(x) such
once is the line y = 0.
that p(x)2 has 2n−2 negative coefficients. For example,
We next observe that on [0, ∞), f ′ (x) = 1+x2x
2 increases we may take
′ ′
on [0, 1] from f (0) = 0 to a maximum at f (1) = 1, and
then decreases on [1, ∞) with limx→∞ f ′ (x) = 0. In par- p(x) = n(xn + 1) − 2(xn−1 + · · · + x),
ticular, f ′ (x) ≤ 1 for all x (including x < 0 since then
f ′ (x) < 0) and f ′ (x) achieves each value in (0, 1) ex- so that
actly twice on [0, ∞).
p(x)2 = n2 (x2n + xn + 1) − 2n(xn + 1)(xn−1 + · · · + x)
For a ≥ 1, we claim that any line y = ax + b inter-
sects y = f (x) exactly once. They must intersect at + (xn−1 + · · · + x)2 .
least once by the intermediate value theorem: for x ≪ 0,
For i ∈ {1, . . . , n − 1, n + 1, . . . , n − 1}, the coefficient of
ax + b < 0 < f (x), while for x ≫ 0, ax + b > f (x) since
ln(1+x2 )
xi in p(x)2 is at most −2n (coming from the cross term)
limx→∞ x = 0. On the other hand, they cannot plus −2n + 2 (from expanding (xn−1 + · · · + x)2 ), and
intersect more than once: for a > 1, this follows from hence negative.
the mean value theorem, since f ′ (x) < a for all x. For
a = 1, suppose that they intersect at two points (x0 , y0 ) A3 First solution. We view the sequence a1 , a2 , . . . as
and (x1 , y1 ). Then lying in F×p ⊂ F p . Then the sequence is determined
R x1 ′ by the values of a1 and a2 , via the recurrence an+2 =
y1 − y0 x0 f (x) dx (1 + an+1 )/an . Using this recurrence, we compute
1= = <1
x1 − x0 x1 − x0
1 + a2 1 + a1 + a2
a3 = , a4 = ,
since f ′ (x) is continuous and f ′ (x) ≤ 1 with equality a1 a1 a2
only at one point. 1 + a1
a5 = , a6 = a1 , a7 = a2
Finally we consider 0 < a < 1. The equation f ′ (x) = a2
a has exactly two solutions, at x = r− and x = r+ for
r± as defined above. If we define g(x) = f (x) − ax, and thus the sequence is periodic with period 5. The
then g′ (r± ) = 0; g′ is strictly decreasing on (−∞, r− ), values for a1 and a2 may thus be any values in F× p pro-
strictly increasing on (r− , r+ ), and strictly decreasing vided that a1 ̸= p − 1, a2 ̸= p − 1, and a1 + a2 ̸= p − 1.
on (r+ , ∞); and limx→−∞ g(x) = ∞ while limx→∞ g(x) = The number of choices for a1 , a2 ∈ {1, . . . , p − 2} such
−∞. It follows that g(x) = b has exactly one solution that a1 + a2 ̸= p − 1 is thus (p − 2)2 − (p − 2) = (p −
for b < g(r− ) or b > g(r+ ), exactly three solutions for 2)(p − 3).
g(r− ) < b < g(r+ ), and exactly two solutions for b = Since p is not a multiple of 5, (p − 2)(p − 3) is a prod-
g(r± ). That is, y = ax + b intersects y = f (x) in exactly uct of two consecutive integers a, a + 1, where a ̸≡ 2
one point if and only if b < g(r− ) or b > g(r+ ). (mod 5). Now 0 · 1 ≡ 0, 1 · 2 ≡ 2, 3 · 4 ≡ 2, and
