Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

William Lowell

maa
...
org/putnam

PUTNAM
Mathematical Competition

Problems for
Session B

The 82nd William Lowell Putnam Mathematical Competition
2021

A1 A grasshopper starts at the origin in the coordinate plane and makes a sequence of hops
...
What is
the smallest number of hops needed for the grasshopper to reach the point (2021, 2021)?
Answer: 578
...

One way to write the total displacement as a sum of 578 of these vectors is
h2021, 2021i = 288 · h3, 4i + 288 · h4, 3i + h0, 5i + h5, 0i
...
Because this sum has to reach
2021 + 2021 = 4042 = 7 · (577) + 3 ,
at least 578 hops are needed
...


g(x)

...


Find lim

x→∞

Solution: Note that for r > −1 and any positive x, we have (x + 1)r+1 − xr+1 > 0
...

r

Applying L’Hˆ
opital’s rule, we get
(x + 1)r+1 log(x + 1) − xr+1 log x
r→0
(x + 1)r+1 − xr+1


(x + 1) log(x + 1) − x log x
= log (x + 1)x+1 x−x ,
=
(x + 1) − x

x
1
g(x) = (x + 1)x+1 x−x = (x + 1) 1 +

...


so

A3 Determine all positive integers N for which the sphere
x2 + y 2 + z 2 = N
has an inscribed regular tetrahedron whose vertices have integer coordinates
...

Solution 1: To see that the condition is sufficient, note that the four points
(−m, −m, −m), (m, m, −m), (m, −m, m), (−m, m, m)
are the vertices of a regular tetrahedron inscribed in the sphere x2 + y 2 + z 2 = 3m2
...
If T is a tetrahedron whose vertices have integer coordinates, then its volume is
of the form V (T ) = D/6 for some integer D
...
The
√ volume of a regular tetrahedron T inscribed in a sphere of radius R is given
8 3R3
by V (T ) =

...

D = 6 V (T ) =
=
9
9
√
Because D is an integer, it follows that 3N is a rational number
...


Proof of Lemma 1: Let P , Q, R, and S be the vertices of the tetrahedron
...
We can use a triple product to express



q1 q2

1 ~
1
~
~


V = |P Q · (P R × P S)| =  det r1 r2
6
6 
s1 s2

the volume as

q3 
r3  ,
s3 

and as the determinant is an integer, we are done
...
We then have
P~Q = h0, 2d, 2di,

P~R = h2d, 0, 2di,

3

P~S = h2d, 2d, 0i,

and the volume is



√

0 2d 2d 

8 3
1 ~
1 
8 3R3
~
~



=
det
V = |P Q · (P R × P S)| = 
d =

...
To show that it is necessary,
note that if
vi = (xi , yi , zi ), i = 1, 2, 3, 4
are the vertices of a regular tetrahedron inscribed in the sphere x2 + y 2 + z 2 = N , we can add
the four antipodal points
wi = (−xi , −yi , −zi ),

i = 1, 2, 3, 4

to get the eight vertices of a cube
...
) Because this cube is inscribed in the
space diagonals have length 2 N ; therefore, each edge of the cube has length 2 N/3 and its
3
p
N/3
...


4

A4 Let



ZZ
I(R) =

1 + y2
1 + 2x2
−
4
2
2
4
1 + x + 6x y + y
2 + x4 + y 4


dx dy
...


√
π 2 log 2
Answer: The limit exists and equals

...
Let
f (x, y) =

x4

1+

f (x, y) + f (y, x) =

1 + 2x2
1 + y2
−
,
2
2
4
+ 6x y + y
2 + x4 + y 4

so that

2 + 2(x2 + y 2 )
2 + x2 + y 2
−
1 + x4 + 6x2 y 2 + y 4
2 + x4 + y 4

and thus

2 + 2(x2 + y 2 )
2 + x2 + y 2
−
dx dy
...

1 + x4 + 6x2 y 2 + y 4
x2 +y 2 ≤R2

Let u = x − y and v = x + y
...

2 + u4 + v 4

ZZ
=
u2 +v 2 ≤2R2

Note that if we rename the variables in this last integral x, y instead of u, v, the integrand
will be the same as the integrand of the “second part” of the double integral for 2 I(R) above
...

2 + x4 + y 4
R2
Converting to polar coordinates, we get
Z

2π

Z

√
R 2

