AMC 10 · 2012 · #22

학년 7 countingpattern
유형 Casework by Position / Vertex Type └ 세부 유형 Count of Type
lattice-pathssystematic-enumeration systematic-enumeration ↑ 선수 지식: systematic-enumeration
📏 중간 풀이 💡 3 개 인사이트 📊 도형
문제
어떤 변은 양방향, 어떤 변은 한 방향으로만 갈 수 있고 변을 다시 쓸 수 없다. 경로의 수를 세어라.

답을 골라 클릭하세요.

(A)
2112
(B)
2304
(C)
2368
(D)
2384
(E)
2400
풀이 과정
전략 빠짐없이 나열하기

"경로가 몇 개인가"를 묻고 있으므로 목표는 겹치거나 빠짐없이 세는 것이다(도구 #2, 빠짐없이 나열하기). 먼저 그림을 방향 그래프로 다시 그려 규칙을 기계적으로 만든다: 점은 꼭짓점, 대각선은 양방향 변, 가로 화살표는 일방통행 변이다(도구 #1, 그림 그리기). 어려움은 전부 가운데 선 위의 왼쪽 방향 역방향 화살표 세 개에 있으므로, 모든 경로를 그 역방향 화살표를 몇 개 쓰는지(0, 1, 2, 3)로 나눈다(도구 #7, 작은 문제로 쪼개기; 도구 #16, 관점 바꾸기). 그러면 각 경우는 깔끔한 순방향 세기가 되고, 네 경우를 더하면 된다.

1STEP 1

격자를 그래프로 다시 그리기

다시 그리면 어떤 변이 뒤로 가는지 보인다.

대각선 = 양방향, 가로 = 일방통행(오른쪽, 단 가운데 선 위 역방향 3개는 예외)
2STEP 2

역방향 화살표가 전부다

그 몇 개의 화살표가 전부다.

경로 수 = N₀ + N₁ + N₂ + N₃, N_k = #{역방향 화살표를 정확히 k 개 쓰는 경로}
3STEP 3

경우 0: 역방향 화살표를 안 씀

하나도 안 쓰면 경로가 1024개다.

N₀ = 1024
4STEP 4

경우 1, 2, 3: 역방향 화살표를 씀

하나, 둘, 셋을 쓰면 갈수록 적게 더해진다.

N₁ = 1024, N₂ = 320, N₃ = 32
5STEP 5

네 경우를 더하기

경우를 더하면 2400, 보기 (E).

1024 + 1024 + 320 + 32 = 2400 → (E)
정답
2400
네 경우는 역방향 화살표를 쓰는 개수로 나뉘어 서로 겹치지 않고(0,1,2,3개), 모든 경로가 그중 하나에 속하므로 합을 구하는 것이 타당하다. 1024+1024+320+32를 따로 다시 더해도 2400이 나와 보기 (E)와 일치한다. 또 이 값은 매끈하고 약수가 많은 수 2400 = 2⁵ · 3 · 5²로, 작은 갈림 선택 수들을 곱하고 더해 나올 법한 전형적인 모양이다. 반면 다른 보기들은 큰 소인수를 품고 있어 -- 2368 = 2⁶ · 37, 2384 = 2⁴ · 149, 2112 = 2⁶ · 3 · 11 -- 작은 선택 수의 곱에서는 거의 나오지 않고, 2304 = 2⁸ · 3²는 2400에 못 미친다. 그래서 (E)가 계산으로도, 구조로도 가장 그럴듯하다.
💡핵심 정리

미로를 일방통행과 양방향 길로 다시 그리고, 말썽을 일으키는 뒤로 가는 화살표가 셋뿐임을 알아챈 뒤, 그것을 몇 개 쓰는지로 경로를 나눠 더한다: 1024+1024+320+32=2400.

  • 격자를 그래프로 다시 그리기
  • 역방향 화살표가 전부다
  • 경우 0: 역방향 화살표를 안 씀
  • 경우 1, 2, 3: 역방향 화살표를 씀
  • 네 경우를 더하기

비슷한 유형 더 풀어보기

같은 archetype · 비슷한 학년부터.