# 2011 AMC 12B Problems/Problem 23

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

## Problem

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? $\textbf{(A)}\ 161 \qquad \textbf{(B)}\ 185 \qquad \textbf{(C)}\ 195 \qquad \textbf{(D)}\ 227 \qquad \textbf{(E)}\ 255$

## Solution

We declare a point $(x, y)$ to make up for the extra steps that the bug has to move. If the point $(x, y)$ satisfies the property that $|x - 3| + |y + 2| + |x + 3| + |y - 2| \le 20$, then it is in the desirable range because $|x - 3| + |y + 2|$ is the length of the shortest path from $(x,y)$ to $(3, -2)$ and $|x + 3| + |y - 2|$ is the length of the shortest path from $(x,y)$ to $(-3, 2)$.

If $-3\le x \le 3$, then $-7\le y \le 7$ satisfy the property. there are $15 \times 7 = 105$ lattice points here.

else let $3< x \le 8$ (and for $-8 \le x < -3$ because it is symmetrical) We set 8 as the upper bound for x because the shortest distance from $(-3, 2)$ to $(x, y)$ added to the shortest distance from $(x, y)$ to $(3, -2)$ is $|x - 3| + |y + 2| + |x + 3| + |y - 2|$. Since the minimum value for the difference between the y-coordinates is at $y = 0$, we get $2x + 4 = 16$ or $-2x + 4 = 16$. Thus, the upper and lower bounds for $x$ are $8$ and $-8$, respectively.

Now we test each value for x satisfying $3< x \le 8$ and double the result because of symmetry.

For $x = 4$, the possibles values of y are such that $|2y| \le 12$ for a total of $13$ lattice points,

for $x = 5$, the possibles values of y are such that $|2y| \le 10$ for a total of $11$ lattice points,

for $x = 6$, the possibles values of y are such that $|2y| \le 8$ for a total of $9$ lattice points,

for $x = 7$, the possibles values of y are such that $|2y| \le 6$ for a total of $7$ lattice points,

for $x = 8$, the possibles values of y are such that $|2y| \le 4$ for a total of $5$ lattice points,

Hence, there are a total of $105 + 2 ( 13 + 11 + 9 + 7 + 5) = \boxed{(C) 195}$ lattice points.

One may also obtain the result by using Pick's Theorem(how?). $i = a - \frac{b}{2} - 1$ (Suggestion)

## Solution 2

(Anyone mind making a diagram for this) Notice that the bug is basically moving from A to B (length 10) but going on a detour in the middle.

Specifically the detour would be of length 5 to some point and then going back by retracing its path (also length 5). Just to simplify things we can observe that the coordinates don't matter here and all we need to remember is that A and B are the diagonally opposite vertices of a 4 by 6 rectangle. The bug can start the "detour" from any point on or inside the rectangle. Notice that the bug can go 5 steps in the y direction, 5 steps in the x direction, or anything in between, so the points covered by possible detours from any point would look like a rhombus or square rotated 45 degrees (with centre at a point on or inside the rectangle). Drawing this out we would get an octagon.

Finding the final answer is then easy, for this solution I will slice the octagon into 4 rectangles (2 of which are squares) and 4 isosceles triangles. There are $(4+1)\cdot (6+1) = 35$ points on or inside the original triangle, $5\cdot 7$ points covered by the rectangles above and below the original one and $5\cdot 5$ points for the squares to the right and left of the original triangle. Lastly each of the four isosceles triangles cover $4+3+2+1 = 10$ points. (Notice that although the length of the detour is 5, the points on the edge of the triangles were already counted).

Adding these up, we get $3\cdot 35 + 2\cdot 25 + 4\cdot 10 = 195 => \boxed{(C)}$

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 