AMC 8 · 2020 · #21

학년 5 counting

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

pattern-recognitioncombinations-basicsystematic-enumeration tree-enumerationpattern-recognitionidentify-subproblems ↑ 선수 지식: systematic-enumeration

📏 긴 풀이 💡 4 개 인사이트 📊 도형

📘 쉬운 버전 보기 →

문제

한 보드게임 판은 검은색과 흰색이 번갈아 칠해진 $64$ 개의 정사각형 칸으로 이루어져 있습니다. 아래 그림은 맨 아랫줄에 있는 칸 $P$ 와 맨 윗줄에 있는 칸 $Q$ 를 보여 줍니다. 말 하나가 $P$ 에 놓여 있습니다. 한 번의 이동은 말을 바로 윗줄에 있는 인접한 흰색 칸 중 하나로 옮기는 것입니다. $P$ 에서 $Q$ 까지 $7$ 번의 이동으로 가는 경로의 수는 몇 가지입니까? (그림은 그러한 경로의 한 예를 보여 줍니다.)

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

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

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: $8 \times 8$ 체스판이 검은색과 흰색 칸으로 번갈아 칠해져 있습니다. 말은 맨 아랫줄 흰색 칸 $P$ 에서 출발하며, 한 번의 이동은 바로 윗줄의 대각선 왼쪽 또는 대각선 오른쪽 흰색 칸으로 옮기는 것입니다. 정확히 $7$ 번 이동하여 맨 윗줄의 흰색 칸 $Q$ 에 도달하는 서로 다른 경로는 모두 몇 가지일까요?

주어진 것: $8 \times 8$ 체스판이 검은색·흰색 칸으로 번갈아 칠해짐; 말은 맨 아랫줄 흰색 칸 $P$ 에서 출발; 도착 칸 $Q$ 는 맨 윗줄의 흰색 칸; 한 번의 이동은 대각선으로 한 줄 위의 흰색 칸 (좌·우 둘 중 하나) 으로만 가능하며 판 안에 머물러야 함; 총 이동 횟수는 정확히 $7$ 번 (맨 아랫줄에서 맨 윗줄까지); 선택지: (A) $28$, (B) $30$, (C) $32$, (D) $33$, (E) $35$

구하는 것: $P$ 에서 $Q$ 까지 가는 서로 다른 $7$ 단계 경로의 개수

이해

계획

주요 도구: #1 그림 그리기

보조 도구: #5 패턴 찾기, #7 작은 문제로 쪼개기

격자 위에서 경로를 세는 문제는 도구 #1(그림 그리기)의 교과서 같은 예시입니다 — 판을 다시 그리고 $P$ 부터 한 줄씩 올라가며 각 흰색 칸에 "여기까지 오는 경로 수" 를 적어 나가면 됩니다. 도구 #5(패턴 찾기)가 자연스럽게 등장하는 이유는, 어떤 칸의 수가 바로 아래 두 대각선 칸 수의 합으로 정해지기 때문입니다 — 가장자리에서 한 쪽이 판 밖으로 떨어지는 점만 빼면 그대로 파스칼의 삼각형 패턴입니다. 도구 #7(작은 문제로 쪼개기)은 "$(r, c)$ 에 도달하는 방법의 수" 를 "$(r-1, c-1)$ 과 $(r-1, c+1)$ 에 도달하는 방법의 수의 합" 이라는 두 개의 더 작은 문제로 깔끔하게 갈라 줍니다.

실행 — 정답: A

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

좌표를 잡습니다.
열은 왼쪽에서 오른쪽으로 $0$ 부터 $7$ 까지, 행은 아래에서 위로 $0$ 부터 $7$ 까지 번호를 붙입니다.
그림에서 $P$ 는 (행 $0$, 열 $5$) 이고 $Q$ 는 (행 $7$, 열 $6$) 입니다.
합법적인 이동은 모두 흰색 칸에서 흰색 칸으로 대각선 한 칸 위로만 가능하다는 점을 확인합니다 — 검은 칸이나 옆 칸, 아래 칸으로는 절대 갈 수 없습니다.

