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 개 인사이트

문제

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

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

풀이 과정

전략 작은 문제로 쪼개기

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

1STEP 1

격자를 그리면 집 → SW 모퉁이는 동·북 이동만 사용 — E 2번, N 1번으로 총 3번 이동.

1구간 이동 = 2E + 1N, 총 3 번

2STEP 2

2개의 E와 1개의 N을 N의 위치로 나열하면 NEE, ENE, EEN — 1구간은 3가지.

{NEE, ENE, EEN} → 3 가지

3STEP 3

공원 안은 SW → NE 대각선 하나뿐이라 2구간은 정확히 1가지.

2구간 경로 = 1

4STEP 4

3구간(NE 모퉁이 → 학교)은 2개의 E와 2개의 N이 필요 — 순서를 정하면 6가지.

{NNEE, NENE, NEEN, ENNE, ENEN, EENN} → 6 가지

5STEP 5

세 구간이 독립이므로 곱셈 원리로 경우의 수를 곱합니다: 3 × 1 × 6 = 18가지.

전체 = 3 × 1 × 6 = 18 → (E)

정답

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

💡핵심 정리

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

비슷한 유형 더 풀어보기