AMC 10 · 2012 · #22

학년 7 counting

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

pattern-recognitioncombinations-basic easier-related-problem ↑ 선수 지식: pattern-recognition

📏 중간 풀이 💡 3 개 인사이트

문제

( $a_1$ , $a_2$ , ... $a_{10}$ )이 처음 10개의 양의 정수를 나열한 것으로, 각 $2\le$ $i$ $\le10$ 에 대하여 $a_i + 1$ 또는 $a_i-1$ 중 적어도 하나가 목록에서 $a_i$ 보다 앞의 어딘가에 나타난다고 하자. 이러한 목록은 몇 개인가?

답을 골라 클릭하세요.

(A)

$\ 120$

(B)

512

(C)

$\ 1024$

(D)

181,440

(E)

$\ 362,880$

AMC 10 2012 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

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

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: $1$ 부터 $10$ 까지의 수를 어떤 순서로 늘어놓습니다. 규칙은 이렇습니다: 두 번째 수부터는, 새로 적는 모든 수가 자기보다 정확히 $1$ 크거나 $1$ 작은 이웃 값을 이미 앞쪽 어딘가에 두고 있어야 합니다. 이 규칙을 지키는 서로 다른 나열이 몇 가지인지 세세요.

주어진 것: 이 나열은 처음 $10$ 개의 양의 정수 $1, 2, \dots, 10$ 의 한 순서(순열)입니다.; $2 \le i \le 10$ 인 각 위치 $i$ 에 대해, $a_i - 1$ 또는 $a_i + 1$ 중 적어도 하나가 위치 $i$ 앞쪽 어딘가에 나타납니다.; 첫 번째 수 $a_1$ 에는 제약이 없습니다.; 선택지: (A) $120$, (B) $512$, (C) $1024$, (D) $181{,}440$, (E) $362{,}880$.

구하는 것: $1$ 부터 $10$ 까지의 유효한 나열(순서)의 개수.

이해

계획

주요 도구: #16 관점 바꾸기

보조 도구: #9 더 쉬운 문제로 줄이기, #1 그림 그리기, #2 빠짐없이 나열하기, #3 가능성 지우기