$$P = (0, 5), \quad Q = (7, 6)$$

💡 판 위에 행과 열을 매기는 것은 모든 흰색 칸에 좌표 $(r, c)$ 라는 주소를 부여하는 5학년 좌표 격자의 발상 그대로입니다.

#7 작은 문제로 쪼개기 4.OA.C.5 단계 2

세는 규칙을 정합니다.
$N(r, c)$ 를 "$P$ 에서 시작해 $r$ 번 이동하여 흰색 칸 $(r, c)$ 에 도달하는 경로의 수" 라고 합시다.
$(r, c)$ 에는 오직 $(r-1, c-1)$ 또는 $(r-1, c+1)$ 에서만 올 수 있고 (각 칸이 판 위에 있을 때만), 따라서 $N(r, c) = N(r-1, c-1) + N(r-1, c+1)$ 입니다.
시작값은 $N(0, 5) = 1$ ($P$ 에 있는 방법은 "가만히 있기" 한 가지뿐).

$$N(r, c) = N(r-1, c-1) + N(r-1, c+1), \quad N(0, 5) = 1$$

💡 "$(r, c)$ 도달" 을 "바로 아래 두 대각선 칸 도달" 이라는 두 작은 문제의 합으로 쪼개는 것은 4학년 "규칙으로 패턴 만들기" 의 핵심 동작입니다.

#5 패턴 찾기 4.OA.C.5 단계 3

Step 2 의 규칙을 한 줄씩 적용합니다.
행 $1$: $(1, 4) = 1$, $(1, 6) = 1$.
행 $2$: $(2, 3) = 1$, $(2, 5) = 1 + 1 = 2$, $(2, 7) = 1$.
행 $3$: $(3, 2) = 1$, $(3, 4) = 1 + 2 = 3$, $(3, 6) = 2 + 1 = 3$ ($(3, 8)$ 은 판 밖이라 더할 게 없음).

$$N(1, 4) = 1,\; N(1, 6) = 1; \quad N(2, 3) = 1,\; N(2, 5) = 2,\; N(2, 7) = 1; \quad N(3, 2) = 1,\; N(3, 4) = 3,\; N(3, 6) = 3$$

💡 새 숫자는 바로 아래 두 대각선 숫자의 합 — 4학년 때 본 파스칼의 삼각형 패턴 그대로입니다.

#1 그림 그리기 4.OA.C.5 단계 4

행 $6$ 까지 같은 방식으로 채워 갑니다.
오른쪽 가장자리(열 $8$ 은 존재하지 않음) 때문에 $(4, 7)$ 같은 칸은 $(3, 6)$ 한 곳에서만 값을 받습니다.
행 $4$: $(4, 3) = 1 + 3 = 4$, $(4, 5) = 3 + 3 = 6$, $(4, 7) = 3$.
행 $5$: $(5, 4) = 4 + 6 = 10$, $(5, 6) = 6 + 3 = 9$.
행 $6$: $(6, 5) = 10 + 9 = 19$, $(6, 7) = 9$.

$$N(4, 3) = 4,\; N(4, 5) = 6,\; N(4, 7) = 3; \quad N(5, 4) = 10,\; N(5, 6) = 9; \quad N(6, 5) = 19,\; N(6, 7) = 9$$

💡 각 흰색 칸 위에 누적합을 직접 적어 두면 진행 상황이 한눈에 보이고, 가장자리 칸은 한 곳에서만 값을 받는 것도 자연스럽게 드러납니다.

#1 그림 그리기 4.NBT.B.4 단계 5

마지막으로 $N(7, 6) = N(6, 5) + N(6, 7) = 19 + 9 = 28$ 을 계산합니다.
따라서 $P$ 에서 $Q$ 까지 가는 서로 다른 $7$ 단계 경로는 정확히 $28$ 가지이고, 답은 (A) 입니다.

$$N(7, 6) = 19 + 9 = 28 \;\Rightarrow\; \textbf{(A)}$$

💡 $19 + 9 = 28$ 의 마무리 덧셈은 4학년 여러 자리수 덧셈 그대로입니다.

