AMC 10 · 2018 · #5

학년 7 number-theory

유형 Overlap / Complement Counting └ 세부 유형 Complement by Subtracting Forbidden Arrangements

prime-numberscombinations-basicexponents complementary-countingsystematic-enumeration ↑ 선수 지식: prime-numberscombinations-basic

📏 중간 풀이 💡 2 개 인사이트

문제

8개의 원소를 가진 집합 {2,3,4,5,6,7,8,9}의 부분집합 중에서 소수를 적어도 하나 포함하는 것이 몇 개인지 센다.

답을 골라 클릭하세요.

(A)

$text{ 128}$

(B)

$text{ 192}$

(C)

$text{ 224}$

(D)

$text{ 240}$

(E)

$text{ 256}$

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

풀이 과정

전략 관점 바꾸기

도구 #16 (관점 바꾸기): "소수를 적어도 하나"는 부분집합이 소수를 한 개, 두 개, 세 개, 네 개 가질 수 있어 직접 세기 까다롭다. 반대 사건인 "소수가 하나도 없음"은 깔끔한 한 가지 경우이므로, 그것을 세서 전체에서 빼면 된다. 도구 #2 (빠짐없이 나열하기): 먼저 여덟 수를 소수와 합성수로 분류해 각각 몇 개인지 정확히 파악한다. 도구 #3 (가능성 지우기): 결과는 다섯 보기 중 하나여야 하므로 240을 확인하고 나머지를 배제할 수 있다.

1STEP 1

소수와 합성수로 분류

여덟 수를 표시하면 2,3,5,7은 소수, 4,6,8,9는 합성수이므로 소수 4개와 합성수 4개다.

소수={2,3,5,7}, 합성수={4,6,8,9}

2STEP 2

여사건으로 뒤집기

소수가 든 부분집합을 직접 세는 대신 반대를 센다: (소수 적어도 하나) = (전체) - (소수 없음).

#(소수 적어도 하나) = #(전체) - #(소수 없음)

3STEP 3

모든 부분집합 세기

여덟 수 각각이 독립적으로 들어가거나 빠지므로 2가지 선택을 곱하면 전체 2⁸ = 256개다.

2⁸ = 256 (전체 부분집합)

4STEP 4

소수 없는 부분집합 세기

소수 없는 부분집합은 합성수 {4,6,8,9} 4개만 쓰므로 2⁴ = 16개다(공집합 포함).

2⁴ = 16 (소수 없는 부분집합)

5STEP 5

빼서 마무리

전체에서 소수 없는 부분집합을 빼면 256 - 16 = 240, 즉 보기 (D)이다.

256 - 16 = 240 → (D)

정답

text{ 240}

답 240은 전체 256보다 조금 작은데, 이는 타당하다: 모든 부분집합 중 16개만 소수를 전부 피하므로 대다수는 소수를 적어도 하나 포함해야 한다. 소수 4개와 합성수 4개로 균형이 맞고, 2⁸ - 2⁴ = 256 - 16 = 240은 정확하다. 보기 (A) 128과 (B) 192는 너무 작고, (E) 256은 공집합까지 포함해 모든 부분집합을 잘못 세며, (C) 224 = 256 - 32는 합성수를 2⁵로 잘못 계산한 것이다 — 오직 (D)만 맞는다.

💡핵심 정리

"적어도 하나"의 소수를 가진 부분집합을 세려면, 전체 2⁸ = 256개에서 합성수만 쓰는 2⁴ = 16개를 빼면 240이 나온다.

소수와 합성수로 분류
여사건으로 뒤집기
모든 부분집합 세기
소수 없는 부분집합 세기
빼서 마무리

소수와 합성수로 분류

여사건으로 뒤집기

모든 부분집합 세기

소수 없는 부분집합 세기

빼서 마무리

비슷한 유형 더 풀어보기