AMC 10 · 2022 · #22

학년 8 arithmetic

combinations-basiccomplementary-countingpattern-recognition easier-related-problemcomplementary-countingpattern-recognition ↑ 선수 지식: combinations-basic

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

문제

Suppose that $13$ cards numbered $1, 2, 3, \ldots, 13$ are arranged in a row. The task is to pick them up in numerically increasing order, working repeatedly from left to right. In the example below, cards $1, 2, 3$ are picked up on the first pass, $4$ and $5$ on the second pass, $6$ on the third pass, $7, 8, 9, 10$ on the fourth pass, and $11, 12, 13$ on the fifth pass. For how many of the $13!$ possible orderings of the cards will the $13$ cards be picked up in exactly two passes?

$\textbf{(A) } 4082 \qquad \textbf{(B) } 4095 \qquad \textbf{(C) } 4096 \qquad \textbf{(D) } 8178 \qquad \textbf{(E) } 8191$

답을 골라 클릭하세요.

(A)

4082

(B)

4095

(C)

4096

(D)

8178

(E)

8191

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: $13$ 장의 카드 $1, 2, \ldots, 13$ 을 한 줄로 놓고, 각 패스마다 왼쪽에서 오른쪽으로 훑으며 "이번 패스에서 직전에 집은 카드보다 오른쪽에 있는, 아직 안 집은 가장 작은 번호" 를 차례로 집습니다. $13!$ 가지 배열 중 정확히 두 패스에 끝나는 배열의 수는?

주어진 것: 한 줄에 $1, 2, \ldots, 13$ 카드 $13$ 장; 패스 규칙: 좌→우 훑기, 이번 패스 직전 카드보다 오른쪽에 있는 가장 작은 미수집 카드를 집기; 전체 배열 수: $13!$; 선택지: (A) $4082$, (B) $4095$, (C) $4096$, (D) $8178$, (E) $8191$

구하는 것: 정확히 두 패스에 끝나는 배열의 수

이해

계획

주요 도구: #9 더 쉬운 문제로 줄이기

보조 도구: #2 빠짐없이 나열하기, #5 패턴 찾기, #16 관점 바꾸기, #3 가능성 지우기

도구 #9(더 쉬운 문제) 와 #2(빠짐없이 나열) 로 $n = 2, 3, 4$ 카드에 대해 모든 순열을 직접 나열해 패스 수를 셉니다. 데이터 점들이 공식 $2^n - n - 1$ 에 맞습니다(도구 #5). 왜? 도구 #16(관점 바꾸기): 패스 1 은 초기 구간 $\{1, \ldots, k\}$ 만 수집하고, 배열이 $\le 2$ 패스로 끝나는 것은 $\{1, \ldots, k\}$ 와 $\{k+1, \ldots, 13\}$ 이 각각 위치 오름차순 — 즉 두 증가 부분열의 셔플 — 인 것과 동치. 그러면 각 $k$ 마다 $\binom{13}{k}$ 개씩 있지만, 부분집합 단위로 세면 $2^{13}$ 으로 합쳐지고 정렬된 순열만 여러 번 중복 셈됩니다. 도구 #3 로 크기 $\approx 8000$ 의 답을 골라냅니다.

실행 — 정답: D

#9 더 쉬운 문제로 줄이기 3.OA.D.9 단계 1

$n = 2$ 시도.
배열은 $12$(한 패스) 와 $21$(두 패스), 두 패스 개수 $= 1$.

$$n=2: \text{두 패스} = 1 = 2^2 - 2 - 1$$

💡 3학년 — 아주 작은 경우로 규칙의 감을 잡습니다.

#2 빠짐없이 나열하기 4.OA.C.5 단계 2

$n = 3$ 시도.
$6$ 개 순열을 모두 시뮬레이션.
$123$: 한 패스.
$132$: 패스 1 에서 $1, 2$, 패스 2 에서 $3$ — 두 패스.
$213$: 패스 1 에서 $1$, 패스 2 에서 $2, 3$ — 두 패스.
$231$: 패스 1 에서 $1$, 패스 2 에서 $2, 3$ — 두 패스.
$312$: 패스 1 에서 $1, 2$, 패스 2 에서 $3$ — 두 패스.
$321$: 패스 1 에서 $1$, 패스 2 에서 $2$, 패스 3 에서 $3$ — 세 패스.
두 패스 개수 $= 4 = 2^3 - 3 - 1$.

$$n=3: \text{두 패스} = 4 = 2^3 - 3 - 1$$

💡 4학년 — 규칙대로 모두 나열해 세기; 두 데이터 점만으로도 $2^n - n - 1$ 패턴이 보입니다.

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

일반화.
임의의 배열에서 패스 1 은 정확히 $\{1, 2, \ldots, k\}$ 를 수집합니다 ($k$ = 카드 $1, 2, \ldots, k$ 가 줄에서 위치 순으로 나타나는 가장 큰 $k$).
패스 2 가 $\{k+1, \ldots, 13\}$ 을 한 번에 끝내려면 그들의 위치도 오름차순이어야 합니다.
따라서 "최대 두 패스" $\Leftrightarrow$ "배열이 두 증가 부분열 $\{1, \ldots, k\}$ 와 $\{k+1, \ldots, 13\}$ ($0 \le k \le 13$ 의 어떤 $k$) 의 셔플".

