AMC 10 · 2007 · #25

학년 9 countingpattern

유형 Branching State Enumeration └ 세부 유형 Constrained Sequence or Path Count

recursive-sequenceset-partitioncombinations-basic easier-related-problemcaseworksystematic-enumeration ↑ 선수 지식: recursive-sequence

📏 긴 풀이 💡 4 개 인사이트

문제

연속한 세 수의 창 안에 원소가 둘 이상 들어가지 않는 부분집합을 성기다고 한다. 처음 열두 수의 성긴 부분집합의 개수를 구하여라.

답을 골라 클릭하세요.

(A)

121

(B)

123

(C)

125

(D)

127

(E)

129

풀이 과정

전략 더 쉬운 문제로 줄이기

4096개의 부분집합을 손으로 훑는 것은 불가능하고, 선택지가 2씩만 차이 나므로 어림으로는 아무것도 되지 않는다. 첫 번째 진짜 작업은 도구 #15(다르게 정리하기)가 맡는다. spacy 규칙은 연속한 세 정수 덩어리에 대해 쓰여 있는데, 이를 고른 두 수가 얼마나 떨어져 있어야 하는지에 대한 규칙으로 다시 써야 한다. 이 다시 쓰기가 문제의 경첩이다. "2 이상 떨어짐"과 "3 이상 떨어짐"의 차이가 답을 377과 129로 갈라놓는다. 일단 규칙이 간격에 대한 것이 되고 나면 그것은 순전히 국소적이다. 어디에도 12라는 수가 등장하지 않는다. 도구 #9(더 쉬운 문제로 줄이기)가 그 점을 이용한다. 작은 n에 대해 {1,…,n}에서 같은 질문을 하면 손으로 답할 수 있고, 큰 경우는 작은 경우들로부터 쌓아 올린다. 도구 #4(변수 도입하기)는 그 작은 답들에 S_n이라는 이름을 붙여 서로 연결할 수 있게 하고, 도구 #2(빠짐없이 나열하기)는 손으로 확인한 시작값들을 대고 점화식을 n=12까지 굴린다. 지켜야 할 규율은 점화식을 앞 몇 항에서 눈치로 알아내지 말고 양방향으로 증명하는 것이다.

1STEP 1

세 칸짜리 창이 간격 3이 된다

창 규칙은 사실 원소 사이의 최소 간격이다.

|S∩{n,n+1,n+2}| ≤ 1 (모든 n) ⇔ |a-b| ≥ 3 (서로 다른 모든 a,b∈ S)

2STEP 2

작은 문제들에 이름 붙이기

짧은 범위의 개수에 이름을 붙이면 점화식이 준비된다.

S_n=#{A⊆{1,…,n} : 서로 다른 모든 a,b∈ A 에 대해 |a-b| ≥ 3}, 목표는 S₁₂

3STEP 3

시작값은 손으로 나열해서

작은 경우는 손으로 나열할 수 있다.

S₀=1, S₁=2, S₂=3, S₃=4

4STEP 4

맨 위 수를 넣느냐로 가르기

가장 큰 수로 나누면 점화식이 나온다.

S_n=S_n-1+S_n-3 (n ≥ 3)

5STEP 5

점화식을 12까지 굴리기

굴려 올리면 129다.

S₀,…,S₁₂ = 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129

6STEP 6

두 번째 세기: 최댓값으로 가르기

최댓값으로 가른 두 번째 세기도 129를 확인해 준다, 보기 (E).

S₁₂=1+Σ_m=1¹²S_m-3=1+(1+1+1)+(2+3+4+6+9+13+19+28+41)=1+128=129 (E)

정답

129

선택지 다섯 개는 121,123,125,127,129로 2씩 차이 나는 홀수 사다리다. 어림이 통하지 않도록 일부러 그렇게 만든 것이므로, 유일한 방어책은 서로 독립인 정확한 세기들이 일치하는 것이다. 여기서는 셋이 일치한다. 첫째, 점화식이 S₁₂=129를 준다. 둘째, 최댓값으로 가르는 분할이 표 전체를 다른 순서로 다시 더해 역시 129를 준다. 셋째, 크기별로 세면 크기 0,1,2,3,4에 대해 1,12,45,56,15가 나오고 1+12+45+56+15=129이다. 이 중 둘은 손으로 확인할 수 있다. 크기 2에서는 작은 원소 a가 a=1,…,9에 대해 짝을 10-a개 가지므로 9+8+…+1=45이고, 크기 3에서는 가운데 원소 b가 b=4,…,9에 대해 아래로 (b-3)개, 위로 (10-b)개의 짝을 가지므로 1 · 6+2 · 5+3 · 4+4 · 3+5 · 2+6 · 1=56이다. 크기는 4로 제한되는데, 원소가 다섯이면 a₅ ≥ a₁+4 · 3 ≥ 13 ＞ 12가 되기 때문이고 크기별 개수도 이를 지킨다. 규모도 그럴듯하다. 전체 부분집합 중 129/4096≈ 3.1%만이 이렇게 빡빡한 규칙을 통과한다. 마지막으로 규칙의 해석을 일부러 검사해 보자. 만약 spacy가 "연속한 두 수만 아니면 된다"(간격 2 이상)를 뜻했다면 같은 논증이 S_n=S_n-1+S_n-2를 주어 피보나치 값 377이 나온다. 선택지에서 한참 벗어나므로 간격 3 이상이라는 해석이 의도된 것임이 확인된다.

💡핵심 정리

spacy는 결국 고른 수들이 3 이상 떨어져 있다는 뜻이므로, 가장 큰 수를 집으면 그 아래 두 자리가 지워지고 세 칸 짧아진 똑같은 퍼즐만 남는다.

세 칸짜리 창이 간격 3이 된다
작은 문제들에 이름 붙이기
시작값은 손으로 나열해서
맨 위 수를 넣느냐로 가르기
점화식을 12까지 굴리기
두 번째 세기: 최댓값으로 가르기