Solutions to the 82nd William Lowell Putnam Mathematical Competition

Saturday, December 4, 2021

Manjul Bhargava, Kiran Kedlaya, and Lenny Ng

A1 The answer is 578. the error term O(x1−1/r ) is bounded in absolute value by
Each hop corresponds to adding one of the 12 vectors (r + 1)r(x + 1)r−1 /xr . For x ≥ 1, r ≤ 1 this quantity is
(0, ±5), (±5, 0), (±3, ±4), (±4, ±3) to the position bounded in absolute value by 2(r + 1)r, independently
of the grasshopper. Since (2021, 2021) = 288(3, 4) + of x. This allows us to continue by interchanging the
288(4, 3) + (0, 5) + (5, 0), the grasshopper can reach order of the limits, obtaining
(2021, 2021) in 288 + 288 + 1 + 1 = 578 hops.
lim lim (r + 1 + O(x1−1/r ))1/r
On the other hand, let z = x + y denote the sum of the x r→0 x→∞
and y coordinates of the grasshopper, so that it starts at = lim (r + 1)1/r
z = 0 and ends at z = 4042. Each hop changes the sum r→0
of the x and y coordinates of the grasshopper by at most = lim (1 + 1/s)s = e,
s→∞
7, and 4042 > 577 × 7; it follows immediately that the
grasshopper must take more than 577 hops to get from where in the last step we take s = 1/r.
(0, 0) to (2021, 2021).
Remark. This solution implicitly uses the distance A3 The integers N with this property are those of the form
function 3m2 for some positive integer m.
In one direction, for N = 3m2 , the points
d((x1 , y1 ), (x2 , y2 )) = |x1 − x2 | + |y1 − y2 |
on the plane, variously called the taxicab metric, the (m, m, m), (m, −m, −m), (−m, m, −m), (−m, −m, m)
Manhattan metric, or the L1 -norm (or `1 -norm).
form the vertices of a regular tetrahedron inscribed in
A2 The limit is e. the sphere x2 + y2 + z2 = N.
First solution. By l’Hôpital’s Rule, we have Conversely, suppose that Pi = (xi , yi , zi ) for i = 1, . . . , 4
log((x + 1)r+1 − xr+1 ) are the vertices of an inscribed regular tetrahedron.
lim Then the center of this tetrahedron must equal the cen-
r→0 r
ter of the sphere, namely (0, 0, 0). Consequently, these
d
= lim log((x + 1)r+1 − xr+1 ) four vertices together with Qi = (−xi , −yi , −zi ) for i =
r→0 dr 1, . . . , 4 form the vertices of an inscribed cube in the
(r + 1)((x + 1)r+1 log(x + 1) − xr+1 log x) sphere. For each face of that cube, take the sum of
= lim
r→0 (x + 1)r+1 − xr+1 the vectors corresponding to the four corners of that
= (x + 1) log(x + 1) − x log x, face; this yields six vectors with integer coordinates
with form the vertices ofpan octahedron inscribed in the
where log denotes natural logarithm. It follows that sphere x2 + y2 + z2 = 4 N/3. Choose three mutually
x+1
g(x) = e(x+1) log(x+1)−x log x = (x+1)
xx . Thus perpendicular vectors from these six and let A be the
    x  matrix with these row vectors; then
g(x) x+1 1
lim = lim · lim 1 + = 1 · e = e. 16N 16N
x→∞ x x→∞ x x→∞ x AAT = I3 =⇒ det(A)2 = .
3 3
Second solution. We first write
Hence N is divisible by 3 and N/3 is a perfect square,
g(x) ((x + 1)r+1 − xr+1 )1/r as claimed.
lim = lim lim √
x→∞ x x→∞ r→0 x 2
A4 The limit exists and equals 2 π log 2.
((r + 1)x + O(xr−1 ))1/r
r
= lim lim . We first note that we can interchange x and y to obtain
x→∞ r→0 x
We would like to interchange the order of the limits, but ZZ 
1 + 2y2 1 + x2

this requires some justification. Using Taylor’s theorem I(R) = 4 2 2 4
− dx dy.
x2 +y2 ≤R2 1 + x + 6x y + y 2 + x 4 + y4
with remainder, for x ≥ 1 we can bound the error term
O(xr−1 ) in absolute value by (r + 1)r(x + 1)r−1 . This Averaging the two expressions for I(R) yields
means that if we continue to rewrite the orginial limit as
ZZ
lim lim (r + 1 + O(x1−1/r ))1/r , I(R) = ( f (x, y) − g(x, y)) dx dy
r→0 x→∞ x2 +y2 ≤R2
 2

where A5 The values of j in question are those not divisible by

either 42 or 46.
1 + x2 + y2
f (x, y) = We first check that for p prime,
1 + x4 + 6x2 y2 + y4
1 + x2 /2 + y2 /2 p−1
g(x, y) = . ∑ nj ≡ 0 (mod p) ⇔ j 6≡ 0 (mod p − 1).
2 + x4 + y4
n=1
Now note that
If j ≡ 0 (mod p − 1), then n j ≡ 1 (mod p) for each
p−1 j
f (x, y) = 2g(x + y, x − y). n, so ∑n=1 n ≡ p − 1 (mod p). If j 6≡ 0 (mod p − 1),
we can pick a primitive root m modulo p, observe that
We can thus write m j 6≡ 1 (mod p), and then note that
ZZ
p−1 p−1 p−1
I(R) = g(x, y) dx dy.
R2 ≤x2 +y2 ≤2R2 ∑ n j ≡ ∑ (mn) j = m j ∑ n j (mod p),
n=1 n=1 n=1
To compute this integral, we switch to polar coordi-
p−1 j
nates: which is only possible if ∑n=1 n ≡ 0 (mod p).
Z R√2 Z 2π We now note that the prime factorization of 2021 is 43×
I(R) = g(r cos θ , r sin θ )r dr dθ 47, so it suffices to determine when S( j) is divisible by
R 0 each of 43 and 47. We have
Z R√2 Z 2π
1 + r2 /2
= r dr dθ . 42
R 0 2 + r4 (1 − (sin2 2θ )/2) S( j) ≡ 46 ∑ n j (mod 43)
n=1
We rescale r to remove the factor of R from the limits 46
of integration: S( j) ≡ 42 ∑ n j (mod 47).
√ Z n=1
2 2π 1 + R2 r2 /2
Z
I(R) = R2 r dr dθ . Since 46 and 42 are coprime to 43 and 47, respectively,
1 0 2 + R4 r4 (1 − (sin2 2θ )/2)
we have
Since the integrand is uniformly bounded for R  0, we S( j) ≡ 0 (mod 43) ⇔ j 6≡ 0 (mod 42)
may take the limit over R through the integrals to obtain
S( j) ≡ 0 (mod 47) ⇔ j 6≡ 0 (mod 46).
Z √2 Z 2π
r2 /2 This yields the claimed result.
lim I(R) = r dr dθ
R→∞ 1 0 r4 (1 − (sin2 2θ )/2)
Z √2 Z 2π A6 Yes, it follows that P(2) is a composite integer. (Note:
dr 1 1 is neither prime nor composite.)
= dθ
1 r 0 2 − sin2 2θ Write P(x) = a0 + a1 x + · · · + an xn with ai ∈ {0, 1} and
√ Z 2π 1
= log 2 dθ an = 1. Let α be an arbitrary root of P. Since P(α) = 0,
0 1 + cos2 2θ α cannot be a positive real number. In addition, if α 6= 0
Z 2π
1 2 then
= log 2 dθ .
2 0 3 + cos 4θ
|1 + an−1 α −1 | = |an−2 α −2 + · · · + a0 α −n |
It thus remains to evaluate
≤ |α|−2 + · · · + |α|−n .
Z 2π
2 2
Z π

3 + cos 4θ
dθ = 2
3 + cos θ
dθ . If α 6= 0 and Re(α) ≥ 0, then Re(1 + an−1 α −1 ) ≥ 1 and
0 0

One option for this is to use the half-angle substitution |α|−2

1 ≤ |α|−2 + · · · + |α|−n < ;
t = tan(θ /2) to get 1 − |α|−1
√
4 2
Z ∞ Z ∞
dt = dt this yields |α| < (1 + 5)/2.
2 2 2
−∞ 3(1 + t ) + (1 − t ) −∞ 2 + t By the same token, if α 6= 0 then
√ x ∞
 
= 2 arctan √ |1 + an−1 α −1 + an−2 α −2 | ≤ |α|−3 + · · · + |α|−n .
2 −∞
√
= 2π. We deduce from this that Re(α) ≤ 3/2 as follows.
Putting this together yields the claimed result. – There is nothing to check if Re(α) ≤ 0.
 3

– If the argument of α belongs to [−π/4, π/4], then dropped square is at distance less than 1/2 from that
Re(α −1 ), Re(α −2 ) ≥ 0, so side of Sθ . To check the converse, note that there are
two ways to dissect the square Sθ into the square Sθ0 plus
|α|−3 four sin θ × cos θ rectangles. If θ 6= 0, π/4, then one of
1 ≤ |α|−3 + · · · + |α|−n < .
1 − |α|−1 these dissections has the property that each corner P of
S appears as an interior point of a side (not a corner) of
Hence |α|−1 is greater than the unique positive one of the rectangles R. It will suffice to check that if the
root of x3 + x − 1, which is greater than 2/3. center of the dropped square is in R, then the dropped
square covers P; this follows from the fact that sin θ and
– Otherwise, α has argument in (−π/2, √ π/4) ∪ cos θ are both at most 1.
(π/4, π/2), so the bound
√ |α| <√(1 + 5)/2 im-
plies that Re(α) < (1 + 5)/(2 2) < 3/2. It follows that the conditional probability, given that the
angle of rotation is chosen to be θ , that the dropped
By hypothesis, there exists a factorization P(x) = square does not cover any corners of S is (sin θ +
Q(x)R(x) into two nonconstant integer polynomials, cos θ − 1)2 . We then compute the original probability
which we may assume are monic. Q(x + 3/2) is a prod- as the integral
uct of polynomials, each of the form x − α where α is a
2
Z π/2
real root of P or of the form (sin θ + cos θ − 1)2 dθ
   π 0
3 3
x+ −α x+ −α 2
Z π/2
2 2 = (2 + sin 2θ − 2 sin θ − 2 cos θ ) dθ
   2 π 0
3 3 π/2
= x2 + 2Re
 
− α x +  − α  2 1
2 2 = 2θ − cos 2θ + 2 cos θ − 2 sin θ
π 2 0
where α is a nonreal root of P. It follows that Q(x + 2 6
= (π + 1 − 2 − 2) = 2 − .
3/2) has positive coefficients; comparing its values at π π
x = 1/2 and x = −1/2 yields Q(2) > Q(1). We can-
not have Q(1) ≤ 0, as otherwise the intermediate value B2 The answer is 2/3.
theorem would imply that Q has a real root in [1, ∞); By AM-GM, we have
hence Q(1) ≥ 1 and so Q(2) ≥ 2. Similarly R(2) ≥ 2,

1/n
so P(2) = Q(2)R(2) is composite. 2n+1 (a1 · · · an )1/n = (4a1 )(42 a2 ) · · · (4n an )
Remark. A theorem of Brillhart, Filaseta, and Odlyzko ∑nk=1 (4k ak )
from 1981 states that if a prime p is written as ∑i ai bi ≤ .
n
in any base b ≥ 2, the polynomial ∑i ai xi is irreducible.
(The case b = 10 is an older result of Cohn.) The solu- Thus
tion given above is taken from: Ram Murty, Prime num-
bers and irreducible polynomials, Amer. Math. Monthly ∑nk=1 (4k ak )
∞
2S ≤ ∑
109 (2002), 452–458). The final step is due to Pólya and n=1 4n
Szegő. ∞ n ∞ ∞
= ∑ ∑ (4k−n ak ) = ∑ ∑ (4k−n ak )
B1 The probability is 1/π. n=1 k=1 k=1 n=k
∞
Set coordinates so that the original tiling includes the 4ak 4
= ∑ =
(filled) square S = {(x, y) : 0 ≤ x, y ≤ 1}. It is then k=1 3 3
equivalent to choose the second square by first choosing
a point uniformly at random in S to be the center of the and S ≤ 2/3. Equality is achieved when ak = 43k for all
square, then choosing an angle of rotation uniformly at k, since in this case 4a1 = 42 a2 = · · · = 4n an for all n.
random from the interval [0, π/2].
B3 We prove the given statement.
For each θ ∈ [0, π/2], circumscribe a square Sθ around
S with angle of rotation θ relative to S; this square has For any circle S of radius r whose center is at distance
side length sin θ + cos θ . Inside Sθ , draw the smaller d from the origin, express the integral in polar coordi-
square Sθ0 consisting of points at distance greater than nates s, θ :
1/2 from each side of Sθ ; this square has side length ZZ Z s2 Z θ2 (s)
sin θ + cos θ − 1. ρ= (yhx − xhy )(s sin θ , s cos θ )s dθ ds.
S s1 θ1 (s)
We now verify that a unit square with angle of rotation
θ fails to cover any corners of S if and only if its center For fixed s, the integral over θ is a line integral of grad h,
lies in the interior of Sθ0 . In one direction, if one of the which evaluates to h(P2 ) − h(P1 ) where P1 , P2 are the
corners of S is covered, then that corner lies on a side of endpoints of the endpoints of the arc of the circle of ra-
Sθ which meets the dropped square, so the center of the dius s centered at the origin lying within S . If we now
 4

fix r and d and integrate S ρ over all choices of S

RR
To begin, we may take S = {i} to see that aii = 1. We
(this amounts to a single integral over an angle in the next form a (loopless) directed graph on the vertex set
range [0, 2π]), we may interchange the order of integra- {1, . . . , n} with an edge from i to j whenever ai j = 1,
tion to first integrate over θ , then over the choice of S , and claim that this graph has no cycles. To see this,
and at this pointRR we get 0 for every s. We conclude that suppose the contrary, choose a cycle of minimal length
the integral of S over all choices of S vanishes; since m ≥ 2, and let i1 , . . . , im be the vertices in order. The
the given integral varies continuously in S , by the in- minimality of the cycle implies that
termediate value theorem there must be some S where (
the given integral is 0. 1 if k − j ≡ 0 or 1 (mod m)
ai j ik =
B4 We can check directly that R3 = R4 = 1 are Virahanka– 0 otherwise.
Fibonacci numbers; henceforth we will assume m ≥ 5.
m −1 k
Denote the product ∏Fk=1 k by A. Note that if Fm is The submatrix corresponding to S = {i1 , . . . , im } has
composite, say Fm = ab for a, b > 1 integers, then A is row sum 0 and hence is singular, a contradiction.
divisible by aa bb and thus by Fm = ab; it follows that We now proceed by induction on n. Since the directed
Rm = 0 = F0 when Fm is composite. graph has no cycles, there must be some vertex which
Now suppose that Fm is prime. Since F2n = Fn (Fn+1 + is not the starting point of any edge (e.g., the endpoint
Fn−1 ) for all n, Fm is composite if m > 4 is even; thus of any path of maximal length). We may conjugate by
we must have that m is odd. Write p = Fm , and use ≡ a permutation matrix so that this vertex becomes 1. We
to denote congruence (mod p). Then we have now apply the induction hypothesis to the submatrix
p−1 p−1 p−1
corresponding to S = {2, . . . , n} to conclude.
A= ∏ (p − k) p−k ≡ ∏ (−k) p−k = (−1) p(p−1)/2 ∏ k p−k Remark. A directed graph without cycles, as in our
k=1 k=1 k=1 solution, is commonly called a DAG (directed acyclic
and consequently graph). It is a standard fact that a directed graph is a
TAG if and only if there is a linear ordering of its ver-
p−1 tices consistent with all edge directions. See for exam-
A2 ≡ (−1) p(p−1)/2 ∏ (kk k p−k ) ple https://en.wikipedia.org/wiki/Directed_
k=1
acyclic_graph.
p(p−1)/2
= (−1) ((p − 1)!) p
Remark. An n × n matrix A = (ai j ) for which the
≡ (−1) p(p+1)/2 , value of ai j depends only on i − j (mod n) is called
a circulant matrix. The circulant matrix with first row
where the final congruence follows from Wilson’s The-
(1, 1, 0, . . . , 0) is an example of an n × n matrix whose
orem. Now observe that when m is odd, p = Fm must be
determinant is even, but whose other principal minors
congruent to either 1 or 2 (mod 4): this follows from
are all odd.
inspection of the Virahanka–Fibonacci sequence mod
4, which has period 6: 1, 1, 2, 3, 1, 0, 1, 1, . . .. It follows
that A2 ≡ (−1) p(p+1)/2 = −1. B6 Let fk (x) be the probability distribution of Xk , the last
number remaining when one repeatedly trims a list of
On the other hand, by Cassini’s identity 3k random variables chosen with respect to the uniform
Fn2 = (−1)n+1 + Fn−1 Fn+1 distribution Ron [0, 1]; note that f0 (x) = 1 for x ∈ [0, 1].
Let Fk (x) = 0x fk (t) dt be the corresponding cumulative
with n = m − 1, we have Fm−1 2 ≡ (−1)m = −1. Thus distribution. Then fk (x) is the probability distribution
2 2
we have 0 ≡ A − Fm−1 ≡ (A − Fm−1 )(A − Fm−2 ). Since of the median of three random variables chosen with
p is prime, it must be the case that either A = Fm−1 or respect to the distribution fk−1 (x); therefore
A = Fm−2 , and we are done.
fk (x) = 6 fk−1 (x)Fk−1 (x)(1 − Fk−1 (x)). (1)
B5 For convenience, throughout we work with matrices
over the field of 2 elements. In this language, if there By symmetry we have Fk ( 21 ) = 12 , so (1) implies
exists a permutation matrix P such that P−1 AP is unipo-
tent (i.e., has 1s on the main diagonal and 0s below    
1 1 1 1
it), then A is very odd: any principal submatrix of A is fk = 6 fk−1 × × .
conjugate to a principal submatrix of P−1 AP, which is 2 2 2 2
again unipotent and in particular nonsingular. We will
solve the problem by showing that conversely, for any By induction on k, we deduce that fk ( 21 ) = ( 32 )k and
very odd matrix A, there exists a permutation matrix P fk (x) is nondecreasing on [0, 21 ]. (More precisely, be-
such that P−1 AP is unipotent. Since the latter condi- sides (1), the second assertion uses that Fk−1 (x) in-
tion is preserved by taking powers, this will prove the creases from 0 to 1/2 and y 7→ y − y2 is nondecreasing
desired result. on [0, 1/2].)
 5

The expected value of |Xk − 21 | equals (This can also be interpreted as an instance of the rear-
rangement inequality.)
Z 1/2  We now see that

1
µk = 2 − x fk (x) dx
0 2 Z 1/2
Z 1/2 
1
 µk ≥ 2 xgk (x) dx
=2 x fk − x dx 0
0 2  k Z (1/2)(2/3)k
3
≥2 x dx
2 0
Define the function k
1 2 (1/2)(2/3)
 k 
3
h i =2 x 
3 k 2 k 2 2 0
(
x ∈ 0, 21



gk (x) = 2 3  k  2k
1 2 k
 
0 otherwise. 3 1 2
=2 =
2 8 3 4 3
Note that for x ∈ [0, 1/2] we have as desired.
Z x Remark. For comparison, if we instead take the me-
(gk (t) − fk (1/2 − t)) dt ≥ 0 dian of a list of n numbers, the probability distribution
0 is given by

with equality at x = 0 or x = 1/2. (On the in- P2n+1 (x) = (2n + 1)!/(n!n!)xn (1 − x)n .
terval [0, (1/2)(2/3)k ] the integrand is nonnegative,
so the function increases from 0; on the interval The expected value of the absolute difference between
[(1/2)(2/3)k , 1/2] the integrand is nonpositive, so the 1/2 and the median is
function decreases to 0.) Hence by integration by parts, Z 1/2  
2n + 1
2 (1/2 − x)P2n+1 (x)dx = 2−2n−2 .
Z 1/2 0 n
µk − 2 xgk (x) dx
0 For n = 32021 , using Stirling’s approximation this can be
1/2 estimated as 1.13(0.577)2021 < 0.25(0.667)2021 . This
 
1
Z
= 2x( fk − x − gk (x)) dx
0 2 shows that the trimming procedure produces a quantity
Z 1/2 Z x Z x    that is on average further away from 1/2 than the me-
2 1
= x gk (t) − fk − t dt dt dx ≥ 0. dian.
0 0 0 2