AMC 10 · 2019 · #10

쉬운 모드 학년 5

문제

아래 지도에는 점으로 그린 도시 $12$ 개가 $3$ 줄로, 한 줄에 $4$ 개씩 있어요. 각 점은 바로 옆에 있는 점들과 왼쪽, 오른쪽, 위, 아래로 도로가 이어져 있습니다. 도로는 모두 $17$ 개입니다. 왼쪽 맨 위의 점이 도시 $A$ 이고, 오른쪽 맨 아래의 점이 도시 $L$ 입니다.

Paula 는 $A$ 에서 출발해 $L$ 까지 갑니다. 도로를 정확히 $13$ 개 지나야 해요. 어떤 도로도 그 일부조차 두 번 지날 수 없지만, 같은 도시는 여러 번 지나가도 됩니다.

Paula 가 갈 수 있는 서로 다른 경로는 몇 가지일까요?

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 지도에 도시 $12$ 개가 $3$ 행 $4$ 열의 점 격자로 놓여 있고, 바로 옆에 있는 점끼리 (좌우, 상하) 길 $17$ 개로 이어져 있습니다. 도시 $A$ 는 왼쪽 위 점, 도시 $L$ 은 오른쪽 아래 점입니다. Paula 는 $A$ 에서 출발해 $L$ 에서 끝나며, 길 중 정확히 $13$ 개를 지나는데, 어떤 길도 (일부라도) 두 번 지나지 않습니다. 같은 도시는 여러 번 지나가도 됩니다. 서로 다른 경로가 몇 가지인지 세세요.

주어진 것: $3$ 행 $4$ 열 격자에 놓인 도시 $12$ 개, 이를 잇는 길 $17$ 개 (가로 $9$ 개, 세로 $8$ 개); 경로는 $A$ (왼쪽 위 점) 에서 시작해 $L$ (오른쪽 아래 점) 에서 끝남; 정확히 $13$ 개의 길을 지나므로 정확히 $17 - 13 = 4$ 개의 길은 사용하지 않음; 어떤 길도 일부라도 두 번 지날 수 없음. 단, 도시는 여러 번 방문 가능; 선택지: (A) $0$, (B) $1$, (C) $2$, (D) $3$, (E) $4$

구하는 것: $A$ 에서 $L$ 까지 길 $13$ 개를 지나는 서로 다른 경로의 개수

이해

계획

주요 도구: #14 극단의 원리

보조 도구: #1 그림 그리기, #3 가능성 지우기, #2 빠짐없이 나열하기

도구 #14 (극단의 원리)가 핵심: 각 도시를 최대 몇 번까지 지날 수 있는지 구해 모두 더한 뒤, 길 $13$ 개가 요구하는 머무름 횟수와 비교합니다. 두 값이 정확히 같아 여유가 전혀 없고, 따라서 모든 도시가 최대 횟수로 쓰여야 합니다. 도구 #1 (그림)은 그 최대 횟수의 근거가 되는 좌표와 길 개수를 마련합니다. 도구 #3 (가능성 지우기)로 잘못된 첫 이동을 제거하고 사용하지 않는 길 네 개를 확정합니다. 도구 #2 (나열하기)로 마지막에 남은 자유로운 선택만 셉니다.

실행 — 정답: E

#1 그림 그리기 5.G.A.1 단계 1

지도에 좌표 붙이기

각 도시를 $(x,y)$로 부릅니다.
$x = 0,1,2,3$은 왼쪽에서 오른쪽, $y = 0,1,2$는 아래에서 위 방향입니다.
그러면 $A = (0,2)$, $L = (3,0)$.
두 도시는 한 좌표만 $1$ 만큼 다르고 나머지 좌표가 같을 때 정확히 길로 이어지므로, 가로 길은 $3 \cdot 3 = 9$ 개, 세로 길은 $4 \cdot 2 = 8$ 개입니다.
합이 $17$로 문제와 일치합니다.

$$9 + 8 = 17$$

💡 좌표를 붙이면 모든 도시에 이름이 생겨 "저 옆 도시" 가 더 이상 애매하지 않음.

#1 그림 그리기 4.G.A.1 단계 2

도시마다 길 개수 세기

각 도시에 모이는 길의 개수를 셉니다.
네 모서리 $A = (0,2)$, $(3,2)$, $(0,0)$, $L = (3,0)$은 각각 $2$ 개.
모서리가 아닌 테두리 도시 여섯 곳 — $(1,2)$, $(2,2)$, $(1,0)$, $(2,0)$, $(0,1)$, $(3,1)$ — 은 각각 $3$ 개.
가운데 두 도시 $(1,1)$, $(2,1)$은 각각 $4$ 개.
검산: 모든 길은 양쪽 끝에서 한 번씩 세어지므로 총합은 $17$의 두 배가 되어야 합니다.