$10$ 길이의 나열을 정면으로 세는 것은 무리이므로, 무엇을 셀지 관점을 바꿉니다(도구 #16). 먼저 문제를 줄여 보면(도구 #9) $n = 2, 3, 4$ 에서 개수가 $2, 4, 8$ 로 나와 $2^{\,n-1}$ 을 암시합니다. 수직선 그림(도구 #1)으로 핵심 구조가 드러납니다 — 지금까지 적은 값들은 항상 끊김 없는 한 덩어리를 이루며 그 왼쪽 끝이나 오른쪽 끝에서만 자랄 수 있습니다. 그러면 각 나열을 $9$ 번의 왼쪽/오른쪽 이동 문자열로 다시 쓸 수 있고, 덩어리가 $[1, 10]$ 으로 끝나야 한다는 조건이 시작 수를 강제로 정해 줍니다. 그 문자열들을 세는 것은 곱셈 원리를 쓰는 단순한 나열(도구 #2)이라 $2^9$ 이 되고, 그 값을 선택지에 맞추면(도구 #3) 답이 나옵니다.

실행 — 정답: B

#9 더 쉬운 문제로 줄이기 4.OA.C.5 단계 1

작은 버전을 먼저 시험

$10$ 을 작은 $n$ 으로 바꿔 손으로 셉니다.
$n = 2$ 일 때 $(1,2)$ 와 $(2,1)$ 둘 다 되므로 $2$ 가지.
$n = 3$ 일 때 유효한 나열은 $(1,2,3),\ (2,1,3),\ (2,3,1),\ (3,2,1)$ 로 $4$ 가지.
$n = 4$ 를 조심스레 세면 $8$ 가지.
$2, 4, 8$ 은 매번 두 배가 되어 길이 $n$ 에서 $2^{\,n-1}$ 가지를 시사합니다.

$$f(2) = 2, \quad f(3) = 4, \quad f(4) = 8 \;\Rightarrow\; f(n) = 2^{\,n-1}\,?$$

💡 나열을 줄이면 증명 전에 숨은 두 배 패턴이 눈에 보입니다.

#1 그림 그리기 6.NS.C.6 단계 2

수들을 하나의 선분으로 보기

이미 적은 값들을 수직선 위의 점으로 그려 봅니다.
첫 수는 점 하나입니다.
이후의 모든 수는 이미 놓인 점 옆에 붙어야 하므로, 현재 무리의 왼쪽 끝이나 오른쪽 끝에만 붙을 수 있습니다.
따라서 적힌 수들은 항상 연속한 정수의 끊김 없는 한 덩어리 $[L, R]$ 를 이루며 — 절대 사이가 벌어지지 않습니다.
수를 하나 더하면 $[L, R]$ 는 $[L-1, R]$ 또는 $[L, R+1]$ 로 바뀝니다.

$$[L, R] \;\longrightarrow\; [L-1, R] \ \text{또는}\ [L, R+1]$$

💡 새 값은 옛 값과 $1$ 만큼만 차이 나므로, 덮인 수들은 하나의 이어진 구간으로 붙어 있습니다.

#16 관점 바꾸기 7.SP.C.8 단계 3

나열을 이동으로 바꾸기

덩어리는 매번 정확히 한 칸씩 — 왼쪽($L$) 또는 오른쪽($R$) — 자라므로, 한 나열은 그 시작 값과 뒤이은 $9$ 번의 이동(각각 $L$ 또는 $R$)일 뿐입니다.
그런데 시작은 자유롭지 않습니다: $9$ 번의 이동 뒤 덩어리는 반드시 전체 $[1, 10]$ 이어야 합니다.
이동 중 왼쪽이 $k$ 개, 오른쪽이 $9 - k$ 개면 덩어리는 $[\text{시작} - k,\ \text{시작} + (9 - k)] = [1, 10]$ 에서 끝나므로 $\text{시작} = k + 1$ 로 정해집니다.
따라서 $9$ 번 이동 문자열 하나하나가 정확히 유효한 나열 하나를 주고, 유효한 나열 하나하나가 정확히 문자열 하나를 줍니다 — 완벽한 일대일 대응입니다.

$$\text{유효한 나열} \;\longleftrightarrow\; \{L, R\} \text{ 의 } 9 \text{ 번 이동 문자열}, \quad \text{시작} = (\#L) + 1$$

💡 나열을 세지 말고 왼쪽/오른쪽 결정을 세세요 — 시작 수는 저절로 정해집니다.

#2 빠짐없이 나열하기 7.SP.C.8 단계 4

이동 문자열 세기

이제 질문은 단 하나입니다: 두 글자 $L$ 과 $R$ 로 만든 길이 $9$ 의 문자열은 몇 개일까요?
$9$ 개의 각 자리를 독립적으로 $2$ 가지 중 하나로 채우므로, 곱셈 원리에 의해 총수는 $2$ 를 아홉 번 곱한 $2 \times 2 \times \dots \times 2$ 입니다.

$$\underbrace{2 \times 2 \times \cdots \times 2}_{9 \text{ 개}} = 2^{9}$$

💡 아홉 번의 독립적인 두 갈래 갈림길이 곱해져 $2^9$ 가지가 됩니다.

#3 가능성 지우기 6.EE.A.1 단계 5

계산하고 선택지 고르기

$2^9 = 512$ 를 계산합니다.
선택지 중 $512$ 만 나타나므로 나머지 — $120$, $1024$, $181{,}440$, $362{,}880$ — 는 모두 배제됩니다.
유효한 나열은 $512$ 가지, 즉 선택지 $\textbf{(B)}$ 입니다.

$$2^{9} = 512 \;\Rightarrow\; \textbf{(B)}$$

💡 깔끔한 $2$ 의 거듭제곱 $2^9$ 이 정확히 한 선택지에 딱 맞습니다.

[1] #9 4.OA.C.5 $10$ 을 작은 $n$ 으로 바꿔 손으로 셉니다. $n = 2$ 일 때 $(1,2)$ 와 $(2,1)$ 둘 다 되므로 $2$ 가지. $n =

[2] #1 6.NS.C.6 이미 적은 값들을 수직선 위의 점으로 그려 봅니다. 첫 수는 점 하나입니다. 이후의 모든 수는 이미 놓인 점 옆에 붙어야 하므로, 현재 무리의

[3] #16 7.SP.C.8 덩어리는 매번 정확히 한 칸씩 — 왼쪽($L$) 또는 오른쪽($R$) — 자라므로, 한 나열은 그 시작 값과 뒤이은 $9$ 번의 이동(각각 $L

[4] #2 7.SP.C.8 이제 질문은 단 하나입니다: 두 글자 $L$ 과 $R$ 로 만든 길이 $9$ 의 문자열은 몇 개일까요? $9$ 개의 각 자리를 독립적으로 $2$

[5] #3 6.EE.A.1 $2^9 = 512$ 를 계산합니다. 선택지 중 $512$ 만 나타나므로 나머지 — $120$, $1024$, $181{,}440$, $362{

검토

합리성 확인: 작은 경우들이 들어맞습니다: $2^{2-1} = 2$, $2^{3-1} = 4$, $2^{4-1} = 8$ 이 손 계산과 일치했으니 $2^{10-1} = 512$ 도 같은 규칙에 맞습니다. 두 번째 확인: 강제된 시작 값에 대해 합하면 $\sum_{k=0}^{9} \binom{9}{k} = 2^9$ ($9$ 번 이동 중 왼쪽인 것을 고르는 방법), 역시 같은 $512$. 오답은 함정입니다: $1024 = 2^{10}$ 은 시작을 별도의 자유 선택으로 취급해 과다 계산한 것이고, $362{,}880 = 9!$ 과 $181{,}440 = 9!/2$ 는 이웃 규칙이 허용하는 것보다 훨씬 많은 자유를 상상한 값입니다.

대안 접근: 재귀(도구 #9 재사용). $\{1, \dots, n\}$ 의 어떤 유효한 나열이든 마지막에 적히는 수는 $1$ 또는 $n$ 이어야 합니다. 최종 덩어리가 $[1, n]$ 이고 끝만 마지막에 붙을 수 있기 때문입니다. 그 수를 지우면 크기 $(n-1)$ 짜리 유효한 나열이 남고, 거꾸로 각 짧은 나열은 정확히 $2$ 가지로 확장됩니다(새로운 최솟값 또는 최댓값을 붙임). 따라서 $f(1) = 1$ 과 함께 $f(n) = 2\,f(n-1)$ 이고, 곧바로 $f(10) = 2^9 = 512$ 를 얻습니다.

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

4.OA.C.5 주어진 규칙을 따르는 수 또는 도형 패턴 만들기 (작은 경우 $n = 2, 3, 4$ 를 $2, 4, 8$ 로 세어 두 배 패턴 $2^{\,n-1}$ 을 발견.)
6.NS.C.6 유리수를 수직선 위의 한 점으로 이해하기 (적힌 값들을 수직선 위의 점으로 그려, 그것들이 항상 끝에서만 자라는 끊김 없는 한 덩어리 $[L, R]$ 를 이룸을 확인.)
7.SP.C.8 정리된 목록·표·모의실험으로 복합 사건의 확률 구하기 (각 나열을 $9$ 번의 독립적인 왼쪽/오른쪽 이동 문자열로 재해석하고 곱셈 원리를 적용해 $2^9$ 을 얻음.)
6.EE.A.1 자연수 지수를 포함한 수식을 쓰고 계산하기 ($2^9 = 512$ 를 계산해 선택지 (B) 를 확인.)

⭐ 규칙이 덩어리의 왼쪽 끝이나 오른쪽 끝에만 덧붙이게 한다면, 수는 잊고 왼쪽/오른쪽 선택만 세세요 — 여기서는 그것이 겁나는 순서 문제를 $2^9 = 512$ 로 바꿔 줍니다.