$$\le 2 \text{ 패스} \Leftrightarrow \text{두 부분열 모두 위치 오름차순}$$

💡 7학년 — 집기 과정을 순열의 구조적 성질로 다시 쓰기.

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

$n = 13$ 에서 "최대 두 패스" 를 셉니다.
"낮은" 카드들을 놓을 위치 집합 $A \subseteq \{1, \ldots, 13\}$ 을 정하면, 낮은 카드 $\{1, \ldots, |A|\}$ 는 $A$ 에 오름차순으로, 나머지 카드 $\{|A|+1, \ldots, 13\}$ 는 보집합에 오름차순으로 — 각 부분집합당 유일한 배열.
따라서 부분집합으로 센 총수 $= 2^{13} = 8192$.

$$\#(\text{부분집합}) = 2^{13} = 8192$$

💡 7학년 — 낮은 카드들의 위치 부분집합 하나가 유효 배열 하나에 대응.

#5 패턴 찾기 8.EE.A.1 단계 5

중복 카운트 정리 후 한 패스 빼기.
서로 다른 부분집합이 같은 순열을 주는 경우는 그 순열이 완전히 정렬된 $(1, 2, \ldots, 13)$ 일 때뿐 — 정렬 순열은 모든 접두사 $A = \{1, \ldots, k\}$ ($k = 0, 1, \ldots, 13$) 에서 만들어져 $14$ 번 중복 셈됨.
다른 $\le 2$ 패스 배열은 모두 정확히 한 번씩.
따라서 서로 다른 $\le 2$ 패스 배열 수 $= (2^{13} - 14) + 1 = 8179$.
그 중 하나(정렬 순열) 가 한 패스이므로 두 패스 수 $= 8179 - 1 = 8178$, 선택지 (D).

$$(2^{13} - 14) + 1 - 1 = 8192 - 14 = 8178 \;\Rightarrow\; \textbf{(D)}$$

💡 8학년 — $2^{13}$ 으로 시작해 정렬 순열의 중복 $13$ 회를 빼고, 한 패스 케이스(정렬 순열) 하나를 마저 뺍니다.

[1] #9 3.OA.D.9 $n = 2$ 시도. 배열은 $12$(한 패스) 와 $21$(두 패스), 두 패스 개수 $= 1$.

[2] #2 4.OA.C.5 $n = 3$ 시도. $6$ 개 순열을 모두 시뮬레이션. $123$: 한 패스. $132$: 패스 1 에서 $1, 2$, 패스 2 에서 $3$

[3] #16 7.SP.C.8 일반화. 임의의 배열에서 패스 1 은 정확히 $\{1, 2, \ldots, k\}$ 를 수집합니다 ($k$ = 카드 $1, 2, \ldots,

[4] #2 7.SP.C.8 $n = 13$ 에서 "최대 두 패스" 를 셉니다. "낮은" 카드들을 놓을 위치 집합 $A \subseteq \{1, \ldots, 13\}$

[5] #5 8.EE.A.1 중복 카운트 정리 후 한 패스 빼기. 서로 다른 부분집합이 같은 순열을 주는 경우는 그 순열이 완전히 정렬된 $(1, 2, \ldots, 13)

검토

합리성 확인: 작은 경우 점검: $n=2$ 에서 $1 = 4 - 3$, $n=3$ 에서 $4 = 8 - 4$. 공식 $2^n - n - 1$ 이 둘 다 맞고 $n=13$ 에서 $8192 - 14 = 8178$ — 선택지에 정확히 있음. $13! \approx 6.2 \times 10^9$ 에 비해 한참 작아, 두 패스 배열이 전체 중 작은 구조적 부분집합임이 맞습니다.

대안 접근: 도구 #3(가능성 지우기). $\le 2$ 패스 배열 수가 $2^{13}$ 으로 상한이고 한 패스는 단 $1$ 개라서 답이 $2^{13}$ 근처여야 함. 선택지 (A) $4082$, (B) $4095$, (C) $4096$ 는 모두 $2^{12}$ 근처로 한쪽 분기만 셈한 형태 — 제외. (E) $8191 = 2^{13} - 1$ 은 한 번만 빼서 과대 셈. 오직 (D) $8178 = 2^{13} - 14$ 만 "$2^{13}$ 에서 작은 보정" 조건을 만족.

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

3.OA.D.9 산술 패턴 식별하고 연산의 성질로 설명 (가장 작은 경우 $n=2$ 를 손으로 시도해 집기 규칙의 감을 잡음.)
4.OA.C.5 주어진 규칙을 따르는 수·도형 패턴 생성 ($n=3$ 의 $6$ 개 순열을 모두 나열하고 두 패스 케이스 집계.)
7.SP.C.8 정리된 목록·표·나무그림·모의실험으로 복합 사건의 확률 구하기 (낮은 카드 위치 부분집합 선택으로 배열을 카운트 — 부분집합 하나당 배열 하나.)
8.EE.A.1 정수 지수의 성질을 알고 적용해 동치 수식 만들기 ($2^{13} = 8192$ 계산과 정렬 순열의 $14$ 회 중복 카운트 보정.)

⭐ 이 AMC 10 문제는 이미 배운 8학년 $2$ 의 거듭제곱만 있으면 풀려요 — $n = 2, 3$ 을 손으로 풀어 패턴 $2^n - n - 1$ 을 찾고, $n = 13$ 에 대입해 $8192 - 14 = 8178$.