2 I(R) =
t=0

r=R

2 + r2
r dr dt
...
So
# Z
"Z √

2π
R 2
dr
dt
2 I(R) ∼

...

2
2 cos (2t) + sin2 (2t)

π
and is also even, so we can proceed as follows:
2
Z π/4
2 dt
2 dt
=
8
2 (2t) + sin2 (2t)
2 cos2 (2t) + sin2 (2t)
2
cos
t=0

The integrand is periodic with period
Z

2π

t=0

Z π/4
dt
=
4
cos4 t + sin4 t
t=−π/4
Z π/4
16 sec2 (2t) dt
=
2 + tan2 (2t)
t=0
Z ∞
Z ∞
8 dw
4 dw
=
=
2
2
w=0 2 + w
w=0 1 + w /2
∞
√
√
√

= 2π 2
...

R→∞
2

A5 Let A be the set of all integers n such that 1 ≤ n ≤ 2021 and gcd(n, 2021) = 1
...

n∈A

Determine all values of j such that S(j) is a multiple of 2021
...

Solution: Note that modulo 2021, the set A consists precisely of the elements of the multiplicative group
...

n∈A

m∈A

Therefore,
(xj − 1) S(j) ≡ 0 (mod 2021)
...
Let
x be a primitive root modulo 43 (that is, an integer between 1 and 42 that is a generator of
the cyclic group (Z/43 Z)∗ , which is the multiplicative group of the field with 43 elements)
...
In particular, if j is not a multiple of 42 we have
(xj − 1) S(j) ≡ 0 (mod 2021) ⇒ (xj − 1) S(j) ≡ 0 (mod 43) ⇒ S(j) ≡ 0 (mod 43)
...
So if j is not a multiple of 42 or 46, then S(j) is a multiple
of both 43 and 47, hence of 2021
...
Then nj ≡ 1 (mod 43) for all n in the sum,
and S(j) is therefore not a multiple of 43 (or of 2021), as
X
S(j) ≡
1 = 42 · 46 · 1 ≡ −3 ≡ 40 (mod 43)
...


7

A6 Let P (x) be a polynomial whose coefficients are all either 0 or 1
...
Does it follow
that P (2) is a composite integer?
Solution: Yes, we will show that P (2) must be composite
...
Then either F (2) or G(2) would be a unit, so without
loss of generality we may assume that G(2) = 1
...

Because the coefficients of P (x) are nonnegative integers, P (x) cannot have a positive real
root, so G(x) cannot have a positive real root either
...
In particular, because σN = 1 is the product of the leading coefficients
of F (x) and G(x), the polynomial G(x) must be monic
...
, rk be the (complex, not
necessarily distinct) roots of G(x), so that
G(x) =

k
Y

(x − rj )
...
Because G(x) > 0 for x > 0, we have G(1) ≥ 1 = G(2)
...


j=1

j=1

It follows that G(x) must have at least one root ρ with |ρ − 1| ≥ |ρ − 2|, which is equivalent
to Re(ρ) ≥ 23
...

First consider the case N = 2
...

ρ

