AMC 10 · 2023 · #8

학년 11 counting
유형 Casework by Position / Vertex Type └ 세부 유형 Count of Type
combinations-basicset-partitionbound-inequality-then-enumeratecasework identify-subproblemscaseworkbound-inequality-then-enumerate ↑ 선수 지식: combinations-basiccasework
📏 중간 풀이 💡 3 개 인사이트
문제
0부터 12까지의 수 중에서 비어 있지 않은 모임을 고릅니다. 모임의 원소 개수가 그 모임의 가장 작은 원소와 정확히 같아야 합니다. 그런 모임이 몇 개인지 구하세요.

답을 골라 클릭하세요.

(A)
256
(B)
136
(C)
108
(D)
144
(E)
156
풀이 과정
전략 작은 문제로 쪼개기

후보가 되는 부분집합은 2¹³개나 되므로 하나씩 확인하는 것은 손으로 할 일이 못 된다. 이 문제의 조건은 B의 두 가지 특징, 곧 크기와 가장 작은 원소를 하나로 묶어 놓았고, 도구 #4(변수 도입하기)는 그 둘을 글자 하나 k로 합쳐 준다. k에 이름이 붙고 나면 진짜 일은 도구 #7(작은 문제로 쪼개기)이 한다. 모든 부분집합은 가장 작은 원소가 정확히 하나뿐이므로, 그 값에 따라 부분집합을 나누면 서로 겹치지도 빠지지도 않는 작은 셈 몇 개로 갈라진다. 이어서 도구 #14(극단의 원리)가 k의 범위를 조인다. 가장 작은 원소가 클수록 집합도 커야 하는데, 동시에 그 위에 남는 수는 줄어들기 때문에 두 요구가 금방 충돌한다. 살아남은 각 경우 안에서는 도구 #2(빠짐없이 나열하기)가 남은 자유를 순서 없는 선택 하나로 바꾸어 주고, 그 개수는 이항계수가 세어 준다.

1STEP 1

가장 작은 원소에 이름 붙이기

개수와 최솟값이 같습니다.

k = min B = |B|, |B| ≥ 1 → k ≥ 1
2STEP 2

경우 나누기

나머지 원소는 모두 그보다 큽니다.

B = {k} ∪ C, C ⊆ {k+1, k+2, …, 12}, |C| = k - 1, |{k+1, …, 12}| = 12 - k
3STEP 3

범위 조이기

위쪽에 남는 수가 충분해야 합니다.

12 - k ≥ k - 1 ⇔ 13 ≥ 2k ⇔ k ≤ 6 (k 는 정수) → k ∈ {1, 2, 3, 4, 5, 6}
4STEP 4

조합으로 세기

각 경우를 조합으로 셉니다.

C(11, 0) = 1, C(10, 1) = 10, C(9, 2) = 36, C(8, 3) = 56, C(7, 4) = 35, C(6, 5) = 6
5STEP 5

모두 더하기

모두 더하면 144입니다.

Σ_k=1⁶ C(12-k, k-1) = 1 + 10 + 36 + 56 + 35 + 6 = 144 → (D)
정답
144
두 무더기는 손으로 직접 확인할 수 있다. k = 2인 경우 조건을 만족하는 집합은 2에서 시작하는 원소 두 개짜리 집합, 곧 {2,3}, {2,4}, …, {2,12}의 10개이고 C(10, 1)과 일치한다. k = 6인 경우에는 6을 포함해 {6, 7, …, 12}에서 여섯 개를 가져와야 하는데 이 후보는 7개뿐이므로 6보다 큰 수 여섯 개 중 정확히 하나만 빠진다. 그래서 6개가 되고 C(6, 5)와 맞는다. 문제가 준 예 {4,6,8,11}은 k = 4 무더기에 속하며, 6, 8, 11은 {5, 6, …, 12}에서 고른 세 수로서 C(8, 3) = 56가지 중 하나이다. 답의 크기도 납득이 간다. 부분집합은 모두 2¹³ = 8192개인데 조건이 매우 까다로우므로 수백 단위의 답이 자연스럽고, 선택지 (A) 256 = 2⁸은 이항계수의 합이라기보다 어디선가 잘못 나온 2의 거듭제곱처럼 보인다. 마지막으로 여섯 개의 수 1, 10, 36, 56, 35, 6은 파스칼 삼각형의 완만한 대각선 위에 놓인 값들인데, 이런 대각선의 합은 피보나치 수가 된다. 여기서는 F₁₂ = 144이므로 계산이 독립적으로 한 번 더 확인된다. 8192개의 부분집합을 전부 훑는 전수 조사도 144를 준다.
💡핵심 정리

가장 작은 원소가 스스로 이름을 정하게 하라. 가장 작은 원소가 k이면 B는 그 위에 있는 12-k개의 수 중에서 k-1개를 더 골라야 하므로, 가능한 모든 k에 대해 C(12-k, k-1)을 더하면 된다.

  • 가장 작은 원소에 이름 붙이기
  • k에 따라 경우 나누기
  • k의 범위 조이기
  • 조합으로 각 무더기 세기
  • 여섯 무더기 더하기

비슷한 유형 더 풀어보기

같은 archetype · 비슷한 학년부터.