AMC 8 · 2013 · #21

학년 7 counting

유형 Branching State Enumeration └ 세부 유형 Constrained Sequence or Path Count

lattice-pathscombinations-basicsystematic-enumeration identify-subproblemssystematic-enumeration ↑ 선수 지식: combinations-basicsystematic-enumeration

📏 중간 풀이 💡 3 개 인사이트

문제

사만다(Samantha)는 시티 파크(City Park)의 남서쪽 모퉁이로부터 서쪽으로 $2$ 블록, 남쪽으로 $1$ 블록 떨어진 곳에 살고 있습니다. 그녀의 학교는 같은 공원의 북동쪽 모퉁이로부터 동쪽으로 $2$ 블록, 북쪽으로 $2$ 블록 떨어진 곳에 있습니다. 학교에 가는 날, 그녀는 길을 따라 자전거를 타고 공원의 남서쪽 모퉁이까지 간 다음, 공원 안에서는 대각선 길을 따라 북동쪽 모퉁이까지 가로지르고, 다시 길을 따라 자전거를 타고 학교까지 갑니다. 전체 경로의 길이가 가능한 한 짧을 때, 그녀가 갈 수 있는 서로 다른 경로는 모두 몇 가지일까요?

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

AMC 8 2013 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

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

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 사만다는 City Park 의 남서(SW) 모퉁이에서 서쪽으로 $2$ 블록, 남쪽으로 $1$ 블록 떨어진 곳에 삽니다. 학교는 공원 북동(NE) 모퉁이에서 동쪽으로 $2$ 블록, 북쪽으로 $2$ 블록 떨어진 곳에 있습니다. 그녀는 길을 따라 가장 짧은 경로로 SW 모퉁이까지 자전거를 타고, 공원 안에서는 SW $\to$ NE 로 가는 단 하나의 대각선 길을 지난 뒤, 다시 길을 따라 가장 짧은 경로로 학교에 갑니다. 가능한 서로 다른 최단 경로는 총 몇 가지일까요?

주어진 것: 집은 공원 SW 모퉁이에서 서쪽 $2$ 블록, 남쪽 $1$ 블록 떨어져 있음; 학교는 공원 NE 모퉁이에서 동쪽 $2$ 블록, 북쪽 $2$ 블록 떨어져 있음; 공원 안에는 SW $\to$ NE 대각선 길이 정확히 $1$ 개; 길 위에서는 블록 단위로만 이동 (대각선 지름길 없음); 각 구간 모두 최단 경로여야 함; 선택지: (A) $3$, (B) $6$, (C) $9$, (D) $12$, (E) $18$

구하는 것: 집에서 학교까지의 서로 다른 최단 경로의 총 개수

이해

계획

주요 도구: #7 작은 문제로 쪼개기

보조 도구: #2 빠짐없이 나열하기, #1 그림 그리기

이 여정은 집 $\to$ SW 모퉁이, SW $\to$ NE (공원 통과), NE 모퉁이 $\to$ 학교 의 독립적인 세 구간으로 나뉘므로, 도구 #7(작은 문제로 쪼개기) 로 어려운 한 번의 셈을 쉬운 세 번으로 바꿉니다. 각 길 구간은 이동이 $3$ 번 또는 $4$ 번뿐이라 도구 #2(빠짐없이 나열하기) 로 E·N 의 순서를 직접 적어 모든 최단 경로를 열거할 수 있습니다. 도구 #1(그림 그리기) 로 격자를 그려두면 N/S/E/W 가 헷갈리지 않습니다. 마지막에는 세 구간이 독립이므로 곱셈 원리(곱셈 셈하기 원칙) 로 결과를 곱해 줍니다.

실행 — 정답: E

#1 그림 그리기 4.OA.A.3 단계 1

격자를 그립니다.
공원을 정사각형으로 두고, 집을 SW 모퉁이에서 서쪽 $2$ 블록·남쪽 $1$ 블록에, 학교를 NE 모퉁이에서 동쪽 $2$ 블록·북쪽 $2$ 블록에 표시합니다.
집 $\to$ SW 모퉁이의 최단 경로는 동(E) 와 북(N) 방향 이동만 사용합니다 — E 가 $2$ 번, N 이 $1$ 번 필요합니다.
다른 방향으로 가면 거리가 늘어납니다.

$$\text{1구간 이동} = 2\text{E} + 1\text{N},\ \text{총 } 3 \text{ 번}$$

💡 격자를 그려두면 헷갈리는 N/S/E/W 문장제가 "오른쪽·위로 걷기" 로 단순해지는, 4학년 다단계 문장제의 기본 셋업입니다.

#2 빠짐없이 나열하기 7.SP.C.8 단계 2

1구간의 모든 최단 경로를 $2$ 개의 E 와 $1$ 개의 N 으로 이루어진 길이 $3$ 의 문자열로 나열합니다.
정렬 규칙을 "N 의 위치(1·2·3 번째)" 로 정하면 $3$ 가지 — NEE, ENE, EEN — 가 빠짐없이 나옵니다.
따라서 1구간은 $\mathbf{3}$ 가지.

$$\{\text{NEE},\ \text{ENE},\ \text{EEN}\} \Rightarrow 3 \text{ 가지}$$

💡 이동 순서를 정렬된 목록으로 적는 것은 복합 사건의 표본 공간을 다루는 7학년 기법 그대로입니다.

