AMC 10 · 2010 · #18
학년 8 countinggeometry-2d답을 골라 클릭하세요.
금지 조건이 경로 위의 17개 점 전체에 한꺼번에 걸리기 때문에 좋은 경로를 바로 세는 것은 어렵다. 해결책은 경로마다 모든 것을 결정하는 점 하나를 찾는 것이다(도구 #7 작은 문제로 쪼개기). s = x+y를 추적하면(도구 #4) s가 한 단계에 정확히 1씩 오르므로, 모든 경로가 직선 x+y=0과 정확히 한 점 M에서 만난다 — 자동으로 붙는 이름표다. 가능한 M을 나열하면(도구 #2) 허용되는 것은 여섯 개뿐이다. 이 계획을 실제로 값어치 있게 만드는 결정적 단계는 경계 확인이다(도구 #14). 허용되는 M 각각에 대해 두 구간이 금지 블록을 완전히 비껴가는 반평면에 갇히므로, 허용되는 M을 지나는 경로는 하나도 버릴 필요가 없다. 그러면 각 경우가 격자 경로 수 두 개의 단순한 곱이 되고, y=x에 대한 대칭이 계산량을 절반으로 줄여 준다.
정사각형을 금지된 아홉 점으로 바꾸기
금지 구역은 사실 격자점 아홉 개다.
금지된 정사각형은 사실 격자 한가운데 놓인 3 × 3 짜리 점 아홉 개 덩어리일 뿐이다.
6.EE.B.8Draw A Diagram한 단계마다 x+y가 정확히 1 오른다
각 걸음이 좌표 합을 하나 올린다.
좌표의 합은 한 걸음에 한 칸씩 째깍이는 시계라서, 반대각선을 건너는 순간이 미리 정해져 있다.
한 걸음마다 좌표의 합이 정확히 1씩 오르므로, 대각선은 예측 가능한 한 순간에 지나게 된다.
▸ 왜?
모든 이동은 정확히 한 좌표에 1을 더하므로, 합이 같은 간격으로 오른다.
▸ 왜?
따라서 각 길은 대각선을 정확히 한 번 만나므로, 그 점으로 길을 분류하는 것은 공정하다.
허용되는 여섯 개의 교차점
따라서 각 경로는 가운데 대각선을 한 번 지난다.
반대각선을 어디서 건너는지로 이름표를 붙이면, 경로마다 이름표가 정확히 하나씩 돌아간다.
5.G.A.2Make A Systematic List허용되는 교차점이 경로 전체를 보증한다
허용되는 교차점이 경로 전체를 허용되게 만든다.
오른쪽과 위로만 가는 걸음은 되돌아올 수 없으니, 한 번 블록 바깥쪽으로 나간 구간은 계속 바깥에 머문다.
6.EE.B.8Extreme Principle왼쪽 위 세 무리 세기
그림의 한쪽에 경로가 849개다.
격자 경로는 어느 걸음을 오른쪽으로 쓸지 말하는 순간 정해지므로, 경로를 세는 일은 곧 선택을 세는 일이다.
7.SP.C.8Identify Subproblems그림을 뒤집어 합치기
뒤집어 두 배 하면 1698, 보기 (D).
출발점과 도착점, 금지 블록이 모두 y=x에 대해 대칭이므로 블록의 위로 도는 길과 아래로 도는 길의 수는 같을 수밖에 없다.
8.G.A.3Draw A Diagram한 걸음마다 x+y가 1씩 오르므로 모든 경로는 직선 x+y=0과 정확히 한 번 만난다. 그 교차점으로 경로를 분류하고, 허용되는 교차점이 이미 양쪽 구간을 금지 블록에서 떼어 놓는다는 것을 확인한 뒤 2(1 + 8² + 28²) = (D) 1698을 센다.
- 정사각형을 금지된 아홉 점으로 바꾸기
- 한 단계마다 x+y가 정확히 1 오른다
- 허용되는 여섯 개의 교차점
- 허용되는 교차점이 경로 전체를 보증한다
- 왼쪽 위 세 무리 세기
- 그림을 뒤집어 합치기