AMC 10 · 2022 · #22

학년 8 arithmetic

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

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

문제

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

답을 골라 클릭하세요.

(A)

4082

(B)

4095

(C)

4096

(D)

8178

(E)

8191

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

풀이 과정

전략 더 쉬운 문제로 줄이기

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

1STEP 1

작은 경우 n = 2 시도: 배열 12(한 패스), 21(두 패스) — 두 패스 개수는 1.

n=2: 두 패스 = 1 = 2² - 2 - 1

2STEP 2

n = 3: 6개 배열 중 123(한 패스)과 321(세 패스)만 빠져 두 패스 개수는 4.

n=3: 두 패스 = 4 = 2³ - 3 - 1

3STEP 3

일반화: 배열이 최대 두 패스로 끝나는 것은 {1,…,k}와 {k+1,…,13}의 두 증가 부분열의 셔플일 때뿐.

≤ 2 패스 ⇔ 두 부분열 모두 위치 오름차순

4STEP 4

낮은 카드가 들어갈 13개 위치의 부분집합마다 배열이 정확히 하나, 그래서 총 2¹³ = 8192개.

#(부분집합) = 2¹³ = 8192

5STEP 5

정렬 순열만 14번 중복 셈되고 그건 한 패스이므로, 정확히 두 패스는 8192 - 14 = 8178, 선택지 (D).

(2¹³ - 14) + 1 - 1 = 8192 - 14 = 8178 → (D)

정답

8178

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

💡핵심 정리

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