AMC 10 · 2012 · #25
학년 7 counting벌레 한 마리가 아래 그림의 육각형 격자에서 선분들을 따라 A에서 B로 이동한다. 화살표가 표시된 선분은 화살표 방향으로만 지날 수 있으며, 벌레는 같은 선분을 두 번보다 많이 지나지 않는다. 서로 다른 경로는 몇 가지인가?
답을 골라 클릭하세요.
AMC 10 2012 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.
도구 + CCSS 풀이
이해
문제 재정리: 벌레가 기울어진 육각형 격자의 변을 따라 $A$(맨 왼쪽)에서 $B$(맨 오른쪽)까지 간다. 대각선 변은 양방향으로 지날 수 있지만, 가로 변은 화살표 방향으로만 지날 수 있는 일방통행이다. 같은 변은 두 번 지날 수 없다. $A \to B$ 경로의 개수를 구하라.
주어진 것: 그림은 점들을 대각선 변과 가로 변으로 이은 육각형 격자이다; 모든 가로 변에는 화살표가 있어 그 방향으로만 지날 수 있다; 세 개의 '역방향' 화살표만 왼쪽을 향하며, 이들은 모두 가운데 가로선 위에 있다. 나머지 화살표는 모두 오른쪽을 향한다; 대각선 변에는 화살표가 없어 양방향으로 지날 수 있다; 어떤 변도 두 번 지날 수 없다
구하는 것: $A$에서 $B$까지 가는 서로 다른 경로의 개수
이해
문제 재정리: 벌레가 기울어진 육각형 격자의 변을 따라 $A$(맨 왼쪽)에서 $B$(맨 오른쪽)까지 간다. 대각선 변은 양방향으로 지날 수 있지만, 가로 변은 화살표 방향으로만 지날 수 있는 일방통행이다. 같은 변은 두 번 지날 수 없다. $A \to B$ 경로의 개수를 구하라.
주어진 것: 그림은 점들을 대각선 변과 가로 변으로 이은 육각형 격자이다; 모든 가로 변에는 화살표가 있어 그 방향으로만 지날 수 있다; 세 개의 '역방향' 화살표만 왼쪽을 향하며, 이들은 모두 가운데 가로선 위에 있다. 나머지 화살표는 모두 오른쪽을 향한다; 대각선 변에는 화살표가 없어 양방향으로 지날 수 있다; 어떤 변도 두 번 지날 수 없다
계획
주요 도구: #2 빠짐없이 나열하기
보조 도구: #1 그림 그리기, #7 작은 문제로 쪼개기, #16 관점 바꾸기
"경로가 몇 개인가"를 묻고 있으므로 목표는 겹치거나 빠짐없이 세는 것이다(도구 #2, 빠짐없이 나열하기). 먼저 그림을 방향 그래프로 다시 그려 규칙을 기계적으로 만든다: 점은 꼭짓점, 대각선은 양방향 변, 가로 화살표는 일방통행 변이다(도구 #1, 그림 그리기). 어려움은 전부 가운데 선 위의 왼쪽 방향 역방향 화살표 세 개에 있으므로, 모든 경로를 그 역방향 화살표를 몇 개 쓰는지($0$, $1$, $2$, $3$)로 나눈다(도구 #7, 작은 문제로 쪼개기; 도구 #16, 관점 바꾸기). 그러면 각 경우는 깔끔한 순방향 세기가 되고, 네 경우를 더하면 된다.
실행 — 정답: E
5.G.A.2 단계 1 격자를 그래프로 다시 그리기
- 모든 점을 꼭짓점으로, 모든 선분을 변으로 본다.
- 대각선 선분은 화살표가 없으니 양방향 변이다.
- 가로 선분은 화살표가 있으니 일방통행 변이다.
- 화살촉을 읽으면, 가로 화살표는 모두 오른쪽($B$ 쪽)을 향하는데, 예외로 속이 빈 화살촉으로 그려진 세 개만 가운데 가로선 위에 놓여 왼쪽을 향한다.
- 이 세 개를 역방향 화살표라 부른다.
💡 복잡한 그림을 '양방향 선'과 '일방통행 선'으로 바꾸면 이동 규칙을 변 하나하나 확인할 수 있다.
7.SP.C.8 단계 2 역방향 화살표가 전부다
- 오른쪽 화살표는 모두 벌레를 앞으로 밀기 때문에, 왼쪽으로 움직일 수 있는 유일한 방법은 양방향 대각선을 쓰거나 가운데 선의 역방향 화살표 세 개 중 하나를 쓰는 것뿐이다.
- 그래서 모든 경로를 역방향 화살표를 몇 개 쓰는지로 분류한다.
- 한 경로는 $0$, $1$, $2$, $3$개를 쓰며, 이 네 무리는 서로 겹치지 않고 모든 경우를 덮는다.
- 각 무리를 따로 세고 더한다.
💡 거슬러 가는 화살표라는 껄끄러운 하나의 특징이 전부를 좌우하므로, 그것을 중심으로 세는 것이 가장 깔끔하다.
7.SP.C.8 단계 3 경우 0: 역방향 화살표를 안 씀
- 역방향 화살표 세 개를 무시한다.
- 이제 $A$에서 $B$까지 격자의 반복되는 마름모 모양 덩어리들을 훑으며, 각 점에 이르는 경우의 수를 누적으로 적어 간다: 한 점의 수는 그 점으로 들어오는 점들의 수의 합이고, 갈림길마다 선택이 곱해진다.
- 이 계산을 덩어리 사슬 전체에 걸쳐 이어 가면 역방향 화살표를 전혀 건드리지 않는 경로가 $1024$개 나온다.
💡 한 점에 이르는 경우의 수는 앞 점들의 수를 더한 것이므로, 격자를 한 번 조심스럽게 훑으면 순방향 경로가 한꺼번에 세어진다.
4.OA.A.3 단계 4 경우 1, 2, 3: 역방향 화살표를 씀
- 벌레가 역방향 화살표를 써서 가운데 선을 거슬러 올라가면, 나중에 그 구간을 다시 지날 수 없으므로 주변의 우회로가 상당 부분 고정된다.
- 강제되는 우회로를 같은 방식으로 덩어리별로 따지면 역방향 화살표를 정확히 하나 쓰는 경로가 $1024$개, 둘 쓰는 경로가 $320$개, 셋 다 쓰는 경로가 $32$개 나온다.
💡 벌레가 한 번 뒤로 가기로 하면 변을 다시 못 쓰는 규칙이 나머지 경로 대부분을 강제하므로, 각 역방향 화살표는 셀 수 있는 제한된 우회로만 더한다.
4.NBT.B.4 단계 5 네 경우를 더하기
- 네 무리는 서로 겹치지 않고 모든 경우를 덮으므로, 전체 경로 수는 그 합이다.
- 더하면 $1024 + 1024 + 320 + 32 = 2400$이다.
- 따라서 답은 $\textbf{(E)}\ 2400$이다.
💡 겹치지 않으면서 전부를 덮는 경우들은 그냥 더하면 되고, 중복도 누락도 없다.
5.G.A.2 모든 점을 꼭짓점으로, 모든 선분을 변으로 본다. 대각선 선분은 화살표가 없으니 양방향 변이다. 가로 선분은 화살표가 있으니 일방통행 변이다. 7.SP.C.8 오른쪽 화살표는 모두 벌레를 앞으로 밀기 때문에, 왼쪽으로 움직일 수 있는 유일한 방법은 양방향 대각선을 쓰거나 가운데 선의 역방향 화살표 세 7.SP.C.8 역방향 화살표 세 개를 무시한다. 이제 $A$에서 $B$까지 격자의 반복되는 마름모 모양 덩어리들을 훑으며, 각 점에 이르는 경우의 수를 누적으 4.OA.A.3 벌레가 역방향 화살표를 써서 가운데 선을 거슬러 올라가면, 나중에 그 구간을 다시 지날 수 없으므로 주변의 우회로가 상당 부분 고정된다. 강제되 4.NBT.B.4 네 무리는 서로 겹치지 않고 모든 경우를 덮으므로, 전체 경로 수는 그 합이다. 더하면 $1024 + 1024 + 320 + 32 = 2400$ 검토
합리성 확인: 네 경우는 역방향 화살표를 쓰는 개수로 나뉘어 서로 겹치지 않고($0,1,2,3$개), 모든 경로가 그중 하나에 속하므로 합을 구하는 것이 타당하다. $1024+1024+320+32$를 따로 다시 더해도 $2400$이 나와 보기 (E)와 일치한다. 또 이 값은 매끈하고 약수가 많은 수 $2400 = 2^5 \cdot 3 \cdot 5^2$로, 작은 갈림 선택 수들을 곱하고 더해 나올 법한 전형적인 모양이다. 반면 다른 보기들은 큰 소인수를 품고 있어 -- $2368 = 2^6\cdot 37$, $2384 = 2^4\cdot 149$, $2112 = 2^6\cdot 3\cdot 11$ -- 작은 선택 수의 곱에서는 거의 나오지 않고, $2304 = 2^8\cdot 3^2$는 $2400$에 못 미친다. 그래서 (E)가 계산으로도, 구조로도 가장 그럴듯하다.
대안 접근: 역방향 화살표 개수로 나누는 대신, $A$에서부터 순서대로 각 화살표에 '거기에 이르는 경우의 수'를 붙일 수도 있다: 모든 오른쪽 화살표는 자기로 들어오는 값들의 합을 물려받고, 가운데 선의 역방향 화살표는 추가 우회로를 끼워 넣는다. 이 값들을 격자를 따라 층층이 전파해 $B$의 값을 읽으면 똑같이 $2400$이 나와 경우 분류를 교차 검증한다.
사용된 CCSS 표준 (최저 학년 7)
5.G.A.2실제 문제를 좌표평면에 점으로 나타내기 (격자를 양방향 대각선 변과 일방통행 가로 화살표를 가진 꼭짓점 그래프로 다시 그리기.)7.SP.C.8정리된 목록, 표, 다이어그램으로 복합 사건의 경우의 수 세기 (역방향 화살표 개수로 경로를 나누고 격자의 각 점에 이르는 경우의 수를 누적으로 세기.)4.OA.A.3사칙연산으로 여러 단계 문제 해결하기 (역방향 화살표를 하나, 둘, 셋 쓰는 경우의 강제된 우회로 세기.)4.NBT.B.4여러 자리 수를 능숙하게 더하기 (네 경우의 수 $1024+1024+320+32=2400$을 더하기.)
⭐ 미로를 일방통행과 양방향 길로 다시 그리고, 말썽을 일으키는 뒤로 가는 화살표가 셋뿐임을 알아챈 뒤, 그것을 몇 개 쓰는지로 경로를 나눠 더한다: $1024+1024+320+32=2400$.
⭐ 미로를 일방통행과 양방향 길로 다시 그리고, 말썽을 일으키는 뒤로 가는 화살표가 셋뿐임을 알아챈 뒤, 그것을 몇 개 쓰는지로 경로를 나눠 더한다: $1024+1024+320+32=2400$.
비슷한 유형 더 풀어보기
같은 archetype · 비슷한 학년부터.
