2006 AMC 12B Problem 18

Question

An object in the plane moves from one lattice point to another. At each step, the object may move one unit to the right, one unit to the left, one unit up, or one unit down. If the object starts at the origin and takes a ten-step path, how many different points could be the final point?

120

121

221

230

231

Answer: B

Concepts:lattice point parity basic counting

Difficulty rating: 1820

Small hint:

After

10

steps the endpoint

(a, b)

satisfies

|a| + |b| \le 10

with

a + b

even

Big hint:

Count lattice points with even coordinate sum inside the diamond

|a| + |b| \le 10

Solution:

Each step changes the coordinate sum by

1,

so after

10

steps the endpoint

(a, b)

has

a + b

even, and

|a| + |b| \le 10.

Any such point is reachable: walk

|a| + |b|

steps to it, then use the remaining even number of steps going out and back.

The reachable points lie on the lines

a + b = 2k

for

-5 \le k \le 5.

Each such line meets the diamond in exactly

11

lattice points.

With

11

lines and

11

points each, there are

121

points.

Thus, the correct answer is B.