경시 · AMC 대비 · 4단계 중 4

AMC 10 · 2022A · #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인 경우 해 보기

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

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

n이 3인 경우 해 보기

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.

  • n이 2인 경우 해 보기
  • n이 3인 경우 해 보기
  • 규칙 일반화하기
  • 두 번 이하인 경우 세기
  • 중복과 한 번짜리 빼기

가족의 부모 대시보드는 sensimlab.com에 있습니다.