AMC 10 · 2012 · #24

학년 8 counting

유형 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

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

풀이는 먼저 직접 풀어본 뒤에 보는 게 가장 효과적이에요.

보기 방식:

도구 + CCSS 풀이

이해

문제 재정리: 에이미, 베스, 조 세 사람이 서로 다른 노래 4곡을 각각 좋아하거나 좋아하지 않는다. 세 명 모두가 좋아하는 노래는 있을 수 없다. 또한 세 쌍의 두 사람 각각에 대해, 그 두 사람만 좋아하고 나머지 한 명은 좋아하지 않는 노래가 적어도 한 곡 있어야 한다. 이 두 조건을 모두 만족하는 좋아함/싫어함 경우의 수를 구하라.

주어진 것: 서로 다른 노래가 4곡 있다.; 각 노래는 세 사람 중 임의의 부분집합이 좋아할 수 있다.; 세 명 모두가 좋아하는 노래는 없다.; 세 쌍(에이미-베스, 베스-조, 에이미-조) 각각에 대해, 정확히 그 두 사람만 좋아하는 노래가 적어도 한 곡 있어야 한다.

구하는 것: 두 조건을 모두 만족하는, 4곡 전체에 대한 좋아함/싫어함 배열의 개수.

이해

계획

주요 도구: #16 관점 바꾸기

보조 도구: #2 빠짐없이 나열하기, #7 작은 문제로 쪼개기

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

실행 — 정답: B

#2 빠짐없이 나열하기 7.SP.C.8 단계 1

각 노래의 가능한 유형 나열

노래를 '그 노래를 좋아하는 사람들의 집합'으로 나타낸다.
세 명 모두가 좋아하는 노래는 없으므로 허용되는 집합은 공집합, 한 명짜리 집합 3개, 두 명짜리(쌍) 집합 3개뿐이다.
즉 가능한 유형은 7가지이고, 4곡 각각이 독립적으로 이 중 하나를 갖는다.

\text{7가지 유형: } \varnothing,\ \{A\},\{B\},\{J\},\ \{A,B\},\{B,J\},\{A,J\}

💡 노래를 '누가 좋아하는가'라는 이름표로 바꾸면, 애매한 좋아함/싫어함 이야기가 7개 중 하나를 고르는 깔끔한 선택이 된다.

#16 관점 바꾸기 7.SP.C.8 단계 2

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

정확히 에이미와 베스만 좋아하는 노래는 바로 유형 {A,B}인 노래이고, 다른 쌍도 마찬가지다.
따라서 '각 쌍에 그런 노래가 있다'는 조건은, 4개의 노래 이름표 중에서 세 쌍 유형 {A,B}, {B,J}, {A,J}가 각각 적어도 한 번씩 나타나야 한다는 뜻이다.
한 명짜리 유형과 공집합에는 제약이 없다.

💡 따로 놓인 세 개의 '적어도 하나' 요구가 하나의 그림으로 합쳐진다. 세 쌍 이름표가 모두 등장해야 한다는 것이다.

#7 작은 문제로 쪼개기 8.EE.A.1 단계 3

먼저 모든 이름표 배열 세기

쌍 조건을 잠시 무시하자.
4곡 각각이 7가지 유형 중 아무거나 될 수 있고 선택이 서로 독립이므로, 전체 배열은 7 x 7 x 7 x 7가지다.
이것이 앞으로 깎아 나갈 전체 후보다.

$$7^4 = 2401$$

💡 전체를 먼저 세고 나쁜 경우를 덜어내는 편이, 좋은 경우만 직접 쌓아 올리는 것보다 쉽다.

#16 관점 바꾸기 7.SP.C.8 단계 4

쌍이 빠진 배열 빼기

