AMC 10 · 2012 · #20

학년 8 algebra

유형 Small-Domain Constrained Search └ 세부 유형 Sum-Target Search

base-conversionexponentsfundamental-counting-principlecomplementary-counting identify-subproblemseasier-related-problemcomplementary-counting ↑ 선수 지식: base-conversionexponents

📏 긴 풀이 💡 4 개 인사이트

문제

긴 괄호의 곱을 전개하고 특정한 거듭제곱 항 하나를 골라낸다. 그 계수의 지수를 구하여라.

답을 골라 클릭하세요.

(A)

(B)

(C)

(D)

(E)

풀이 과정

전략 다르게 정리하기

2048개의 항을 손으로 곱할 수는 없으니 실제 일은 도구 #15(다르게 정리하기)가 한다. 전개의 각 항에 "어느 괄호들이 x항을 내놓았는가"라는 집합으로 이름을 붙이는 것이다. 이 하나의 재정리가 "거대한 곱을 전개하라"를 "합이 2012가 되도록 서로 다른 2의 거듭제곱들을 골라라"로 바꾼다. 도구 #9(더 쉬운 문제로 줄이기)로 앞의 세 괄호만 손으로 전개해 아이디어를 시험한다. 위험한 대목은 "2012에 이진 표현이 있다"에서 곧장 "그러니 계수는 이 곱 하나다"로 건너뛰는 것이다. 그것은 x²⁰¹²을 만드는 선택이 오직 하나뿐임을 슬쩍 가정하는 셈이고, 만약 두 선택이 있었다면 두 기여가 더해져 계수가 2의 거듭제곱일 이유가 없어진다. 도구 #7(작은 문제로 쪼개기)이 이 구멍을 막는다. 괄호를 하나씩 붙여 가며 두 조각이 서로 겹치지 않는 지수 구간을 차지함을 보이면, 0부터 2047까지 모든 지수가 정확히 한 번씩 나타남이 증명된다. 그 뒤에야 도구 #11(거꾸로 풀기)로 2012에서 2의 거듭제곱을 벗겨 내 선택을 찾고, 도구 #16(관점 바꾸기)으로 고르지 않은 괄호들을 본다. 계수를 만드는 것은 고른 쪽이 아니라 바로 그쪽이기 때문이다.

1STEP 1

각 항에 선택으로 이름 붙이기

각 항은 어느 괄호를 골랐는지로 이름 붙는다.

P(x)=Σ_{S⊆{0,…,10}}(Π_k∉ S2^k)x^Σ_k∈ S2^k=Σ_S2^(Σ_k∉ Sk)x^(Σ_k∈ S2^k)

2STEP 2

괄호 세 개로 예행연습

괄호 셋이면 패턴이 보인다.

(x+1)(x²+2)(x⁴+4)=x⁷+x⁶+2x⁵+2x⁴+4x³+4x²+8x+8

3STEP 3

두 선택이 겹치지 않음을 증명하기

두 선택은 결코 겹치지 않는다.

deg P_m=2^m+1-1 ＜ 2^m+1이므로 구간 [0, 2^m+1-1]과 [2^m+1, 2^m+2-1]은 겹치지 않는다

4STEP 4

고른 괄호를 거꾸로 찾기

이진 표기가 고른 괄호를 알려 준다.

2012=1024+512+256+128+64+16+8+4=11111011100₂

5STEP 5

넘긴 괄호들을 보기

넘긴 괄호가 상수를 내놓는다.

2047-2012=35=32+2+1=2⁵+2¹+2⁰

6STEP 6

남은 상수들 곱하기

그것을 곱하면 지수가 6이다.

1 · 2 · 32=2⁰ · 2¹ · 2⁵=2⁰⁺¹⁺⁵=2⁶=64, 따라서 a=6 → (B)

7STEP 7

다항식의 양 끝에서 확인하기

다항식의 양 끝이 그것을 확인한다, 보기 (B).

0+1+2+…+10=55이고, 1 · 2 · 4… 1024=2⁵⁵

정답

a=6은 넘긴 세 자리 번호의 합 0+1+5이고, 계수 자체도 32 · 2 · 1=64=2⁶이므로 두 읽기가 일치한다. 추가 확인 세 가지. 첫째, 자릿수 세기: 2012=11111011100₂은 자리 k=0,…,10의 11칸 중 1이 여덟 개, 0이 세 개이며, 이는 여덟 괄호가 x를, 세 괄호가 상수를 내놓은 것과 맞는다. 둘째, 범위: a는 0(모든 x를 고름)과 55(모든 상수를 고름) 사이여야 하는데 6은 그 안에 넉넉히 들어간다. 셋째, 오답들은 이 방법이 피해 가는 실수 그 자체다. 5는 넘긴 자리 중 가장 큰 2⁵만 쓰고 2와 1을 잊었을 때 나오고, 10은 가장 큰 괄호의 자리 번호인데 이것은 계수에 아예 들어오지 않는다. 계수가 2의 거듭제곱이라는 것도 여기서는 가정이 아니다. 3단계에서 x²⁰¹²을 만드는 선택이 하나뿐임을 증명했기에, 서로 다른 항들이 더해져 이를 망가뜨릴 수 없다.

💡핵심 정리

원하는 지수를 이진법으로 써 보라. 1은 어느 괄호가 x를 내놓았는지, 0은 어느 괄호가 상수를 내놓았는지 말해 준다. 그리고 두 선택이 같은 지수를 만들 수 없으므로, 계수는 그냥 2를 0이 있는 자리 번호들의 합만큼 거듭제곱한 값이다 — 여기서는 0+1+5=6.

각 항에 선택으로 이름 붙이기
괄호 세 개로 예행연습
두 선택이 겹치지 않음을 증명하기
고른 괄호를 거꾸로 찾기
넘긴 괄호들을 보기
남은 상수들 곱하기
다항식의 양 끝에서 확인하기