AMC 10 · 2016 · #20

학년 7 algebra
유형 Small-Domain Constrained Search └ 세부 유형 Sum-Target Search
combinations-basiccombinatorial-identity easier-related-problemconvert-to-algebra ↑ 선수 지식: combinations-basic
📏 긴 풀이 💡 4 개 인사이트
문제
(a+b+c+d+1)^N을 전개하고 동류항을 모은다. 합쳐진 항들 중에서 a, b, c, d 네 변수를 모두 양의 거듭제곱으로 포함하는 항만 센다. 이 개수가 정확히 1001이 되는 특정한 N을 구하여라.

답을 골라 클릭하세요.

(A)
9
(B)
14
(C)
16
(D)
17
(E)
19

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

풀이 과정
전략 빠짐없이 나열하기

합쳐진 각 항은 N개의 인수 각각에서 a,b,c,d,1 다섯 조각 중 하나를 골라 만들어지므로, 한 항은 '각 조각을 몇 개의 인수가 내놓았는가'로 완전히 결정된다. 도구 #4(변수 도입하기)는 그 다섯 개수에 이름을 붙여 '항을 세기'를 'i+j+k+l+m=N의 음이 아닌 정수해 세기'로 바꾼다. 도구 #9(더 쉬운 문제로 줄이기)는 각 변수의 개수에서 1씩 빼서 '각 변수 최소 한 번' 조건을 없애고 모두 0 이상인 깔끔한 형태로 만든다. 도구 #2(빠짐없이 나열하기)는 별과 막대 형태로 그 해의 개수를 단번에 C(N, 4)로 센다. 마지막으로 도구 #6(추측하고 확인하기)이 C(N, 4)=1001인 N을 찾는데, 1001=7· 11· 13임을 알아차리면 쉬워진다.

1STEP 1

조건을 만족하는 한 항 묘사하기

각 인수가 a,b,c,d,1 중 하나를 내므로, 한 항은 a^ib^jc^kd^l1^m 꼴이고 지수 합은 N이다.

a^ib^jc^kd^l1^m, i+j+k+l+m=N
2STEP 2

조건을 식으로 바꾸기

항이 세어지려면 i,j,k,l이 각각 1 이상이어야 하고(m은 0 이상), 개수는 i+j+k+l+m=N의 해의 수다.

i+j+k+l+m=N, i,j,k,l ≥ 1, m ≥ 0
3STEP 3

'최소 한 번' 조건 떼어내기

a,b,c,d에 필요한 1을 먼저 주어 i'=i-1 식으로 바꾸면, 모든 변수가 0 이상이 되고 합은 N-4로 준다.

i'+j'+k'+l'+m=N-4, i',j',k',l',m ≥ 0
4STEP 4

별과 막대로 해의 개수 세기

N-4개의 별과 막대 4개를 늘어놓으면 별이 5묶음으로 나뉘고, N자리 중 막대 4자리를 고르면 C(N, 4)이다.

C((N-4)+4, 4)=C(N, 4)
5STEP 5

개수 식을 N에 대해 풀기

C(N, 4)=1001. 1001=7· 11· 13이니 N=14면 C(14, 4)=1001로 맞고, C(N, 4)은 증가만 하므로 N=14.

C(14, 4)=(14· 13· 12· 11)/24=1001 → N=14=(B)
정답
14
C(14, 4)=1001을 직접 확인한다: 14· 13· 12· 11=24024이고 24024/24=1001이다. C(N, 4)은 N에 대해 순증가하므로 다른 선택지는 맞을 수 없다: C(9, 4)=126은 너무 작고, C(16, 4)=1820, C(17, 4)=2380, C(19, 4)=3876은 모두 1001을 넘는다. 따라서 정확히 1001개를 주는 것은 N=14뿐이며, (B)가 확정되고 다른 선택지는 배제된다.
💡핵심 정리

각 항은 어떤 글자를 몇 개의 인수가 냈는지 적은 집계표이므로, 항 세기는 별과 막대로 세는 C(N, 4)이 되고, C(14, 4)=1001에서 N=14가 나온다.

  • 조건을 만족하는 한 항 묘사하기
  • 조건을 식으로 바꾸기
  • '최소 한 번' 조건 떼어내기
  • 별과 막대로 해의 개수 세기
  • 개수 식을 N에 대해 풀기

비슷한 유형 더 풀어보기

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