AMC 10 · 2011 · #23

학년 7 countinggeometry-2d
lattice-pathsshortest-pathabsolute-value systematic-enumeration ↑ 선수 지식: lattice-paths
📏 긴 풀이 💡 4 개 인사이트
문제
모든 경로가 축에 나란히 가고 전체 길이에 상한이 있다. 어떤 경로든 닿을 수 있는 격자점의 수를 세어라.

답을 골라 클릭하세요.

(A)
161
(B)
185
(C)
195
(D)
227
(E)
255
풀이 과정
전략 관점 바꾸기

경로는 나열하기엔 너무 많으므로 Tool #16 (관점 바꾸기)이 풀이를 떠받친다: 경로를 생각하기를 그만두고, 대신 각 점마다 하나의 질문을 던진다 — 이 점을 지나면서 A 에서 B 로 가는 가장 싼 경로의 길이는 얼마인가? 이 한 숫자가 그 점의 포함 여부를 결정하며, 결정한다는 것을 양방향으로 보여야 한다: 충분한 예산이 필요조건이고, 가장 싼 값을 실제로 달성하는 경로를 만들 수 있으므로 충분조건이기도 하다. Tool #4 (변수 도입하기)로 그 비용을 x 와 y 에 대한 부등식으로 바꾸면 가로 부분과 세로 부분으로 분리된다. Tool #14 (극단의 원리)는 그 부등식을 지출 한도로 읽는다 — 예산이 바닥나기 전에 점이 A 와 B 사이 상자 밖으로 얼마나 멀리 나갈 수 있는가. Tool #1 (그림 그리기)로 그 한도를 구체적인 영역으로 바꾸고, Tool #2 (빠짐없이 나열하기)로 그 안의 정수 점을 세로줄 단위로 센다.

1STEP 1

"경로 위에 있다"를 판정식으로 바꾸기

도달 가능성은 하나의 거리 판정이다.

P 가 세어짐 ⇔ d(A,P) + d(P,B) ≤ 20
2STEP 2

판정식을 좌표로 쓰기

그 판정은 좌표로 깔끔하게 쓰인다.

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

각 부분은 간격 더하기 초과분의 두 배

각 부분은 간격에 초과분의 두 배를 더한 것이다.

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

허용되는 영역 그려 보기

그러면 작은 계단 모양 영역이 남는다.

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

세로줄마다 점 세기

세로줄마다 세는 것은 쉽다.

|y| ≤ 7-u ⟹ y 의 선택지 15-2u 개
6STEP 6

세로줄 더하기

합계는 195, 보기 (E).

7 × 15 + 2(13+11+9+7+5) = 105 + 90 = 195
정답
195
영역의 가장자리가 예상대로 움직인다: (8,0)은 16 + 4 = 20으로 딱 들어맞고 (9,0)은 18 + 4 = 22로 탈락한다; (0,7)은 6 + 14 = 20으로 들어맞고 (0,8)은 6 + 16 = 22로 탈락한다. 그러므로 영역은 실제로 |x| ≤ 8, |y| ≤ 7 에서 멈추며 팔각형과 일치한다. 홀짝도 함정이 아니다: 비용은 언제나 10 더하기 짝수이므로 항상 짝수이고, 20까지 허용하는 것은 21까지 허용하는 것과 정확히 같다. 마지막으로 이 영역의 바깥 직사각형은 17 × 15 = 255 개의 점을 담는데, 이것이 바로 선택지 (E) 다: 벗어날 예산을 나눠 써야 한다는 사실을 잊고 x 와 y 가 각자 극단까지 간다고 두면 나오는 값이다. 잘라낸 네 모서리가 각각 15 개씩, 모두 60 개를 덜어내므로 255 - 60 = 195로 세로줄 계산과 일치한다.
💡핵심 정리

A 에서 B 로 곧장 가면 10 걸음이 들고 그 사이 상자 밖으로 한 칸 벗어날 때마다 2 걸음이 더 드니, 20 걸음으로는 딱 5 칸만큼 벗어날 수 있다 — 그 예산 안에 들어오는 점을 세면 된다.

  • "경로 위에 있다"를 판정식으로 바꾸기
  • 판정식을 좌표로 쓰기
  • 각 부분은 간격 더하기 초과분의 두 배
  • 허용되는 영역 그려 보기
  • 세로줄마다 점 세기
  • 세로줄 더하기