AMC 10 · 2008 · #19

학년 8 countingalgebra
유형 Overlap / Complement Counting └ 세부 유형 Complement by Subtracting Forbidden Arrangements
generating-functionsfundamental-counting-principlecomplementary-counting complementary-countingsystematic-enumeration ↑ 선수 지식: fundamental-counting-principle
📏 중간 풀이 💡 2 개 인사이트
문제
연속한 거듭제곱으로 이루어진 괄호 셋을 곱한다, 하나는 길고 둘은 짧다. 어떤 특정 거듭제곱의 계수를 구하여라.

답을 골라 클릭하세요.

(A)
195
(B)
196
(C)
224
(D)
378
(E)
405
풀이 과정
전략 관점 바꾸기

이 곱을 항 하나하나 전개할 필요는 없습니다. 전개란 각 괄호에서 항을 하나씩 뽑는 것이고 뽑힌 항들의 지수는 더해지므로, x²8의 계수는 결국 세 개의 적법한 지수가 28이 되는 경우의 수, 즉 개수 세기입니다. 그런데 짧은 두 괄호가 모든 것을 결정합니다. 두 지수를 정하면 긴 괄호의 지수는 자동으로 정해지기 때문입니다. 그러면 세 번 고르는 문제가 15 곱하기 15 격자 위의 쌍을 세는 문제로 바뀝니다. 격자 전체를 세는 것은 쉬우므로, 진짜 할 일은 어떤 격자점이 안 되는지를 정확히 찾아서 빼는 것입니다. 양쪽 경계를 확인하는 단계가 답을 결정하며, 이 문제의 유일한 함정도 거기에 숨어 있습니다.

1STEP 1

계수를 개수 세기로 바꾸기

계수는 사실 선택의 개수다.

x^a · x^b · x^c = x^a+b+c, 0 ≤ a ≤ 27, 0 ≤ b ≤ 14, 0 ≤ c ≤ 14
2STEP 2

짧은 두 괄호가 결정하게 하기

짧은 두 괄호가 자유롭게 고르면 긴 괄호는 강제된다.

a + b + c = 28 ⟹ a = 28 - b - c
3STEP 3

강제로 정해진 a의 양쪽 벽 확인하기

그 범위의 한쪽 끝은 저절로 만족되고 다른 쪽이 하나만 배제한다.

b+c ≤ 14+14 = 28 ⟹ a = 28-b-c ≥ 0 (항상 성립); a ≤ 27 ⇔ b+c ≥ 1 ⇔ (b,c) ≠ (0,0)
4STEP 4

격자 전체를 먼저 세기

격자 전체에 225가지 선택이 있다.

15 × 15 = 225
5STEP 5

나쁜 모서리 하나 빼기

나쁜 모서리 하나를 빼면 224, 보기 (E).

225 - 1 = 224
정답
224
서로 독립인 두 가지로 확인합니다. 첫째, 같은 모양으로 문제를 줄여 손으로 검증합니다. (1+x+x²)²(1+x+x²+x³)에서 x⁴의 계수를 묻는 문제를 봅시다. 여기서도 긴 괄호는 목표보다 한 차수 낮은 곳에서 멈춥니다. 우리 규칙의 예측은 3² - 1 = 8입니다. 직접 전개하면 (1+x+x²)² = 1+2x+3x²+2x³+x⁴이고, 차수 1부터 4까지의 항을 긴 괄호의 짝이 되는 거듭제곱과 맞추면 2+3+2+1 = 8로 일치합니다. 둘째, 원래 문제를 다른 방식으로 교차 확인합니다. (1+x+…+x¹⁴)²의 계수는 1, 2, 3, …, 15, …, 3, 2, 1이고 그 총합은 15² = 225인데, 긴 괄호는 차수 0을 제외한 모든 차수에 대해 자기가 실제로 가진 거듭제곱을 짝지어 줄 수 있으므로 다시 225 - 1 = 224가 됩니다. 함정도 짚어 둘 만합니다. 225는 x²⁷이라는 천장을 잊었을 때 나오는 수이고, 225는 의도적으로 선택지에 없습니다. 따라서 (C) 224가 일관된 값입니다.
💡핵심 정리

괄호를 전개하는 것은 각 괄호에서 항을 하나씩 뽑아 지수를 더하는 일이므로 계수는 곧 개수입니다. 짧은 두 괄호에서 나오는 225개의 쌍은 모두 되지만, 긴 괄호에게 없는 x²8을 내놓으라고 요구하는 단 하나의 쌍만 안 됩니다.

  • 계수를 개수 세기로 바꾸기
  • 짧은 두 괄호가 결정하게 하기
  • 강제로 정해진 a의 양쪽 벽 확인하기
  • 격자 전체를 먼저 세기
  • 나쁜 모서리 하나 빼기

비슷한 유형 더 풀어보기

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