> 0 and hence


 
ρ¯
1
1
= Re
= 2 Re (ρ) > 0
...
(Alternatively, one can check the four possible polynomials P (x) of
degree 2 with coefficients from {0, 1}
...

ρ
ρ
ρ

Once again, the terms on the left have nonnegative real parts
...

|ρ| 1 − 1/|ρ|
|ρ|(|ρ| − 1)
But

1
3
is a decreasing function of x for x > 1, and |ρ| ≥ Re(ρ) ≥ , so we get
x(x − 1)
2
3
1
≤ Re(ρ) ≤
≤
2
|ρ|(|ρ| − 1)

3 3
2(2

4
1
= ,
3
− 1)

a contradiction
...
There are polynomials like x7 + x2 + x + 1 = (x + 1)(x2 + 1)(x4 − x3 + 1) or
x7 + x3 + x2 + x + 1 (which is irreducible) which have roots with real part greater than 1
...
Hence one needs to take some
care with this argument
...
If another unit
square is dropped on the plane at random with position and orientation independent of the
checkerboard tiling, what is the probability that it does not cover any of the corners of the
squares of the checkerboard?
2(π − 3)

...
Let S 0 be the additional
square that is dropped at random; we may assume that the center of S 0 is at some uniformly
distributed random position in [−1, 1] × [−1, 1], and that S 0 is rotated clockwise relative to S
by some uniformly distributed angle θ
...
Given such a θ, first suppose that the
center of S 0 is at the origin (so it coincides with the center of S)
...
The upper right corner
of S at (1, 1) projects along ~u to a vector of length h1, 1i · hsin θ, cos θi = sin θ + cos θ
...
By symmetry, the allowable region for the center of S 0 is a square with side length
2(sin θ + cos θ − 1) (centered at the origin, and rotated by an angle of θ)
...

=
=
π 2
2
π
2
2

1

B2 Determine the maximum value of the sum
∞
X
n
1/n
S=
(a1 a2 · · · an )
n
2
n=1
over all sequences a1 , a2 , a3 , · · · of nonnegative real numbers satisfying
∞
X

ak = 1
...

3
4

Solution: First consider geometric sequences, which are given by ak = a1 rk−1 for all k, with
0 < r < 1
...
Thus we can calculate S as a function of r:

k=1

 √ n
∞
∞
∞
X
X
n
nr(n−1)/2
1−r X
r
1/n
√
(a
a
·
·
·
a
)
=
(1
−
r)
=
n
1 2
n
n
n
2
2
2
r
n=1
n=1
n=1
√ 


∞
X
1−r
2(1 − r)
d
1
x
r
n
√
= √ f
=
, where f (x) =
nx = x
=

...
It remains to show
(3/2)2
3
4
that this is actually the maximum value for any sequence
...
This can be written as

1/n
1/n
(4a1 ) · (42 a2 ) · · · (4n an )
1 
1/n
,
Gn = (a1 a2 · · · an )
=
= n+1 (4a1 ) · (42 a2 ) · · · (4n an )
1
2
n
4 · 4 ··· 4
2
and we can then apply the AM-GM inequality to obtain


n
1 (4a1 ) + (42 a2 ) + · · · + (4n an )
1 X k
Gn ≤ n+1
= n+1
4 ak
...

2 n=1
4n−k
k=1

This series is absolutely convergent, so we can change the order of summation to get

"
#
∞ ∞
∞ ∞
∞
∞
1 X X ak
1 X X ak
1 X 1  X
S≤
=
=
ak
...

2

k=1

1
1−

1
4

=

4
and the second factor is
3

B3 Let h(x, y) be a real-valued function that is twice continuously differentiable throughout R2 ,
and define
ρ(x, y) = yhx − xhy
...

Solution: We will prove the statement above
...
Then
∂h
= hx xθ + hy yθ = −R sin θ hx + R cos θ hy = −yhx + xhy
...

θ=0

Now let S(α) be the disc of radius r centered at (x, y) = (d cos α, d sin α) and let
ZZ
I(α) =
ρ(x, y) dA ;
S(α)

our goal is to show that I(α) = 0 for some value of α
...
Note that the disk subtends an angle 2β at the origin, where
r
β = sin−1

...
p(A short calculation using the law of cosines shows that
R± (ϕ) = d cos ϕ ± r2 − d2 sin2 ϕ , but we won’t need this formula
...

ϕ=−β

R=R− (ϕ)

Note that I(α) is a continuous (and even differentiable) function of α, because ρ(x, y) is
continuously differentiable
...
But by the mean value theorem for integrals, I(α) must assume this mean value 0 at
least once (actually, at least twice) on the interval [0, 2π], so we are done
...
be the sequence of Fibonacci numbers, with F0 = 0, F1 = 1, and
Fn = Fn−1 + Fn−2 for n ≥ 2
...
Prove that Rm is also a Fibonacci number
...


k=1

Thus, Rm is the remainder when H(Fm − 1) is divided by Fm
...

If m = 4, then Fm = 3 and H(Fm − 1) = 4 ≡ 1 (mod 3), so R4 = 1
...

If Fm is composite, then Fm = qr for some integers 1 < q ≤ r < Fm
...
If q = r, then Fm = q 2 divides q q and again, H(Fm − 1) is divisible by
Fm and Rm = 0
...

Let p = Fm , p ≥ 5 , be prime
...


The first identity shows that if Fm is prime and m > 4, m cannot be even
...

Now consider H(p − 1) modulo p
...


k=1

But (p − 1)! ≡ −1 (mod p) by Wilson’s theorem, so
H(p − 1)2 ≡

p−1
Y

(−1)k+1 ≡ (−1)p(p+1)/2 = −1

(mod p) ,

k=0

where the last step uses that p ≡ 1 (mod 4)
...
In particular, for j = m − 1 we see that, because
1 1
m is odd and Fm = p,
2
Fm−1
= Fm−2 p + (−1)m−2 ≡ −1

4

(mod p)
...
Then the remainder Rm is Fm−1 in the first case and
Fm − Fm−1 = Fm−2 in the second, so we are done
...
, n}, the |S|-by-|S| submatrix (aij )i,j∈S has odd determinant
...

Solution: First of all, because we are only interested in determinants modulo 2, we can reduce
the entries of A modulo 2 ; that is, we may assume that all entries of A are in {0, 1}
...
, n} such that, when both the rows and columns of
A are permuted by π, A becomes upper triangular with all diagonal entries 1
...

