AMC 8 · 2024 · #13

학년 2 counting

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

systematic-enumerationparity systematic-enumerationcomplementary-counting ↑ 선수 지식: multi-digit-arithmeticparity

📏 중간 풀이 💡 3 개 인사이트 📊 도형

문제

토끼 버즈가 계단을 한 번에 한 칸씩 오르락내리락하며 뛰고 있습니다. 버즈가 땅에서 출발해 $6$ 번 뛴 뒤 다시 땅으로 돌아오는 방법의 수는 몇 가지입니까? (예를 들어, 한 가지 가능한 순서는 위-위-아래-아래-위-아래입니다.)

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

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

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

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 토끼 버즈는 땅(0층)에서 출발해 $6$ 번의 깡충 뛰기를 합니다. 각 깡충은 계단을 한 칸 위로(U) 가거나 한 칸 아래로(D) 가는 동작입니다. 마지막에 다시 땅(0층)에 도착해야 하고, 도중에 단 한 순간도 땅 아래(음수 층)로 내려가서는 안 됩니다. 가능한 모든 U/D 수열이 몇 가지인지 세는 것이 목표입니다.

주어진 것: 총 깡충 횟수: $6$; 각 깡충은 위(+1층) 또는 아래(-1층); 출발 위치: 0층 (땅); 도착 위치: 0층 (땅); 도중의 어떤 시점에도 층계 수준 $\geq 0$ (땅 밑 금지); 선택지: (A) 4, (B) 5, (C) 6, (D) 8, (E) 12

구하는 것: 출발과 도착이 모두 0층이고 도중에 0층 미만으로 내려가지 않는 6번 깡충 수열의 총 개수

이해

계획

주요 도구: #2 빠짐없이 나열하기

보조 도구: #1 그림 그리기, #3 가능성 지우기

선택지의 최댓값이 $12$ 로 아주 작아서, 모든 후보 수열을 직접 적어볼 수 있을 만큼 경우의 수가 적습니다. 따라서 가장 자연스러운 주된 도구는 #2 **빠짐없이 나열하기** 입니다. 각 수열에서 "지금 버즈는 땅 아래로 내려갔는가?"를 확인하기 위해 #1 **그림 그리기** 로 매 단계의 층계 높이를 적어 봅니다. 마지막에 #3 **가능성 지우기** 로 음수 층에 들른 수열을 지워서 유효한 것만 남기고 세면 됩니다. 초등학생에게는 카탈란 수 공식이나 #13 **대수로 바꾸기** 가 필요 없습니다 — 나열만으로 충분히 빠르고 정확합니다.

실행 — 정답: B

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

먼저 큰 그림을 잡습니다.
U 한 번은 $+1$ 층, D 한 번은 $-1$ 층입니다.
6번의 깡충 후 다시 0층으로 돌아오려면 더한 총량과 뺀 총량이 같아야 하므로, U의 개수와 D의 개수가 같아야 합니다.
총 6번이니 U $=$ D $= 3$ 으로 결정됩니다.

$$\#U + \#D = 6,\; \#U = \#D \;\Rightarrow\; \#U = \#D = 3$$

💡 6을 같은 두 묶음 3과 3으로 나누는 것은 1학년의 덧셈·뺄셈 문장제 수준의 추론입니다.

#1 그림 그리기 1.OA.A.1 단계 2

경계 조건 두 가지로 후보를 크게 줄일 수 있습니다.
첫 깡충이 D 이면 곧바로 $-1$ 층(땅 밑)으로 가서 금지되므로 첫 깡충은 반드시 U.
마지막 깡충이 U 이면 0층에서 1층으로 끝나 버리므로, 0층으로 돌아오려면 마지막 깡충은 반드시 D.
따라서 모든 유효 수열은 $U\,\_\,\_\,\_\,\_\, D$ 모양이며, 가운데 네 칸에는 남은 U 2개와 D 2개가 들어갑니다.

$$\text{수열} = U\,\_\,\_\,\_\,\_\,D \;\text{(가운데에 U 2개와 D 2개)}$$

💡 "0에서 1을 빼면 음수가 된다"라는 1학년 덧셈·뺄셈의 직관으로 첫 깡충 방향이 강제됩니다.

#2 빠짐없이 나열하기 K.MD.B.3 단계 3

이제 가운데 4칸에 U 2개를 어디에 둘지 **순서 규칙**(두 U의 자리를 작은 번호부터)으로 빠짐없이 나열합니다: 자리쌍은 $(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)$.
이렇게 정확히 6개의 후보가 나옵니다.
앞뒤의 강제 U, D를 붙여 전체 수열로 풀어 적어 봅시다.

$$\text{후보 6개: } UUUDDD,\; UUDUDD,\; UUDDUD,\; UDUUDD,\; UDUDUD,\; UDDUUD$$

💡 정해진 순서대로 모두 나열해 빠뜨림과 중복을 막는 것은 유치원 "분류하고 세기" 수준의 사고입니다.

#3 가능성 지우기 2.OA.A.1 단계 4

6개 후보 각각에 대해 0층에서 시작해 U면 $+1$, D면 $-1$ 로 층계 높이를 한 단계씩 적어 봅니다.
한 번이라도 0층 미만으로 내려가면 지웁니다.
결과는 다음과 같습니다.
$UUUDDD\to(1,2,3,2,1,0)$ 통과; $UUDUDD\to(1,2,1,2,1,0)$ 통과; $UUDDUD\to(1,2,1,0,1,0)$ 통과; $UDUUDD\to(1,0,1,2,1,0)$ 통과; $UDUDUD\to(1,0,1,0,1,0)$ 통과; $UDDUUD\to(1,0,-1,\ldots)$ \textbf{땅 밑} — 탈락.

