AMC 10 · 2005 · #20

학년 9 algebracounting

유형 Branching State Enumeration └ 세부 유형 Numeric Operation Tree

function-compositionrecursive-sequenceexponents work-backwardseasier-related-problempattern-recognition ↑ 선수 지식: function-compositionfunction-evaluationexponents

📏 긴 풀이 💡 3 개 인사이트

문제

어떤 함수가 구간을 자기 위로 접는데, 왼쪽 절반에서는 값을 두 배로, 오른쪽에서는 오른쪽 끝까지의 거리를 두 배로 만든다. 이 함수를 2005번 연달아 적용한다. 중점에 도착하는 시작값의 개수를 구하여라.

답을 골라 클릭하세요.

(A)

(B)

2005

(C)

4010

(D)

$2005^2$

(E)

$2^{2005}$

풀이 과정

전략 거꾸로 풀기

f를 앞으로 2005번 굴리는 것은 불가능하지만 도착점은 정확히 알고 있다. 한 단계 전에 무엇이 1/2을 만들 수 있었는지 묻는 순간 문제는 역상(preimage) 세기의 반복으로 바뀌고, 한 단계 뒤로 갈 때의 개수는 어느 단계에서나 같다. 작은 경우 n=1, n=2가 그 개수를 드러내고, 텐트 모양 그래프가 그 이유를 설명한다.

1STEP 1

출력이 구간 안에 머무는지 확인

규칙이 구간을 자기 안으로 보내므로 모든 반복이 정의된다.

f([0,1]) = [0,1]

2STEP 2

목표를 역상 문제로 바꾸기

거꾸로 가면 문제가 역상의 사슬이 된다.

S_n+1 = { x ∈ [0,1] : f(x) ∈ S_n }

3STEP 3

내부 값마다 근원은 두 개

내부의 각 값은 가지마다 하나씩 정확히 두 근원을 가진다.

f(x) = y ⇔ x = y/2 또는 x = 1 - y/2, 0 ＜ y ＜ 1

4STEP 4

처음 두 단계는 손으로

처음 두 회에 값이 2개, 다음 4개가 된다.

S₁ = { 1/4, 3/4 }, S₂ = { 1/8, 3/8, 5/8, 7/8 }

5STEP 5

두 배 규칙이 깨지지 않음을 증명

귀납으로 모든 값이 안쪽에 머물러 두 배 규칙이 깨지지 않는다.

|S_n+1| = 2 |S_n| (n ≥ 1)

6STEP 6

두 배를 곱해 나가기

두 배를 곱해 나가면 2²⁰⁰⁵, 보기 (E).

|S_n| = 2 · 2^ n-1 = 2ⁿ → |S₂₀₀₅| = 2²⁰⁰⁵

정답

2²⁰⁰⁵

선택지 중 2005, 4010, 2005²는 반복 횟수에 대해 다항식처럼 자라지만, 뒤로 가는 한 단계마다 개수가 2배가 되므로 증가는 지수적이어야 한다. 선택지 (A)는 x = 1/4이 이미 한 번 반복에서 성립하므로 바로 제외된다. 공식 |S_n| = 2ⁿ은 손으로 구한 두 경우 |S₁| = 2, |S₂| = 4와도 맞고, 나열된 해가 정확히 2ⁿ⁺¹ 분의 홀수여서 0이나 1이 되는 일이 없다.

💡핵심 정리

뒤로 가는 한 걸음마다 출발점이 정확히 두 개씩이라면, 2005걸음 뒤로 가면 출발점은 2²⁰⁰⁵개다.

출력이 구간 안에 머무는지 확인
목표를 역상 문제로 바꾸기
내부 값마다 근원은 두 개
처음 두 단계는 손으로
두 배 규칙이 깨지지 않음을 증명
두 배를 곱해 나가기