#7 작은 문제로 쪼개기 4.OA.A.3 단계 3

2구간은 공원 안.
문제에서 "대각선 길" 하나로 SW $\to$ NE 를 통과한다고 했으므로 2구간은 정확히 $\mathbf{1}$ 가지.

$$\text{2구간 경로} = 1$$

💡 쉬운 구간을 먼저 분리해 두면 어려운 셈에 집중할 수 있는 것이 도구 #7 의 핵심입니다.

#2 빠짐없이 나열하기 7.SP.C.8 단계 4

3구간(NE 모퉁이 $\to$ 학교) 에서는 E 가 $2$ 번, N 이 $2$ 번 필요해 총 $4$ 번 이동합니다.
$2$ 개의 E 와 $2$ 개의 N 으로 만들 수 있는 길이 $4$ 의 문자열을 "첫 N 의 위치" 순으로 정렬하면 $6$ 가지 — NNEE, NENE, NEEN, ENNE, ENEN, EENN — 가 나옵니다.
따라서 3구간은 $\mathbf{6}$ 가지.

$$\{\text{NNEE},\ \text{NENE},\ \text{NEEN},\ \text{ENNE},\ \text{ENEN},\ \text{EENN}\} \Rightarrow 6 \text{ 가지}$$

💡 정렬 규칙을 정해 두면 빠짐도 중복도 생기지 않는다는 점이 도구 #2 의 핵심 규율입니다.

#7 작은 문제로 쪼개기 7.SP.C.8 단계 5

세 구간이 독립이므로 곱셈 원리(기본 셈하기 원칙) 에 따라 각 구간의 경우의 수를 모두 곱합니다.

$$\text{전체} = 3 \times 1 \times 6 = 18 \;\Rightarrow\; \textbf{(E)}$$

💡 한 단계의 선택이 다른 단계의 선택에 영향을 주지 않을 때 경우의 수를 곱하는 것이 7학년 복합 사건 추론입니다.

[1] #1 4.OA.A.3 격자를 그립니다. 공원을 정사각형으로 두고, 집을 SW 모퉁이에서 서쪽 $2$ 블록·남쪽 $1$ 블록에, 학교를 NE 모퉁이에서 동쪽 $2$ 블

[2] #2 7.SP.C.8 1구간의 모든 최단 경로를 $2$ 개의 E 와 $1$ 개의 N 으로 이루어진 길이 $3$ 의 문자열로 나열합니다. 정렬 규칙을 "N 의 위치(1

[3] #7 4.OA.A.3 2구간은 공원 안. 문제에서 "대각선 길" 하나로 SW $\to$ NE 를 통과한다고 했으므로 2구간은 정확히 $\mathbf{1}$ 가지.

[4] #2 7.SP.C.8 3구간(NE 모퉁이 $\to$ 학교) 에서는 E 가 $2$ 번, N 이 $2$ 번 필요해 총 $4$ 번 이동합니다. $2$ 개의 E 와 $2$

[5] #7 7.SP.C.8 세 구간이 독립이므로 곱셈 원리(기본 셈하기 원칙) 에 따라 각 구간의 경우의 수를 모두 곱합니다.

검토

합리성 확인: 답 $18$ 은 선택지 (E) 와 일치합니다. 검산: E·N 이동만 허용되는 $m \times n$ 격자의 최단 경로 수는 $\binom{m+n}{m}$ 입니다. 1구간 $\binom{2+1}{1} = 3$, 3구간 $\binom{2+2}{2} = 6$, 곱 $3 \times 1 \times 6 = 18$ — 직접 나열한 결과와 정확히 일치합니다. 짧은 구간 $3$ 가지, 긴 구간 $6$ 가지의 곱이므로 $6$ 미만이거나 $18$ 초과인 답은 모두 비현실적입니다.

대안 접근: 도구 #9(더 쉬운 문제로 줄이기) 로도 같은 답이 나옵니다. 작은 격자부터 — $1 \times 1$ 모퉁이는 $2$ 가지(EN, NE), $1 \times 2$ 는 $3$ 가지, $2 \times 2$ 는 $6$ 가지 — 를 직접 세어 보면 파스칼 삼각형 ($\binom{m+n}{m}$) 의 규칙이 보입니다. 다시 나열하지 않고도 1구간 $= 3$, 3구간 $= 6$ 을 확인할 수 있고, 고정된 대각선 $1$ 을 곱해 $18$ 을 얻습니다.

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

4.OA.A.3 사칙연산을 사용한 다단계 문장제 해결 (N/S/E/W 설명으로부터 격자를 세팅하고 여정을 독립적인 세 구간으로 쪼개 마지막에 결합하는 데 사용.)
7.SP.C.8 정렬된 목록·표·나무 그림·시뮬레이션을 사용해 복합 사건의 확률 구하기 (각 길 구간의 최단 경로를 이동 순서 문자열로 나열($1$ 구간 $3$ 가지, $3$ 구간 $6$ 가지) 하고, 곱셈 원리로 세 구간을 결합해 $3 \times 1 \times 6 = 18$ 을 얻는 데 사용.)

⭐ 여정을 조각내고, 조각마다 짧은 경로를 빠짐없이 나열한 뒤, 곱하기. 격자 경로 문제는 이게 전부예요.

문제

도구 + CCSS 풀이

이해

계획

실행 — 정답: E

검토

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

비슷한 유형 더 풀어보기