AMC 10 · 2011 · #6

학년 4 arithmetic

유형 Overlap / Complement Counting └ 세부 유형 Two-Set Inclusion-Exclusion: Solve for Missing Region

set-partitionoptimizationprinciple-of-inclusion-exclusion extremal-construction ↑ 선수 지식: set-partition

📏 짧은 풀이 💡 1 개 인사이트

📘 쉬운 버전 보기 →

문제

집합 A의 원소는 20개, 집합 B의 원소는 15개이다. 두 집합을 잘 배치해서 합집합 A ∪ B의 원소 개수를 가능한 한 작게 만들 때, 그 최소 개수를 구하여라.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

300

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

풀이 과정

전략 극단의 원리

합집합을 '가장 작게' 만들라는 질문은 최소/최대를 묻는 문제이고, 이것이 바로 도구 #14 극단의 원리가 쓰이는 상황이다. 모든 배치를 하나씩 시도하는 대신, 극단으로 곧장 간다. 합집합을 줄이는 유일한 방법은 원소를 공유하는 것뿐이므로 겹치는 부분을 최대로 밀어붙인다. 벤 다이어그램(도구 #12)을 그리면 그 극단이 한눈에 보인다 — B의 원을 A의 원 안으로 완전히 밀어 넣어 밖으로 삐져나오지 않게 한다. 그다음은 세기만 하면 된다.

1STEP 1

겹침을 최대로 노리기

합집합은 각 원소를 한 번만 세니 개수를 눌러 주는 건 공유 원소뿐이다. 겹침을 최대로 키우자.

|A ∪ B| = |A| + |B| - |A ∩ B| 이므로, |A ∩ B|가 클수록 합집합은 작아진다.

2STEP 2

B를 A 안으로 밀어 넣기

B의 원소는 15개뿐이라 겹침은 많아야 15이다. B의 원을 A 안에 통째로 넣으면 B는 새 원소를 더하지 않는다.

B ⊆ A → A ∩ B = B → |A ∩ B| = 15

3STEP 3

합집합 세기

B가 A 안에 들어가면 합집합은 A 전체다. 공식으로도 20 + 15 - 15 = 20, 선택지 (C).

|A ∪ B| = 20 + 15 - 15 = 20 → (C)

정답

합집합은 적어도 20이어야 한다. A의 원소 20개가 항상 그 안에 들어 있기 때문이다 — 그래서 (A) 5와 (B) 15는 너무 작아 제외된다. 두 집합이 완전히 떨어져 있을 때 합집합은 최대 20 + 15 = 35가 되는데, 이것이 선택지 (D)로 가장 '큰' 합집합이지 가장 작은 것이 아니다. 따라서 최소는 그 범위의 맨 아래인 20이고, (E) 300은 어떤 경우에도 불가능하다. 선택지 (C) 20만이 맞아떨어진다.

💡핵심 정리

합집합은 두 집합이 가장 많이 겹칠 때 가장 작아지므로, 가능한 최소 합집합은 그냥 더 큰 집합의 크기이다.

겹침을 최대로 노리기
B를 A 안으로 밀어 넣기
합집합 세기

겹침을 최대로 노리기

B를 A 안으로 밀어 넣기

합집합 세기

비슷한 유형 더 풀어보기