AMC 8 · 2010 · #25

학년 4 counting

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

recursive-sequencepattern-recognitionsystematic-enumeration tree-enumerationpattern-recognitioneasier-related-problem ↑ 선수 지식: systematic-enumerationpattern-recognition

📏 긴 풀이 💡 4 개 인사이트

문제

조는 6 칸짜리 계단을 오르는데, 한 번에 1 칸, 2 칸, 또는 3 칸을 갈 수 있습니다. 걸음의 순서가 다르면 다른 방법으로 셉니다(예: 3, 1, 2 와 2, 1, 3 은 서로 다른 방법). 조가 꼭대기에 닿는 서로 다른 방법은 모두 몇 가지일까요?

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

풀이 과정

전략 작은 문제로 쪼개기

6 칸 전부를 한 번에 나열하면 실수하기 쉬우므로, 먼저 도구 #9(더 쉬운 문제로 줄이기)로 f(1), f(2), f(3) 을 도구 #2(빠짐없이 나열하기)로 직접 셉니다. 그다음 도구 #7(작은 문제로 쪼개기)이 결정적인 아이디어를 줍니다 — 조의 마지막 걸음이 1, 2, 3 중 무엇이었든 그 직전 상황은 같은 종류의 더 작은 문제일 뿐이라는 점이죠. 그러면 f(n) = f(n-1) + f(n-2) + f(n-3) 으로 한 문제가 세 개의 작은 문제로 쪼개지고, 도구 #5(패턴 찾기)로 이 규칙을 n = 6 까지 늘려 가면 전체 수열을 한 줄도 나열하지 않고 답을 얻을 수 있습니다.

1STEP 1

먼저 문제를 줄입니다 (도구 #9): 계단이 1 칸이면 방법은 하나뿐, 즉 f(1) = 1.

f(1) = 1

2STEP 2

직접 나열합니다 (도구 #2): 2 칸은 (1,1),(2) 로 f(2) = 2, 3 칸은 네 가지로 f(3) = 4.

f(2) = 2, f(3) = 4

3STEP 3

마지막 걸음으로 나눕니다 (도구 #7): 직전 위치가 n-1, n-2, n-3 이므로 f(n-1) + f(n-2) + f(n-3).

f(n) = f(n-1) + f(n-2) + f(n-3)

4STEP 4

이제 패턴을 이어 갑니다 (도구 #5): 1, 2, 4 에서 규칙을 쓰면 f(4) = 7.

f(4) = 4 + 2 + 1 = 7

5STEP 5

점화식을 한 번 더 굴리면 f(5) = 13, 이어서 f(6) = 24 — 정답 (E).

f(5) = 7 + 4 + 2 = 13, f(6) = 13 + 7 + 4 = 24 → (E)

정답

답 24 는 선택지 중 가장 큰 값이고, 6 칸 계단에 세 가지 걸음 크기를 자유롭게 섞을 수 있으니 경우의 수가 꽤 많을 거라는 직관과도 맞습니다. f(4) = 7 을 직접 나열해 검토하면 (1,1,1,1), (1,1,2), (1,2,1), (2,1,1), (2,2), (1,3), (3,1) — 정확히 7 개입니다. 점화식이 옳으니 f(6) = 24 도 일관됩니다.

💡핵심 정리

이 AMC 8 문제는 사실 4학년 때 배운 패턴 만들기 — 마지막 한 걸음으로 경우를 나누고 작은 답들을 더하는 — 만으로도 풀 수 있어요!

비슷한 유형 더 풀어보기