AMC 10 · 2006 · #25

학년 11 counting

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

combinations-basicstars-and-barssystematic-enumeration caseworkidentify-subproblems ↑ 선수 지식: combinations-basic

📏 긴 풀이 💡 4 개 인사이트

문제

처음 열다섯 개 수의 부분집합에서 어느 두 원소도 연속하지 않고, 모든 원소가 원소의 개수 이상이다. 공집합이 아닌 부분집합의 개수를 구하여라.

답을 골라 클릭하세요.

(A)

277

(B)

311

(C)

376

(D)

377

(E)

405

풀이 과정

전략 변수 도입하기

걸림돌은 조건 (2)가 k=|S| 를 가리킨다는 점이다. 그래서 두 규칙을 전체 집합족에 어떤 순서로도 한꺼번에 적용할 수 없다. 도구 #7(작은 문제로 쪼개기)이 이 걸림돌을 한 수에 치운다: 집합족을 크기별로 자른다. 한 집합의 크기는 하나뿐이므로 잘린 조각들은 서로 겹치지 않고 빠짐도 없으며, 조각 안에서 k 는 상수가 되어 조건 (2)가 "모든 원소가 k 이상"이라는 평범한 문장으로 바뀐다. 그다음 진짜 일은 도구 #4(변수 도입하기)가 한다. 남은 두 조건은 모두 여유 공간에 관한 것이다 — 첫 원소 아래의 공간, 이웃 사이의 공간. 그러니 원소가 어디에 있는지를 추적하는 대신 각 틈에 남은 여유를 이름 붙인다. 이 변수 교체 하나가 두 조건을 모두 "모든 변수가 음이 아니다"로 바꾸고, 여유의 총합이 항상 17-3k 라는 깔끔한 항등식을 낳는다. 도구 #11(거꾸로 풀기)은 여기서 장식이 아니다. 변수 교체를 개수 세기에 쓰려면 그것이 일대일 대응이어야 하므로, 구성을 거꾸로 돌려 되살린 부분집합에서 모든 규칙을 다시 확인한다. 유효한 부분집합을 어딘가로 보내기만 하는 사상은 개수가 아니라 부등식만 준다. 이어서 도구 #14(극단의 원리)가 여유 항등식에서 k 의 범위를 곧바로 읽어 낸다 — 여유는 음수가 될 수 없다 — 이것이 "가장 빽빽한 배치"를 눈대중하는 것보다 정직하다. 그 그림 자체가 증명을 필요로 하기 때문이다. 마지막으로 도구 #15(다르게 정리하기)가 여유 배분을 단위와 칸막이의 배열로 다시 적어 세고, 검토 단계에서 이 재해석을 한 걸음 더 밀면 다섯 경우가 하나의 점화식으로 접히면서 완전히 다른 경로로 총합이 확인된다.

1STEP 1

세기 전에 크기부터 고정하기

개수를 먼저 고정해야 둘째 규칙을 쓸 수 있다.

N=Σ_k ≥ 1|A_k|, A_k={S⊆{k,k+1,…,15} : |S|=k, 연속한 원소 없음}

2STEP 2

원소가 아니라 틈을 재기

원소 대신 틈을 재면 두 규칙이 모두 흡수된다.

b₁=a₁-k, b_i=a_i-a_i-1-2 (2 ≤ i ≤ k), b_k+1=15-a_k; b₁+b₂+…+b_k+1=(a₁-k)+(a_k-a₁-2(k-1))+(15-a_k)=17-3k

3STEP 3

여유로부터 부분집합을 되살리기

그 틈으로 부분집합을 되살릴 수 있어 잃는 것이 없다.

a₁=k+b₁ ≥ k, a_i=a_i-1+2+b_i (2 ≤ i ≤ k) → a_i-a_i-1 ≥ 2, a_k=15-b_k+1 ≤ 15

4STEP 4

예산이 가능한 크기를 정한다

남는 여유가 예산이고 음수가 되면 안 된다.

17-3k ≥ 0⇔ k ≤ 17/3⇔ k ≤ 5, k∈{1,2,3,4,5}

5STEP 5

여유를 나누는 방법 세기

그것이 개수를 다섯으로 제한한다.

|A_k|=C(m+k, k)=C((17-3k)+k, k)=C(17-2k, k)

6STEP 6

다섯 경우를 더하기

예산을 나누면 개수마다 이항계수가 하나씩 나오고 합은 405, 보기 (E).

N=Σ_k=1⁵C(17-2k, k)=C(15, 1)+C(13, 2)+C(11, 3)+C(9, 4)+C(7, 5)=15+78+165+126+21=405 → (E)

정답

405

먼저 다섯 항 중 둘을 공식 없이 다시 구해, 공식을 믿는 대신 시험해 보자. k=2 에서 유효한 부분집합은 a₁ ≥ 2, a₂ ≥ a₁+2, a₂ ≤ 15 인 짝 a₁ ＜ a₂이다. a₁이 2부터 13까지 각각에 대해 a₂의 선택은 15-(a₁+2)+1=14-a₁ 가지이고, 12+11+10+…+1=78로 C(13, 2)와 일치한다. k=5 에서 예산은 17-15=2 이므로 여유는 6 개의 틈 중 하나에 2 단위가 몰리거나(6 가지) 서로 다른 두 틈에 1 단위씩 가거나(C(6, 2)=15 가지) 둘 중 하나이고, 합쳐서 21로 C(7, 5)와 일치한다. 다음으로 답을 위아래로 묶어 보자. 유효한 부분집합은 특히 연속한 원소가 없는 공집합 아닌 부분집합이고 그런 것은 F₁₇-1=1597-1=1596 개다. 또 15 개의 한원소 집합은 모두 유효하다. 따라서 답은 15와 1596 사이에 엄격히 놓여야 하는데 405는 그 안에 있고, 제한 없는 개수의 약 1/4이다. 조건 (2)가 작은 부분집합에는 무해하고 큰 부분집합에는 치명적이라는 점을 생각하면 그럴듯하다. 이제 정보가 담긴 오답들을 보자. 조건 (2)를 "k 이하의 수를 포함하지 않는다"로 잘못 읽으면 바닥이 k 가 아니라 k+1이 되어 예산이 17-3k 에서 16-3k 로 떨어지고 개수는 Σ_k ≥ 0C(16-2k, k)=1+14+66+120+70+6=277, 정확히 선택지 (A)가 된다 — 예산 한 칸이 어긋났고 공집합 경우까지 남겨 둔 결과다. 선택지 (C) 376과 (D) 377은 피보나치 미끼다. "연속하지 않기"는 피보나치 개수 문제로 유명하고 377=F₁₄는 풀이자가 외고 있을 피보나치 수 한복판에 있다. 그러나 원소 15 개짜리 전체집합에 실제로 대응하는 피보나치 수는 F₁₇=1597 이므로, 377 근처의 답은 지표도 잘못 짚었고 조건 (2)도 통째로 무시한 것이다. 정답은 피보나치 수가 아니고, 그래서도 안 된다.

💡핵심 정리

원소를 하나 넣을 때마다 공간 세 칸이 든다 — 한 칸은 바닥을 올리고 두 칸은 앞 원소와의 거리를 지킨다 — 그래서 예산이 17로 정해지면 남는 문제는 남은 여유를 틈들에 어떻게 뿌릴 것인가뿐이다.

세기 전에 크기부터 고정하기
원소가 아니라 틈을 재기
여유로부터 부분집합을 되살리기
예산이 가능한 크기를 정한다
여유를 나누는 방법 세기
다섯 경우를 더하기