A dot starts at $(20,19)$. It can move one unit vertically or horizontally to one of the points $(21,19),(19,19),(20,20)$, or $(20,18)$. From there it can move two units in either direction that is perpendicular to the first move. All moves thereafter increase in length by one unit (three units, four units, five units, etc.) and must be perpendicular to the direction of the previous move. The dot stops after ten moves. Which of the following final locations is not possible?
(A) $(27,33)$
(B) $(30,40)$
(C) $(21,21)$
(D) $(42,44)$
(E) $(37,37)$
Solution 1

The ten moves have lengths 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 .

If the first move is vertical, then the five vertical moves have lengths $1,3,5,7,9$ and the five horizontal moves have lengths $2,4,6,8,10$.

If the first move is horizontal, then the five horizontal moves have lengths $1,3,5,7,9$ and the five vertical moves have lengths $2,4,6,8,10$.

If a horizontal move is to the right, then the length of the move is added to the $x$-coordinate. If a horizontal move is to the left, then the length of the move is subtracted from the $x$ coordinate.

If a vertical move is up, then the length of the move is added to the $y$-coordinate.

If a vertical move is down, then the length of the move is subtracted from the $y$-coordinate.

Therefore, once the ten moves have been made, the change in one of the coordinates is a combination of adding and subtracting 1,3,5, 7, 9 and the change in the other coordinate is a combination of adding and subtracting $2,4,6,8,10$.

For example, if the dot moves right 1 , down 2 , right 3 , up 4 , right 5 , down 6 , right 7 , up 8 , left 9 , and up 10 , then its final $x$-coordinate is

$$
20+1+3+5+7-9=27
$$

and its final $y$-coordinate is

$$
19-2+4-6+8+10=33
$$

making its final location $(27,33)$, which is choice (A). This means that choice (A) is not the answer.

We note that, in the direction with the moves of even length, the final change in coordinate
will be even, since whenever we add and subtract even integers, we obtain an even integer. In the other direction, the final change in coordinate will be odd, since adding or subtracting an odd number of odd integers results in an odd integer. (Since odd plus odd is even and odd minus odd is even, then after two moves of odd length, the change to date is even, and after four moves of odd length, the change to date is still even, which means that the final change after the fifth move of odd length is completed must be odd, since even plus or minus odd is odd.)

In the table below, these observations allow us to determine in which direction to put the moves of odd length and in which direction to put the moves of even length.

| Choice | Change in $x$ | Change in $y$ | Horizontal moves | Vertical moves |
| :---: | :---: | :---: | :---: | :---: |
| (A) $(27,33)$ | 7 | 14 | $1+3+5+7-9=7$ | $-2+4-6+8+10=14$ |
| (B) $(30,40)$ | 10 | 21 | $2-4-6+8+10=10$ |  |
| (C) $(21,21)$ | 1 | 2 | $1-3+5+7-9=1$ | $2+4-6-8+10=2$ |
| (D) $(42,44)$ | 22 | 25 | $2-4+6+8+10=22$ | $1+3+5+7+9=25$ |
| (E) $(37,37)$ | 17 | 18 | $-1-3+5+7+9=17$ | $2+4-6+8+10=18$ |

Since each of the locations (A), (C), (D), and (E) is possible, then the location that is not possible must be (B).

We note that in the case of $(\mathrm{B})$, it is the change in the $y$-coordinate that is not possible to make.

In other words, we cannot obtain a total of 21 by adding and subtracting 1, 3, 5, 7, 9 . Can you see why?

## Solution 2

Let $a$ be the horizontal change from the initial to the final position of the point and let $b$ be the vertical change from the initial to the final position.

For example, if $a=-5$ and $b=6$, the point's final position is 5 units to the left and 6 units up from its original position of $(20,19)$.

Notice that if $(x, y)$ is the final position of the point, then $a$ and $b$ can be calculated as $a+20=x$ or $a=x-20$ and $b+19=y$ or $b=y-19$.

First, assume the initial move is in the horizontal direction.

This means the second move will be in the vertical direction, the third will be horizontal, and so on.

In all, the first, third, fifth, seventh, and ninth moves will be horizontal and the others will be vertical.

Also, the first move is by one unit, the second is by two units, the third is by three units, and so on, so the horizontal moves are by $1,3,5,7$, and 9 units.

Each of these moves is either to the left or the right.

If all of the horizontal moves are to the right, then $a=1+3+5+7+9=25$.

If the point moves, left on the first move, right on the third, then left on the fifth, seventh, and ninth moves, $a$ will be $-1+3-5-7-9=-19$.

In this case, the final position is 19 units to the left of the initial position (and has potentially moved up or down, as well).

In each of the five horizontal moves, the point either moves to the left or to the right.

This means there are two choices (left or right) for each of the five horizontal moves, so there are $2 \times 2 \times 2 \times 2 \times 2=32$ possible configurations similar to the examples above.

Going through these carefully, the table below computes all possible values of $a$ :

