AMC 10 · 2012 · #24

학년 8 countinglogic
유형 Overlap / Complement Counting └ 세부 유형 Complement by Subtracting Forbidden Arrangements
combinations-basiccomplementary-counting casework ↑ 선수 지식: combinations-basic
📏 중간 풀이 💡 3 개 인사이트
문제
에이미, 베스, 조 세 사람이 서로 다른 노래 4곡을 각각 좋아하거나 좋아하지 않는다. 세 명 모두가 좋아하는 노래는 있을 수 없다. 또한 세 쌍의 두 사람 각각에 대해, 그 두 사람만 좋아하고 나머지 한 명은 좋아하지 않는 노래가 적어도 한 곡 있어야 한다. 이 두 조건을 모두 만족하는 좋아함/싫어함 경우의 수를 구하라.

답을 골라 클릭하세요.

(A)
108
(B)
132
(C)
671
(D)
846
(E)
1105

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

풀이 과정
전략 관점 바꾸기

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

1STEP 1

각 노래의 가능한 유형 나열

노래를 좋아하는 사람들의 집합으로 이름 붙이면, 세 명 전부는 금지라 이름표는 7가지뿐이다.

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

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

정확히 두 사람만 좋아하는 노래가 곧 그 쌍의 이름표다. 즉 4곡 중에 세 쌍 이름표가 모두 등장해야 한다.

3STEP 3

먼저 모든 이름표 배열 세기

쌍 조건을 잠시 무시하면 4곡이 각각 7가지 중 하나이므로 전체 후보는 2401가지다.

7⁴ = 2401
4STEP 4

쌍이 빠진 배열 빼기

쌍 이름표를 하나 금지하면 곡마다 선택지가 6개, 둘이면 5개, 셋이면 4개다. 포함-배제로 빠진 경우를 덜어낸다.

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

최종 합계 계산

6⁴ = 1296, 5⁴ = 625, 4⁴ = 256이므로 2401 - 3888 + 1875 - 256 = 132, 즉 (B)이다.

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

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

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

비슷한 유형 더 풀어보기

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