$$4 \cdot 2 + 6 \cdot 3 + 2 \cdot 4 = 8 + 18 + 8 = 34 = 2 \cdot 17$$

💡 길 개수를 모두 더하면 각 길이 두 번 세어지므로 빠뜨린 길이 없는지 공짜로 확인됨.

#14 극단의 원리 4.NBT.B.6 단계 3

한 도시는 몇 번까지 쓸 수 있나

어떤 도시를 지나가면 그곳의 길 두 개 (들어오기, 나가기)를 소모하고, 같은 길은 다시 쓸 수 없습니다.
그러므로 길이 $d$ 개인 도시는 최대 $\left\lfloor \frac{d}{2} \right\rfloor$ 번 지날 수 있습니다: $d = 2$ 면 $1$ 번, $d = 3$이면 $1$ 번 (세 번째 길은 남아 버려짐), $d = 4$ 면 $2$ 번.
양 끝점은 다릅니다.
$A$ 를 떠날 때 길 $1$ 개를 쓰고, 다시 $A$ 로 돌아왔다가 또 떠나려면 $2$ 개가 더 필요해 총 $3$ 개인데, $A$ 에는 길이 $2$ 개뿐입니다.
따라서 $A$ 는 정확히 한 번, 같은 계산으로 $L$ 도 정확히 한 번 쓰입니다.

$$\left\lfloor \frac{2}{2} \right\rfloor = 1, \quad \left\lfloor \frac{3}{2} \right\rfloor = 1, \quad \left\lfloor \frac{4}{2} \right\rfloor = 2$$

💡 도시의 길은 들어오기·나가기 짝으로 소모되므로, 길 개수가 홀수면 항상 하나가 남아 버려짐.

#14 극단의 원리 4.OA.A.3 단계 4

예산이 정확히 꽉 참

길 $13$ 개를 지나면 도시에 $14$ 번 머뭅니다 (재방문도 별개로 셈).
그중 하나는 $A$, 하나는 $L$ 이므로 나머지 $12$ 번이 다른 도시 $10$ 곳에 배분됩니다.
앞 단계의 한계를 모두 더하면 $2 \cdot 1 + 6 \cdot 1 + 2 \cdot 2 = 12$ — 필요한 $12$와 정확히 같습니다.
여유가 없으므로 그 도시들은 모두 최대 횟수로 쓰여야 합니다: $(1,1)$과 $(2,1)$은 각각 두 번 지나며 길 $4$ 개를 모두 사용하고, 모서리 $(0,0)$과 $(3,2)$는 각각 한 번 지나며 두 길을 모두 사용하고, 길이 $3$ 개인 여섯 도시는 각각 한 번 지나며 정확히 한 길을 사용하지 않습니다.

$$14 - 2 = 12 = 2 \cdot 1 + 6 \cdot 1 + 2 \cdot 2$$

💡 할 수 있는 최대치와 해야 하는 최소치가 같아지면 모든 선택이 이미 정해짐.

#3 가능성 지우기 2.OA.C.3 단계 5

사용하지 않는 길 네 개의 위치

사용하지 않는 길 끝을 셉니다.
$A$ 는 길 $2$ 개 중 $1$ 개를, $L$ 도 $1$ 개를, 길이 $3$ 개인 여섯 도시도 각각 $1$ 개를 쓰지 않으므로 총 $8$ 개의 길 끝이 버려집니다.
반대로 세면 사용하지 않는 길은 $17 - 13 = 4$ 개이고 각각 끝이 $2$ 개이니 $4 \cdot 2 = 8$.
두 수가 정확히 맞으므로, 사용하지 않는 길은 반드시 그 여덟 도시 중 두 곳을 잇습니다.
특히 $(0,0)$, $(3,2)$, $(1,1)$, $(2,1)$에 닿는 길은 하나도 버릴 수 없습니다.

$$1 + 1 + 6 = 8 = 2 \cdot (17 - 13)$$

💡 같은 것을 도시 기준과 길 기준 두 방식으로 세면 엉뚱한 곳에 버려진 길이 낄 자리가 없음.

#3 가능성 지우기 4.G.A.1 단계 6

$A$ 에서 아래로 출발할 수 없음

첫 길이 $A \to (0,1)$ 이라고 해 봅시다.
도시 $(0,1)$은 길이 $3$ 개이고 한 번만 지나므로 정확히 $2$ 개만 씁니다: $A$ 에서 온 길과 하나 더.
그런데 모서리 $(0,0)$은 자기 길 두 개를 모두 써야 하므로 $(0,1)\!-\!(0,0)$이 강제되고, 가운데 도시 $(1,1)$은 길 네 개를 모두 써야 하므로 $(0,1)\!-\!(1,1)$도 강제됩니다.
그러면 $(0,1)$ 에서 길 $3$ 개를 쓰게 되어 하나 초과입니다.
따라서 첫 길은 $A \to (1,2)$이고, $A\!-\!(0,1)$이 버려지는 네 길 중 하나입니다.