| $1+3+5+7+9$ | $=$ | 25 | $1+3+5+7-9$ | $=$ | 7 |
| ---: | :---: | ---: | ---: | ---: | ---: |
| $-1+3+5+7+9$ | $=$ | 23 | $-1+3+5+7-9$ | $=$ | 5 |
| $1-3+5+7+9$ | $=$ | 9 | $1-3+5+7-9$ | $=$ | 1 |
| $-1-3+5+7+9$ | $=$ | 17 | $-1-3+5+7-9$ | $=$ | -1 |
| $1+3-5+7+9$ | $=$ | 15 | $1+3-5+7-9$ | $=$ | -3 |
| $-1+3-5+7+9$ | $=$ | 13 | $-1+3-5+7-9$ | $=$ | -5 |
| $1-3-5+7+9$ | $=$ | 9 | $1-3-5+7-9$ | $=$ | -9 |
| $-1-3-5+7+9$ | $=$ | 7 | $-1-3-5+7-9$ | $=$ | -11 |
| $1+3+5-7+9$ | $=$ | 1 | $1+3+5-7-9$ | $=$ | -8 |
| $-1+3+5-7+9$ | $=$ | 9 | $-1+3+5-7-9$ | $=$ | -9 |
| $1-3+5-7+9$ | $=$ | 5 | $1-3+5-7-9$ | $=$ | -13 |
| $-1-3+5-7+9$ | $=$ | 3 | $-1-3+5-7-9$ | $=$ | -15 |
| $1+3-5-7+9$ | $=$ | 1 | $1+3-5-7-9$ | $=$ | -17 |
| $-1+3-5-7+9$ | $=$ | -1 | $-1+3-5-7-9$ | $=$ | -19 |
| $1-3-5-7+9$ | $=$ | -5 | $1-3-5-7-9$ | $=$ | -23 |
| $-1-3-5-7+9$ | $=$ | -7 | $-1-3-5-7-9$ | $=$ | -25 |

Some numbers appear more than once, but after inspecting the list, we see that when the first move is in the horizontal direction, $a$ can be any odd number between -25 and 25 inclusive except for -21 and 21 .

When the first move is horizontal, the second, fourth, sixth, eighth, and tenth moves will be vertical and have lengths $2,4,6,8$, and 10 units.

Using the same idea as the previous case, all 32 possible values of $b$ when the first move is horizontal are calculated as follows:

$$
\begin{aligned}
& 2+4+6+8+10=30 \quad 2+4+6+8-10=10 \\
& -2+4+6+8+10=26 \quad-2+4+6+8-10=6 \\
& 2-4+6+8+10=22 \quad 2-4+6+8-10=2 \\
& -2-4+6+8+10=18 \quad-2-4+6+8-10=-2 \\
& 2+4-6+8+10=18 \quad 2+4-6+8-10=-2 \\
& -2+4-6+8+10=14 \quad-2+4-6+8-10=-6 \\
& 2-4-6+8+10=10 \quad 2-4-6+8-10=-10 \\
& -2-4-6+8+10=6 \quad-2-4-6+8-10=-14 \\
& 2+4+6-8+10=14 \quad 2+4+6-8-10=-6 \\
& -2+4+6-8+10=10 \quad-2+4+6-8-10=-10 \\
& 2-4+6-8+10=6 \quad 2-4+6-8-10=-14 \\
& -2-4+6-8+10=2 \quad-2-4+6-8-10=-18 \\
& 2+4-6-8+10=2 \quad 2+4-6-8-10=-18 \\
& -2+4-6-8+10=-2 \quad-2+4-6-8-10=-22 \\
& 2-4-6-8+10=-6 \quad 2-4-6-8-10=-26 \\
& -2-4-6-8+10=-10 \quad-2-4-6-8-10=-30
\end{aligned}
$$

Again, some numbers appear more than once, but examination of the table shows that when the first move is horizontal, the possible values of $b$ are the even numbers between -30 and 30 inclusive which are not multiples of 4.

We now begin to inspect the possible answers. The point in (A) is $(27,33)$.

In this case, we have that $a=27-20=7$ and $b=33-19=14$.

These values for $a$ and $b$ fit the descriptions above, so $(27,33)$ is a possible final position.

The point $(21,21)$ in $(\mathrm{C})$ has $a=1$ and $b=2$, which means $(21,21)$ is also a possible final position for the point.

The point $(37,37)$ in (E) has $a=17$ and $b=18$, so this point is also a possible final position.

We have shown that the answer must be either (B) or (D).

Note that in both cases we have that $a$ is even and $b$ is odd, which means that if either of these points is a possible final position, the first move cannot have been horizontal, which means it must have been vertical.

If the first move is vertical, then the third, fifth, seventh, and ninth moves are also vertical, and the other moves are horizontal.

Going through similar analysis as before, we will see that the restrictions on $a$ and $b$ have switched.

That is, $a$ must be an even number between -30 and 30 inclusive which is not a multiple of 4 , and $b$ must be an odd number between -25 and 25 inclusive other than -21 and 21 .

The point $(42,44)$ in (D) has $a=22$ and $b=25$, which is possible with a vertical first move. However, the point $(30,40)$ in (B) has $a=10$ and $b=21$.

Since 21 is not a possible value for $b$, then $(30,40)$ is not a possible final position.