AMC 10 · 2012 · #12

학년 7 counting

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

principle-of-inclusion-exclusioncombinations-basicsymmetry-argumentconsecutive-integer-count systematic-enumerationidentify-subproblemseasier-related-problem ↑ 선수 지식: principle-of-inclusion-exclusioncombinations-basic

📏 긴 풀이 💡 3 개 인사이트

문제

한 기호 전부가 끊기지 않은 한 덩어리이거나, 다른 기호가 그렇거나, 둘 다여야 한다. 수열의 개수를 세어라.

답을 골라 클릭하세요.

(A)

190

(B)

192

(C)

211

(D)

380

(E)

382

풀이 과정

전략 빠짐없이 나열하기

"모든 0이 연속"이라는 말은 사실 자리에 대한 이야기다. 0들이 끊기지 않는 한 구간의 자리를 차지한다는 뜻이다. 그렇게 읽는 순간 수열 하나는 그 구간이 어디서 시작해 어디서 끝나는지로 완전히 정해지고, 세는 일은 덩어리를 놓는 자리를 차례로 나열하는 일이 된다. 이런 목록이 0 쪽과 1 쪽 두 개 필요하고, 두 목록에 모두 등장하는 수열은 한 번 빼야 한다. 그래서 모든 것은 겹치는 부분을 어림잡지 않고 정확히 구하는 데, 그리고 한 기호만으로 된 두 수열을 셀지 말지를 드러내놓고 정하는 데 달려 있다. 바로 그 두 수열이 보기 중 두 값을 갈라놓기 때문이다.

1STEP 1

말을 자리로 바꾸기

덩어리는 자리의 구간일 뿐이다.

{0이 놓인 자리} = {i, i+1, …, j}, 1 ≤ i ≤ j ≤ 20

2STEP 2

덩어리 길이로 나열하기

덩어리 길이로 세는 것은 단순하다.

k = 1, 2, …, 19 ⟹ 각각 21-k 가지

3STEP 3

놓는 가짓수 더하기

놓는 가짓수의 합은 209다.

20 + 19 + … + 2 = (20 · 21)/2 - 1 = 210 - 1 = 209

4STEP 4

1 쪽은 뒤집기로 공짜

기호를 바꾸면 다른 경우가 공짜로 나온다.

0 ⇔ 1 은 자기 자신이 역이다 ⟹ #{1이 연속} = #{0이 연속} = 209

5STEP 5

겹치는 부분을 정확히 못 박기

겹치는 것은 정확히 38개다.

0…0_a1…1₂₀-a 또는 1…1_a0…0₂₀-a, a = 1, …, 19 ⟹ 19 + 19 = 38

6STEP 6

두 더미를 더하고 겹친 만큼 돌려주기

더하고 돌려주면 380이다.

209 + 209 - 38 = 418 - 38 = 380

7STEP 7

한 기호뿐인 두 수열 정리하기

한 기호뿐인 경우는 제외된다, 보기 (B).

380 (두 기호 모두 필요) 대 380 + 2 = 382 (상수 수열 포함)

정답

380

자리가 4개뿐인 줄에 똑같은 논증을 돌려서 목록 전체를 손으로 확인해 보자. 0이 연속인 경우는 덩어리 길이 1, 2, 3에 대해 4 + 3 + 2 = 9개, 1이 연속인 경우도 9개, 겹치는 것은 0111, 0011, 0001, 1000, 1100, 1110으로 3 + 3 = 6개이므로 합은 9 + 9 - 6 = 12이다. 직접 세어 보면 길이 4인 수열은 16개이고 그중 두 기호를 모두 담은 것은 14개인데, 그 가운데 실패하는 것은 0101과 1010 딱 두 개라서 12개가 남는다. 두 방법이 일치한다. 자리가 n개인 줄에 같은 논증을 돌리면 2((n(n+1))/2 - 1) - 2(n-1) = n² - n = n(n-1)이 되고, n = 4에서 4 · 3 = 12, n = 20에서 20 · 19 = 380이 나온다. 이 닫힌 식은 보기들이 왜 아슬아슬하게 빗나가는지도 드러낸다. n(n-1) = 2C(20, 2) = 2 · 190이므로 190은 답의 절반이고, 211은 210 + 1로 한쪽 모음에 상수 수열을 잘못 남겨 둔 크기이며, 382는 380에 상수 수열 두 개를 더한 값이다. 규모도 말이 된다. 2²⁰ ≈ 1,048,576개 중 약 380개만 조건을 만족하는데, 끊기지 않는 덩어리 하나를 요구하는 것은 그만큼 가혹한 제한이다.

💡핵심 정리

"0이 모두 붙어 있다"는 말은 0들이 자리 한 구간을 채운다는 뜻이니, 수열을 세는 일은 그 구간이 어디서 시작해 어디서 끝나는지를 세는 일이고, 두 번 세어지는 수열은 0 덩어리 옆에 1 덩어리가 딱 붙어 있는 것들뿐이다.

말을 자리로 바꾸기
덩어리 길이로 나열하기
놓는 가짓수 더하기
1 쪽은 뒤집기로 공짜
겹치는 부분을 정확히 못 박기
두 더미를 더하고 겹친 만큼 돌려주기
한 기호뿐인 두 수열 정리하기