$$2 \ne 3$$

💡 한 번만 들어갈 수 있는 도시는 세 가지 요구를 동시에 들어줄 수 없음.

#3 가능성 지우기 4.G.A.1 단계 7

나머지 길이 모두 결정됨

지도를 $180^\circ$ 돌리면 $A$ 와 $L$ 이 바뀌고 길 모양은 그대로이므로, 반대쪽 끝에서 같은 논증이 $(3,1)\!-\!L$ 을 버리게 하고 마지막 길을 $(2,0) \to L$ 로 정합니다.
이제 $(1,2)$는 $A$ 에서 들어오면서 $(1,1)$에 네 번째 길도 대 주어야 하므로, $(1,2)\!-\!(2,2)$가 버려집니다.
대칭인 문장에 의해 $(1,0)\!-\!(2,0)$도 버려집니다.
이렇게 버려지는 길 네 개가 정해졌고 예산도 정확히 네 개였으므로, 나머지 길은 모두 사용됩니다.
즉 사용하는 길 $13$ 개의 집합은 유일합니다.

사용 안 함 $= \{\, A\!-\!(0,1),\; (1,2)\!-\!(2,2),\; (1,0)\!-\!(2,0),\; (3,1)\!-\!L \,\}$

💡 버릴 길 네 개가 정해지는 순간 예산이 소진되어 다른 길은 버릴 수 없음.

#1 그림 그리기 4.G.A.1 단계 8

경로의 모양 읽기

이 $13$ 개의 길은 정사각형 고리 두 개가 매달린 하나의 사슬을 이룹니다.
$A$ 에서 $A \to (1,2) \to (1,1)$로 가고, 왼쪽 아래 정사각형 $(1,1), (0,1), (0,0), (1,0)$의 길 네 개를 돌아 $(1,1)$로 돌아옵니다.
이어서 $(1,1) \to (2,1)$.
다음으로 오른쪽 위 정사각형 $(2,1), (2,2), (3,2), (3,1)$의 길 네 개를 돌아 $(2,1)$로 돌아옵니다.
마지막으로 $(2,1) \to (2,0) \to L$.

$$2 + 4 + 1 + 4 + 2 = 13$$

💡 두 번 방문되는 두 도시가 바로 경로가 고리를 묶었다가 되돌아오는 지점.

#2 빠짐없이 나열하기 3.OA.A.1 단계 9

돌리는 방법 세기

이제 경로는 고리마다 하나씩의 자유로운 선택만 남기고 모두 고정됩니다: 왼쪽 아래 정사각형을 시계 방향으로 돌 수도, 반시계 방향으로 돌 수도 있고, 오른쪽 위 정사각형도 마찬가지입니다.
두 선택은 서로 영향을 주지 않으므로 경로 수는 $2 \cdot 2 = 4$, 즉 선택지 $\textbf{(E)}$입니다.

$$2 \cdot 2 = 4 \;\Rightarrow\; \textbf{(E)}$$

💡 서로 독립인 두 갈래 선택은 더하는 게 아니라 곱함.

[1] #1 5.G.A.1 각 도시를 $(x,y)$로 부릅니다. $x = 0,1,2,3$은 왼쪽에서 오른쪽, $y = 0,1,2$는 아래에서 위 방향입니다. 그러면 $A

[2] #1 4.G.A.1 각 도시에 모이는 길의 개수를 셉니다. 네 모서리 $A = (0,2)$, $(3,2)$, $(0,0)$, $L = (3,0)$은 각각 $2$ 개

[3] #14 4.NBT.B.6 어떤 도시를 지나가면 그곳의 길 두 개 (들어오기, 나가기)를 소모하고, 같은 길은 다시 쓸 수 없습니다. 그러므로 길이 $d$ 개인 도시는 최

[4] #14 4.OA.A.3 길 $13$ 개를 지나면 도시에 $14$ 번 머뭅니다 (재방문도 별개로 셈). 그중 하나는 $A$, 하나는 $L$ 이므로 나머지 $12$ 번이

[5] #3 2.OA.C.3 사용하지 않는 길 끝을 셉니다. $A$ 는 길 $2$ 개 중 $1$ 개를, $L$ 도 $1$ 개를, 길이 $3$ 개인 여섯 도시도 각각 $1$

[6] #3 4.G.A.1 첫 길이 $A \to (0,1)$ 이라고 해 봅시다. 도시 $(0,1)$은 길이 $3$ 개이고 한 번만 지나므로 정확히 $2$ 개만 씁니다: $

