AMC 10 · 2012 · #16

학년 8 countinglogic
유형 Overlap / Complement Counting └ 세부 유형 Complement by Subtracting Forbidden Arrangements
combinations-basiccomplementary-counting casework ↑ 선수 지식: combinations-basic
📏 중간 풀이 💡 3 개 인사이트
문제
어떤 것도 모두가 좋아해서는 안 되고, 모든 짝이 적어도 하나를 함께 좋아해야 한다. 배열의 수를 세어라.

답을 골라 클릭하세요.

(A)
108
(B)
132
(C)
671
(D)
846
(E)
1105
풀이 과정
전략 관점 바꾸기

세 쌍의 조건은 모두 '적어도 하나' 형태라 정면으로 세기 어렵다. 먼저 각 노래를 '그 노래를 좋아하는 사람들의 집합'으로 바꿔 표현하고 가능한 집합을 나열한다. 그다음 좋은 경우만 직접 만드는 대신 여집합으로 센다. 즉 전체 배열에서 시작해, 포함-배제 원리로 필요한 쌍이 빠진 배열을 빼 나간다.

1STEP 1

각 노래의 가능한 유형 나열

각 항목은 일곱 이름표 중 하나를 갖는다.

7가지 유형: ∅, {A},{B},{J}, {A,B},{B,J},{A,J}
2STEP 2

쌍 조건을 '모두 등장' 조건으로 바꾸기

짝 조건은 세 이름표가 모두 나와야 한다는 뜻이다.

3STEP 3

먼저 모든 이름표 배열 세기

모든 배열을 세는 것은 쉽다.

7⁴ = 2401
4STEP 4

쌍이 빠진 배열 빼기

빠진 경우를 빼면 부호가 번갈아 나온다.

7⁴ - C(3, 1)6⁴ + C(3, 2)5⁴ - C(3, 3)4⁴
5STEP 5

최종 합계 계산

합계는 132, 보기 (B).

2401 - 3888 + 1875 - 256 = 132
정답
132
132는 제약 없는 배열 2401보다 훨씬 작은데, 세 쌍 유형이 모두 나타나야 한다는 강한 제약을 생각하면 자연스럽다. 또한 세 쌍 유형을 세 노래에 앉히는 24가지보다는 넉넉히 큰데, 네 번째 노래가 선택지를 몇 개씩 더해 주기 때문이다. 보기 중 이 범위에 드는 것은 (B) 132뿐이며, 671, 846, 1105 같은 큰 값은 사실상 제약이 거의 없어야 나온다.
💡핵심 정리

'각각 적어도 하나'를 요구하는 문제에서는 전체 배열을 먼저 세고, 무언가 빠진 경우를 빼면 된다.

  • 각 노래의 가능한 유형 나열
  • 쌍 조건을 '모두 등장' 조건으로 바꾸기
  • 먼저 모든 이름표 배열 세기
  • 쌍이 빠진 배열 빼기
  • 최종 합계 계산

비슷한 유형 더 풀어보기

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