나쁜 사건 M1을 '유형 {A,B}가 한 번도 안 나옴'이라 하고, M2, M3를 각각 {B,J}, {A,J}에 대해 같은 방식으로 정의한다.
쌍 유형 하나를 금지하면 각 노래의 선택지가 6개로 줄어 각 나쁜 사건은 6^4가지다.
두 개를 금지하면 선택지가 5개가 되어 각 교집합은 5^4가지, 세 개를 모두 금지하면 4^4가지다.
포함-배제 원리에 따라 세 쌍 조건을 모두 만족하는 배열은 전체에서 나쁜 사건들의 합집합을 뺀 값이다.

$$7^4 - \binom{3}{1}6^4 + \binom{3}{2}5^4 - \binom{3}{3}4^4$$

💡 두 쌍이 빠진 경우는 두 번 빼지므로, 포함-배제가 그 겹침을 다시 더해 셈을 바로잡는다.

#16 관점 바꾸기 7.NS.A.3 단계 5

최종 합계 계산

거듭제곱을 계산하면 6^4 = 1296, 5^4 = 625, 4^4 = 256이다.
그러면 2401 - 3(1296) + 3(625) - 256 = 2401 - 3888 + 1875 - 256 = 132이다.
따라서 조건을 만족하는 배열은 132가지이고, 답은 (B)이다.

$$2401 - 3888 + 1875 - 256 = 132$$

💡 거듭제곱 값을 포함-배제 식에 넣으면 모든 것이 좋은 배열의 개수 하나로 정리된다.

[1] #2 7.SP.C.8 노래를 '그 노래를 좋아하는 사람들의 집합'으로 나타낸다. 세 명 모두가 좋아하는 노래는 없으므로 허용되는 집합은 공집합, 한 명짜리 집합 3개

[2] #16 7.SP.C.8 정확히 에이미와 베스만 좋아하는 노래는 바로 유형 {A,B}인 노래이고, 다른 쌍도 마찬가지다. 따라서 '각 쌍에 그런 노래가 있다'는 조건은,

[3] #7 8.EE.A.1 쌍 조건을 잠시 무시하자. 4곡 각각이 7가지 유형 중 아무거나 될 수 있고 선택이 서로 독립이므로, 전체 배열은 7 x 7 x 7 x 7가지다

[4] #16 7.SP.C.8 나쁜 사건 M1을 '유형 {A,B}가 한 번도 안 나옴'이라 하고, M2, M3를 각각 {B,J}, {A,J}에 대해 같은 방식으로 정의한다.

[5] #16 7.NS.A.3 거듭제곱을 계산하면 6^4 = 1296, 5^4 = 625, 4^4 = 256이다. 그러면 2401 - 3(1296) + 3(625) - 256

검토

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

대안 접근: 네 번째 노래에 대한 경우 나누기로 직접 셀 수도 있다. 먼저 필요한 세 쌍 유형을 네 노래 중 세 곳에 배치한다. 순서를 고려하면 4 x 3 x 2 = 24가지다. 네 번째 노래가 쌍이 아닌 유형(공집합, {A}, {B}, {J} - 4가지)이면 겹침이 없어 24 x 4 = 96가지다. 네 번째 노래가 세 쌍 유형 중 하나를 반복하면(3가지) 같은 쌍 유형을 가진 두 노래가 서로 바꿔도 같으므로 2로 나눠 24 x 3 / 2 = 36가지다. 합은 96 + 36 = 132로, 여집합 계산과 일치한다.

사용된 CCSS 표준 (최저 학년 8)

7.SP.C.8 조직적 목록을 이용한 복합 사건의 확률 (각 노래를 7가지 좋아함-집합 중 하나로 모형화하고, 포함-배제 설정을 포함해 경우의 수를 조직적으로 세기)
8.EE.A.1 정수 지수의 성질 (독립적인 노래 선택을 세는 거듭제곱 7^4, 6^4, 5^4, 4^4 계산)
7.NS.A.3 유리수의 사칙연산 (포함-배제 항들을 합쳐 최종 합계 132를 얻기)

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