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

📘 쉬운 버전 보기 →

문제

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

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

풀이 과정

전략 그림 그리기

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

1STEP 1

열은 왼쪽에서 오른쪽으로 0-7, 행은 아래에서 위로 0-7 번호를 매기면 그림에서 P 는 (0, 5), Q 는 (7, 6) 입니다.

P = (0, 5), Q = (7, 6)

2STEP 2

N(r, c) = 흰칸 (r, c) 로 오는 경로 수, 아래 두 대각선의 합: N(r, c) = N(r-1, c-1) + N(r-1, c+1).

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

3STEP 3

규칙을 위로 적용 - 행 1: 1, 1; 행 2: 1, 2, 1; 행 3: 1, 3, 3 (열 8 은 판 밖).

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

4STEP 4

행 6 까지 계속 합산, 가장자리는 한 값만 받음 - 행 4: 4, 6, 3; 행 5: 10, 9; 행 6: 19, 9.

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

5STEP 5

마무리: N(7, 6) = 19 + 9 = 28, 따라서 P 에서 Q 까지 경로는 28 가지 - 답 (A).

N(7, 6) = 19 + 9 = 28 → (A)

정답

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

💡핵심 정리

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

비슷한 유형 더 풀어보기