2011 AMC 12B Problem 23 AoPS Wiki hard-to-understand solution

absolute valueanalytic geometrycontest-math

As stated in the title, I am asking about this question:

A bug travels in the coordinate plane, moving only along the lines that are parallel to the $x$-axis or $y$-axis. Let $A = (-3, 2)$ and $B = (3, -2)$. Consider all possible paths of the bug from $A$ to $B$ of length at most $20$. How many points with integer coordinates lie on at least one of these paths?

The solution's first few steps with the absolute value did not have much explanation, and also it did not have a diagram, which is a necessity in a problem like this. Could somebody please post an easy to read solution with a diagram?

Best Answer

One simply needs to flesh out the argument a bit better. Moreover, the argument is not strictly complete because it only shows that if a point lies on such a path, it must satisfy the absolute value criterion, but it does not explicitly state that there exists a valid passing through a given point that satisfies the absolute value criterion.

To understand the motivation, consider an arbitrary lattice point $C = (x,y)$. We know that such a point must either belong to the set of "desired" points--i.e., there is a path from $A$ to $B$ of at length at most $20$ that passes through it--or, it does not. There clearly cannot be any points whose classification is "ambiguous/unknown."

Now if a point is in the desired set of points, the existence of a path from $A$ to $B$ through $C = (x,y)$ implies that its length is the sum of the lengths of the subpaths from $A$ to $C$ and then from $C$ to $B$. If use the notation $L(A,B)$ to denote this length, then $$20 \ge L(A,B) = L(A,C) + L(C,B) \ge 0.$$

Next, we observe that for any two lattice points $P= (x_1, y_1), Q = (x_2, y_2)$, the length of the shortest path along the lattice must be $|x_1 - x_2| + |y_1 - y_2|$. To see why, we reason that we must move a minimum distance $|x_1 - x_2|$ in the horizontal direction, and a minimum distance $|y_1 - y_2|$ in the vertical. So we deduce $$L(A,C) + L(C,B) \ge (|-3 - x| + |2 - y|) + (|x - 3| + |y - (-2)|).$$ Therefore, if $C$ is in the desired set of points, it satisfies the claimed absolute value inequality.

Conversely, it is easy to show that if $C$ satisfies the absolute value inequality, then a path exists from $A$ to $B$ through $C$ with length not more than $20$: simply choose a route that moves horizontally from $A = (-3,2)$ to $A' = (x,2)$, with length $|x+3|$, then vertically from $A' = (x,2)$ to $C = (x,y)$ with length $|y-2|$; then from $C$ to $B' = (3,y)$ with length $|3-x|$, and finally from $B'$ to $B = (3,-2)$ with length $|y+2|$, and since the sum of these lengths does not exceed $20$ (as we supposed that $C$ satisfies the absolute value inequality), this path meets the desired criteria.