Note that if P AP −1 is upper triangular with 1’s along the diagonal, then so is
P Ak P −1 = (P AP −1 )k
...

Proof of the claim: To show the condition is sufficient, note that if A is upper triangular with
1’s on the diagonal, then any submatrix (aij )i,j∈S has that same form, so such a submatrix
has determinant 1
...

Now we show the condition is necessary
...
By taking the subsets S = {i} of {1,
...
Now consider
a two-element subset {i, j}
...
Define a relation C on {1,
...


Then we’ve seen that for i 6= j, we cannot have both i C j and j C i
...
Suppose we do have such a cycle, and take one for which k is as
small as possible
...
, ik }
...
(Any nonzero term in the determinant has to be ± a product of 1’s, and unless
the corresponding permutation is the identity it has at least one nontrivial cycle in its cycle
decomposition, which is then a cycle for C ; because k is as small as possible, this can only be
a k-cycle, which means it must involve all the elements of S, and if it weren’t the original cycle
(i1 i2 · · · ik ), it could be used together with the original cycle to construct a shorter cycle for
C
...

Because C is acyclic, we can find a permutation π of {1,
...
If we then use π to rearrange the rows and columns of A, the new matrix will
have the desired upper triangular form with 1’s on the diagonal
...
, n} in stages, starting with the elements
- in any order - that have no “predecessors” under the relation C
...
When the
list is complete, let π(i) be the ith number on the list
...

Consider generating a random number X by the following procedure: Start with a list of 32021
numbers, drawn independently and uniformly at random between 0 and 1
...
Then trim again repeatedly until just one
number remains; let X be this number
...
Show that
1
µ≥
4

 2021
2

...
Let ρn (z) be the probability density function on that interval for each of the
numbers that remain after n trims
...
Furthermore, ρn (−z) = ρn (z) for all n, as the process is now symmetric with respect
to the origin
...

2

We proceed to calculate ρn , the probability density after n trims, from ρn−1
...
This yields the recursive formula

"Z
# Z 1
z
2
ρn−1 (t) dt 
ρn−1 (t) dt
ρn (z) = 6 ρn−1 (z)
1
−2

z



Z z
z
1
1
= 6 ρn−1 (z)
+
−
ρn−1 (t) dt
ρn−1 (t) dt
2
2
0
0
"
Z z
2 #
3
ρn−1 (t) dt

...
Also by
induction, for n ≥ 1 the function ρn (z) is monotonically decreasing with respect to |z|, and in

n
particular ρn (z) ≤ ρn (0) = 32
...

0

1
2


...

2
Finally, we integrate by parts to get
Z
µ=2
0

1/2

Z
1/2

−2
zρn (z) dz = 2zS(z)
z=0

1
= −2
2
≥

1
−2
2

Z

1/2

S(z) dz

z=0

1/2

S(z) dz
z=0
Z 1/(2M )

Z

1/2

M z dz − 2
z=0

z=1/(2M )



1
1
1
1
−
−
−
2 4M
2 2M
 2021
1
1 2
=
=
,
4M
4 3

1
dz
2



=

as desired
...


8



---

Title: The 82nd William Lowell Putnam Mathematical Competition, 2021
Description: The William Lowell Putnam Mathematics Competition Is a North American math contest for college students, organized by the Mathematical Association of America (MAA). Each year on the first Saturday in December, several thousands US and Canadian students spend 6 hours (in two sittings) trying to solve 12 problems. This past papers content problems and solutions.

Buy These NotesPreview