Putnam 2021, Problem A-1

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)$?

Solution:
The answer is 578.

Each hop corresponds to adding one of the 12 vectors $(0, \pm 5)$, $(\pm 5, 0)$, $(\pm 3, \pm 4)$, $(\pm 4, \pm 3)$ to the position of the grasshopper. Since $(2021, 2021) = 288(3, 4) + 288(4, 3) + (0, 5) + (5, 0)$, the grasshopper can reach $(2021, 2021)$ in $288 + 288 + 1 + 1 = 578$ hops.

On the other hand, let $z = x + y$ denote the sum of the $x$ and $y$ coordinates of the grasshopper, so that it starts at $z = 0$ and ends at $z = 4042$. Each hop changes the sum of the $x$ and $y$ coordinates of the grasshopper by at most 7, and $4042 > 577 \times 7$; it follows immediately that the grasshopper must take more than 577 hops to get from $(0, 0)$ to $(2021, 2021)$.

**Remark.** This solution implicitly uses the distance function
$$d((x_1, y_1), (x_2, y_2)) = |x_1 - x_2| + |y_1 - y_2|$$
on the plane, variously called the taxicab metric, the Manhattan metric, or the $L^1$-norm (or $\ell_1$-norm).