Putnam (2021)

Problem A1

A grasshopper starts at the origin in the coordinate plane and makes a sequence of hops. Each hop has length $5$, and after each hop the grasshopper is at a point whose coordinates are both integers; thus, there are $12$ possible locations for the grasshopper after the first hop. What is the smallest number of hops needed for the grasshopper to reach the point $(2021, 2021)$?

Problem A2

For every positive real number $x$, let $\displaystyle{ g(x) = \lim_{r \to \infty} \left( (x + 1)^{r + 1} - x^{r + 1} \right)^\frac{1}{r} }$.

Find $\displaystyle{ \lim_{x \to \infty} \frac{g(x)}{x} }$.

Problem A3

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

Problem A4

Let

$$I(R) = \iint_{x^2 + y^2 \le R^2} \left( \frac{1 + 2 x^2} {1 + x^4 + 6 x^2 y^2 + y^4} - \frac{1 + y^2} {2 + x^4 + y^4} \right) dx \ dy$$

Find $\displaystyle{ \lim_{R \to \infty} I(R) }$, or show that this limit does not exist.

Problem A5

Let $A$ be the set of all integers $n$ such that $1 \le n \le 2021$ and $\gcd(n, 2021) = 1$. For every nonnegative integer $j$, let $S(j) = \sum_{n \in A} n^j$. Determine all values of $j$ such that $S(j)$ is a multiple of $2021$.

Problem A6

Let $P(x)$ be a polynomial whose coefficients are all either $0$ or $1$. Suppose that $P(x)$ can be written as a product of two nonconstant polynomials with integer coefficients. Does it follow that $P(2)$ is a composite integer?

Problem B1

Suppose that the plane is tiled with an infinite checkerboard of unit squares. 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?

Problem B2

Determine the maximum value of the sum $\displaystyle{ S = \sum_{n=1}^\infty \frac{n}{2^n} \left( a_1 a_2 \cdots a_n \right)^{1/n} }$ over all sequences $a_1, a_2, a_3, \dots$ of nonnegative real numbers satisfying $\displaystyle{\sum_{k = 1}^\infty a_k = 1}$.

Problem B3

Let $h(x, y)$ be a real-valued function that is twice continuously differentiable throughout $\mathbb{R}^2$, and define $\rho(x, y) = y h_x −x h_y$.

Prove or disprove: For any positive constants $d$ and $r$ with $d > r$, there is a circle $S$ of radius $r$ whose center is a distance $d$ away from the origin such that the integral of $\rho$ over the interior of $S$ is zero.

Problem B4

Let $F_0, F_1, \dots$ be the sequence of Fibonacci numbers, with $F_0 = 0, F_1 = 1,$ and $F_n = F_{n−1} + F_{n−2}$ for $n \ge 2$.

For $m > 2$, let $R_m$ be the remainder when the product $\displaystyle{\prod_{k = 1}^{F_m - 1} k^k}$ is divided by $F_m$. Prove that $R_m$ is also a Fibonacci number.

Problem B5

Say that an $n$-by-$n$ matrix $A = (a_{ij})_{1 \le i, j \le n}$ with integer entries is very odd if, for every nonempty subset $S$ of ${1, 2, \dots, n }$, the $|S|$-by-$|S|$ submatrix $(a_{i j})_{i, j \in S}$ has odd determinant. Prove that if $A$ is very odd, then $A^k$ is very odd for every $k \ge 1$.

Problem B6

Given an ordered list of $3N$ real numbers, we can trim it to form a list of $N$ numbers as follows: We divide the list into $N$ groups of $3$ consecutive numbers, and within each group, discard the highest and lowest numbers, keeping only the median.

Consider generating a random number $X$ by the following procedure: Start with a list of $3^{2021}$ numbers, drawn independently and uniformly at random between $0$ and $1$. Then trim this list as defined above, leaving a list of $3^{2020}$ numbers. Then trim again repeatedly until just one number remains; let $X$ be this number. Let $\mu$ be the expected value of $\left| X − \dfrac{1}{2} \right|$. Show that $\displaystyle{ \mu \ge \frac{1}{4} \left( \frac{2}{3} \right)^{2021} }$.