AMC 10 · 2022 · #19

학년 8 counting

유형 Casework by Position / Vertex Type └ 세부 유형 Count of Type

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

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

문제

번호가 붙은 카드 열세 장을 한 줄로 늘어놓습니다. 한 번 훑을 때마다 왼쪽에서 오른쪽으로 보면서, 아직 안 집은 카드 중 다음 번호가 방금 집은 카드보다 오른쪽에 있으면 집습니다. 카드를 정확히 두 번 훑어서 다 집게 되는 배열이 몇 가지인지 구하세요.

답을 골라 클릭하세요.

(A)

4082

(B)

4095

(C)

4096

(D)

8178

(E)

8191

풀이 과정

전략 더 쉬운 문제로 줄이기

도구 #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: 두 패스 = 1 = 2² - 2 - 1

2STEP 2

다음 경우로 확인하기

세 장짜리도 같은 꼴입니다.

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

3STEP 3

두 번 이하 조건 정하기

각 카드가 두 줄 중 하나에 들어갑니다.

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

4STEP 4

두 번 이하 세기

카드마다 선택이 둘이라 2의 거듭제곱입니다.

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

5STEP 5

한 번짜리 빼기

한 번짜리를 빼면 8178입니다.

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

가장 작은 경우 살펴보기

다음 경우로 확인하기

두 번 이하 조건 정하기

두 번 이하 세기

한 번짜리 빼기

비슷한 유형 더 풀어보기