AMC 10 · 2011 · #23

Grade 7 countinggeometry-2d

Archetype Path Length Comparison & Shortest Path └ Sub-archetype Shortest Route in Weighted Network

lattice-pathsshortest-pathabsolute-value systematic-enumeration ↑ Prerequisites: lattice-paths

📏 Long solution 💡 4 insights

Problem

Every route runs along the axes and its total length is capped. Count the grid points any route can touch.

Pick an answer.

(A)

161

(B)

185

(C)

195

(D)

227

(E)

255

How to solve

Strategy Change Focus / Count the Complement

There are far too many paths to list, so Tool #16 (Change Focus) carries the solution: stop thinking about paths and ask one question about each point instead — what is the cheapest path from A to B that touches this point? That single number decides membership, and it must be shown to decide it both ways: a long enough budget is necessary, and it is also enough, because a path achieving the cheapest cost can actually be built. Tool #4 (Introduce a Variable) turns that cost into an inequality in x and y that splits into independent horizontal and vertical parts. Tool #14 (Extreme Principle) reads the inequality as a spending limit — how far outside the box between A and B can a point sit before the budget runs out. Tool #1 (Draw a Diagram) turns the limit into a concrete region, and Tool #2 (Make a Systematic List) counts the integer points in it column by column.

1STEP 1

Replace "on a path" with a test

Being reachable is one distance test.

P is counted ⇔ d(A,P) + d(P,B) ≤ 20

2STEP 2

Write the test in coordinates

The test writes cleanly in coordinates.

(|x+3| + |x-3|) + (|y-2| + |y+2|) ≤ 20

3STEP 3

Each part is gap plus twice the overshoot

Each part is the gap plus twice the overshoot.

6 + 2u + 4 + 2v ≤ 20 ⟺ u + v ≤ 5

4STEP 4

Sketch the allowed region

That leaves a small stepped region.

u = max(0,|x|-3), v = max(0,|y|-2), u+v ≤ 5

5STEP 5

Count the points column by column

Counting column by column is easy.

|y| ≤ 7-u ⟹ 15-2u choices of y

6STEP 6

Add the columns

The total is 195, choice (E).

7 × 15 + 2(13+11+9+7+5) = 105 + 90 = 195

Answer

195

The edges of the region behave as they should: (8,0) costs 16 + 4 = 20 and just fits, while (9,0) costs 18 + 4 = 22 and fails; (0,7) costs 6 + 14 = 20 and fits, while (0,8) costs 6 + 16 = 22 and fails. So the region really does stop at |x| ≤ 8 and |y| ≤ 7, matching the octagon. Parity is no trap either: the cost is always 10 plus an even number, so it is always even, and allowing 20 allows nothing more or less than allowing 21. Finally, the bounding box of the region holds 17 × 15 = 255 points — exactly choice (E), which is what a solver gets by letting x and y reach their extremes independently and forgetting that the straying budget is shared. The four cut corners remove 15 points each, 60 in all, and 255 - 60 = 195 agrees with the column count.

💡Key takeaway

Going straight from A to B costs 10 steps, and every unit you wander outside the box between them costs 2 extra, so 20 steps buy exactly 5 units of wandering — count the points that fit in that budget.

Replace "on a path" with a test
Write the test in coordinates
Each part is gap plus twice the overshoot
Sketch the allowed region
Count the points column by column
Add the columns