$$UDDUUD: 0 \xrightarrow{U} 1 \xrightarrow{D} 0 \xrightarrow{D} -1 \;\;\text{(땅 밑 — 무효)}$$

💡 $+1$ 과 $-1$ 을 여러 단계 누적하면서 "0보다 작아지지 않았는가"를 확인하는 것은 2학년의 두 단계 덧셈·뺄셈 문장제 수준입니다.

#3 가능성 지우기 K.MD.B.3 단계 5

살아남은 수열을 세어 봅니다: $UUUDDD,\; UUDUDD,\; UUDDUD,\; UDUUDD,\; UDUDUD$ — 총 $5$ 개.
따라서 답은 $\boxed{5}$, 즉 $\textbf{(B)}$.
다른 선택지 확인: (A) $4$ 는 유효한 수열을 하나 더 잘못 지운 경우, (C) $6$ 은 $UDDUUD$ 를 못 지운 경우, (D) $8$ 과 (E) $12$ 는 "U로 시작 D로 끝나는" 후보 총 6개조차 넘어 버려 모두 배제됩니다.

$$\text{유효 개수} = 6 - 1 = 5 \;\Rightarrow\; \textbf{(B)}$$

💡 후보들을 "유효/무효" 두 묶음으로 나눈 다음 유효한 묶음의 개수를 세는 것은 유치원 "분류하고 세기" 표준 그대로입니다.

[1] #1 1.OA.A.1 먼저 큰 그림을 잡습니다. U 한 번은 $+1$ 층, D 한 번은 $-1$ 층입니다. 6번의 깡충 후 다시 0층으로 돌아오려면 더한 총량과 뺀

[2] #1 1.OA.A.1 경계 조건 두 가지로 후보를 크게 줄일 수 있습니다. 첫 깡충이 D 이면 곧바로 $-1$ 층(땅 밑)으로 가서 금지되므로 첫 깡충은 반드시 U.

[3] #2 K.MD.B.3 이제 가운데 4칸에 U 2개를 어디에 둘지 **순서 규칙**(두 U의 자리를 작은 번호부터)으로 빠짐없이 나열합니다: 자리쌍은 $(1,2), (

[4] #3 2.OA.A.1 6개 후보 각각에 대해 0층에서 시작해 U면 $+1$, D면 $-1$ 로 층계 높이를 한 단계씩 적어 봅니다. 한 번이라도 0층 미만으로 내려가

[5] #3 K.MD.B.3 살아남은 수열을 세어 봅니다: $UUUDDD,\; UUDUDD,\; UUDDUD,\; UDUUDD,\; UDUDUD$ — 총 $5$ 개. 따라서

검토

합리성 확인: 답 $5$ 는 선택지 $4, 5, 6, 8, 12$ 중 중간쯤에 위치해 크기 감각으로도 자연스럽습니다. 구조적으로도 일치합니다: 가운데 네 칸에 U 2개를 넣는 방법이 $\binom{4}{2} = 6$ 가지이고, 그중 정확히 한 가지($UDDUUD$)만 땅 밑으로 내려가므로 $6 - 1 = 5$. 살아남은 5개 수열 각각은 층계 높이를 한 단계씩 그려 다시 확인할 수 있고, 나열 규칙이 "두 U의 자리를 작은 순으로"라서 중복도 없습니다.

대안 접근: 다른 풀이로 도구 #9(더 쉬운 문제로 줄이기)를 쓸 수 있습니다. 깡충이 2번이면 $UD$ 한 가지, 4번이면 $UUDD, UDUD$ 두 가지, 6번이면 $5$ 가지. 이렇게 얻은 $1, 2, 5, \ldots$ 는 카탈란 수의 시작이며, $6$ 번 깡충에서 $5$ 가 나옵니다. 멋진 관찰이지만, 초등학생에게는 위의 나열 풀이가 더 빠르고 "어떤 수열이 유효한지"를 눈으로 보여 주기 때문에 더 정직합니다.

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

1.OA.A.1 20까지의 수에서 덧셈·뺄셈 문장제를 해결한다 (총 6번의 깡충을 U 3번과 D 3번으로 나누고, 0층에서 빼면 음수가 되므로 첫 깡충이 U여야 함을 추론하는 데 사용.)
K.MD.B.3 주어진 범주로 사물을 분류하고 각각의 개수를 센다 (후보 수열 6가지를 정해진 순서로 빠짐없이 나열하고, "유효" 묶음에 남은 개수를 세는 데 사용.)
2.OA.A.1 100까지의 덧셈과 뺄셈을 이용해 한 단계 또는 두 단계 문장제를 해결한다 (각 깡충마다 $+1$ 또는 $-1$ 을 누적해 층계 높이를 추적하고, 0층 미만으로 내려가지 않는지 확인하는 데 사용.)

⭐ 이 AMC 8 문제는 사실 2학년 때 배운 한 단계씩 더하고 빼며 추적하기만 알면 풀려요!

문제

도구 + CCSS 풀이

이해

계획

실행 — 정답: B

검토

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

비슷한 유형 더 풀어보기