AMC 10 · 2010 · #18
Grade 8 countinggeometry-2dPick an answer.
Counting the good paths directly is hopeless because the ban is a condition on all 17 points of a path at once. The fix is to find one point per path that decides everything (Tool #7 Identify Subproblems). Tracking s = x+y (Tool #4) shows s climbs by exactly 1 per step, so every path meets the line x+y=0 at exactly one point M — a built-in label. Listing the possible M (Tool #2) leaves only six legal choices. The move that makes the whole plan pay off is a boundary check (Tool #14): for each legal M, the two legs are pinned into a half-plane that misses the forbidden block entirely, so no path through a legal M ever needs to be thrown away. That turns each case into a plain product of two grid-path counts, and a reflection in y=x halves the work.
Turn the square into nine banned points
The forbidden region is really nine lattice points.
The forbidden square is really just a three-by-three block of nine dots sitting in the middle of the grid.
6.EE.B.8Draw A DiagramEach step raises x+y by exactly one
Each step raises the coordinate sum by one.
The coordinate sum is a clock that ticks up by one every step, so the anti-diagonal gets crossed at one predictable moment.
Each step raises the coordinate sum by exactly one, so the diagonal is crossed at one predictable moment.
▸ Why?
Every move adds one to exactly one coordinate, so the total climbs by the same fixed step.
▸ Why?
Each path therefore meets the diagonal exactly once, so labelling paths by that point is a fair sort.
Six legal crossing points
So each path crosses the middle diagonal once.
Labelling each path by where it crosses the anti-diagonal is a fair sort: every path gets exactly one label.
5.G.A.2Make A Systematic ListA legal crossing forces a legal path
A legal crossing point makes the whole path legal.
Steps that only go right and up can never bring you back, so once a leg is on the far side of the block it stays there.
6.EE.B.8Extreme PrincipleCount the three upper-left groups
One side of the picture holds 849 paths.
A grid path is fixed the moment you say which of its steps go right, so counting paths is just counting choices.
7.SP.C.8Identify SubproblemsMirror the picture and add
Mirroring doubles it to 1698, choice (D).
The start, the finish and the forbidden block are all symmetric about y=x, so going around the block above and going around it below must come out equal.
8.G.A.3Draw A DiagramEvery step raises x+y by one, so each path meets the line x+y=0 exactly once; sort paths by that crossing point, check that a legal crossing already traps both halves away from the forbidden block, and count 2(1 + 8² + 28²) = (D) 1698.
- Turn the square into nine banned points
- Each step raises x+y by exactly one
- Six legal crossing points
- A legal crossing forces a legal path
- Count the three upper-left groups
- Mirror the picture and add