[7] #3 4.G.A.1 지도를 $180^\circ$ 돌리면 $A$ 와 $L$ 이 바뀌고 길 모양은 그대로이므로, 반대쪽 끝에서 같은 논증이 $(3,1)\!-\!L$ 을

[8] #1 4.G.A.1 이 $13$ 개의 길은 정사각형 고리 두 개가 매달린 하나의 사슬을 이룹니다. $A$ 에서 $A \to (1,2) \to (1,1)$로 가고,

[9] #2 3.OA.A.1 이제 경로는 고리마다 하나씩의 자유로운 선택만 남기고 모두 고정됩니다: 왼쪽 아래 정사각형을 시계 방향으로 돌 수도, 반시계 방향으로 돌 수도

검토

합리성 확인: 실제로 존재하는지 경로 하나를 따라가 봅니다: $A(0,2) \to (1,2) \to (1,1) \to (1,0) \to (0,0) \to (0,1) \to (1,1) \to (2,1) \to (3,1) \to (3,2) \to (2,2) \to (2,1) \to (2,0) \to L(3,0)$. 길 $13$ 개를 겹치지 않게 지났으므로 선택지 (A) $0$은 탈락. 한 고리만 반대로 돌려도 분명히 다른 경로가 되므로 두 고리는 $2 \cdot 2 = 4$를 만들고 $2$가 아닙니다 — 선택지 (C)는 두 고리 중 하나만 발견했을 때 나오는 답. $4$를 넘을 수도 없는데, 돌리는 선택을 하기 전에 이미 사용할 길의 집합이 강제로 결정되었기 때문입니다. 버려진 길 그림도 일관됩니다: 버려진 네 길은 서로 만나지 않고, 버려져야 했던 여덟 개의 길 끝을 정확히 소진합니다.

대안 접근: 도구 #2 (빠짐없이 나열하기): 최대 횟수 계산을 건너뛰고 가지치기를 하며 손으로 탐색해도 됩니다. $A$ 에서 첫 이동은 $2$ 가지뿐이고, "길이 $3$ 개인 도시는 한 번만 들어갈 수 있다" 는 규칙이 몇 수 안에 대부분의 가지를 잘라 냅니다 — 아래로 가는 가지는 $(0,1)$ 에서 즉시 죽고, 오른쪽으로 가는 가지는 곧바로 두 정사각형 고리를 강제합니다. 마무리 교차 검증: 강제로 정해진 $13$ 개의 길에서 사용되는 길의 개수가 홀수인 도시는 $A$ 와 $L$ 뿐인데, 이는 그 길을 하나도 빠짐없이 쓰며 $A$ 에서 $L$ 로 가는 경로가 존재할 조건과 정확히 일치하고, 그런 경로를 세면 다시 $2 \cdot 2 = 4$입니다.

사용된 CCSS 표준 (최저 학년 5)

2.OA.C.3 물건의 개수가 홀수인지 짝수인지 판단하기 (길 개수가 홀수인 도시는 길 하나가 반드시 남는다는 관찰, 그리고 버려진 길 끝 $8$ 개와 버려진 길 $4$ 개를 맞춰 보기.)
3.OA.A.1 곱셈을 같은 묶음의 총 개수로 해석하기 (서로 독립인 두 고리의 회전 방향을 곱해 $2 \cdot 2 = 4$ 개의 경로 구하기.)
4.G.A.1 점, 직선, 선분, 반직선, 각 그리기 및 도형에서 식별 (지도를 점과 선분으로 읽고, 도시마다 길 개수를 세고, 어떤 선분이 사용되는지 추적.)
4.NBT.B.6 몫과 나머지 구하기 (도시의 길 개수 $d$ 를 방문 한계 $\left\lfloor \frac{d}{2} \right\rfloor$ 로 바꾸기.)
4.OA.A.3 사칙연산을 이용한 여러 단계 문장제 해결 (길 $13$ 개를 머무름 $14$ 번으로, 다시 다른 도시들의 $12$ 번으로 바꾸고 한계 총합 $12$와 비교.)
5.G.A.1 수직인 두 수직선으로 좌표평면 만들기 (도시 $12$ 개를 격자점 $(x,y)$로 이름 붙여 각 길을 정확히 지목하기.)

⭐ 이 AMC 12 문제는 5학년 도구만으로 풀립니다: 각 도시를 최대 몇 번 쓸 수 있는지 세어 보면 그 합이 길 $13$ 개가 요구하는 머무름 횟수와 정확히 같아 경로 전체가 강제되고, 남는 자유는 두 정사각형 고리를 어느 방향으로 도는지뿐이라 $2 \cdot 2 = 4$, 답은 $\textbf{(E)}$입니다.