[1] #1 5.G.A.1 좌표를 잡습니다. 열은 왼쪽에서 오른쪽으로 $0$ 부터 $7$ 까지, 행은 아래에서 위로 $0$ 부터 $7$ 까지 번호를 붙입니다. 그림에서 $

[2] #7 4.OA.C.5 세는 규칙을 정합니다. $N(r, c)$ 를 "$P$ 에서 시작해 $r$ 번 이동하여 흰색 칸 $(r, c)$ 에 도달하는 경로의 수" 라고 합

[3] #5 4.OA.C.5 Step 2 의 규칙을 한 줄씩 적용합니다. 행 $1$: $(1, 4) = 1$, $(1, 6) = 1$. 행 $2$: $(2, 3) = 1$,

[4] #1 4.OA.C.5 행 $6$ 까지 같은 방식으로 채워 갑니다. 오른쪽 가장자리(열 $8$ 은 존재하지 않음) 때문에 $(4, 7)$ 같은 칸은 $(3, 6)$ 한

[5] #1 4.NBT.B.4 마지막으로 $N(7, 6) = N(6, 5) + N(6, 7) = 19 + 9 = 28$ 을 계산합니다. 따라서 $P$ 에서 $Q$ 까지 가는

검토

합리성 확인: 가장자리 제약을 무시한 "자유 버전" 으로 점검해 봅시다. 판 경계가 없다고 가정하면, $7$ 단계 동안 열이 $5$ 에서 $6$ 으로 이동(오른쪽으로 $+1$)하려면 오른쪽 이동 $4$ 번, 왼쪽 이동 $3$ 번이 필요하므로 $\binom{7}{4} = 35$ 가지 경로가 됩니다. 우리가 구한 답 $28$ 은 이보다 살짝 작은데, 이는 오른쪽 가장자리 때문에 일부 경로가 사라지기 때문입니다 ($(4, 7)$ 같은 가장자리 칸은 다음 갈 곳이 한 곳뿐). 잘려 나간 경로 수는 정확히 $35 - 28 = 7$ 가지로, 가장자리 보정으로 충분히 그럴 듯한 작은 차이입니다.

대안 접근: 도구 #16(관점 바꾸기·여사건 세기)을 쓰면 위의 점검을 그대로 풀이로 바꿀 수 있습니다 — 먼저 자유 경로 $\binom{7}{4} = 35$ 를 구한 뒤, "오른쪽 가장자리를 벗어나는 경로" 를 거울 반사 (reflection principle) 로 세어 빼면 됩니다. 아직 이항계수를 모르는 학생이라면 도구 #2(빠짐없이 나열하기) 도 가능합니다 — 길이 $7$ 의 좌(L)·우(R) 수열을 모두 만든 다음, 판 밖으로 벗어나는 것을 지우고 남는 것을 셉니다.

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

5.G.A.1 수직인 두 수직선으로 좌표 체계 만들기 (판에 행 $0$-$7$, 열 $0$-$7$ 을 매겨 모든 흰색 칸에 좌표 $(r, c)$ 를 부여하고 $P = (0, 5)$, $Q = (7, 6)$ 의 위치를 잡는 데 사용.)
4.OA.C.5 주어진 규칙을 따라 수 또는 도형 패턴 만들기 ($N(r, c) = N(r-1, c-1) + N(r-1, c+1)$ 규칙을 한 줄씩 적용하여 (파스칼의 삼각형 형태의) 경로 수 패턴을 채워 나가는 데 사용.)
4.NBT.B.4 여러 자리 자연수의 능숙한 덧셈과 뺄셈 ($10 + 9 = 19$, $19 + 9 = 28$ 같은 행별 누적 덧셈을 수행하는 데 사용.)

⭐ 이 AMC 8 문제는 사실 5학년 좌표 격자와 4학년 "바로 아래 두 수를 더한다" 는 파스칼의 삼각형 패턴만 알면 풀 수 있어요!

문제

도구 + CCSS 풀이

이해

계획

실행 — 정답: A

검토

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

비슷한 유형 더 풀어보기