수열의 귀납적 정의를 이해하고, 역방향으로 항을 추론하여 조건을 만족하는 초기항을 찾는 문항
모든 항이 정수이고 다음 조건을 만족시키는 모든 수열 $\{a_n\}$에 대하여 $|a_1|$의 값의 합을 구하시오. [4점]
(가) 모든 자연수 $n$에 대하여
이다.
(나) $|a_m| = |a_{m+2}|$ 인 자연수 $m$의 최솟값은 3이다.
이 문항은 주어진 조건에 따라 정의된 수열의 규칙을 파악하고, 역추적(Backward Tracking)을 통해 조건을 만족시키는 초기항 $a_1$의 가능한 모든 값을 찾아내는 추론 능력을 평가합니다.
조건 (나)에서 $|a_m| = |a_{m+2}|$를 만족하는 자연수 $m$의 최솟값이 3이라고 했습니다. 이는 다음과 같은 중요한 두 가지 정보를 제공합니다.
1) $m=3$일 때 성립하므로, $|a_3| = |a_5|$ 입니다.
2) 최솟값이 3이므로, $m=1, 2$일 때는 성립하지 않습니다. 즉, $|a_1| \neq |a_3|$ 이고 $|a_2| \neq |a_4|$ 입니다.
먼저 $|a_3| = |a_5|$ 를 만족하는 $a_3$의 값을 찾아봅시다. 이를 위해 $a_n$의 값에 따라 $a_{n+1}$, $a_{n+2}$가 어떻게 변하는지 점화식 (가)를 이용하여 확인해야 합니다. 편의상 $a_3 = k$ (단, $k$는 정수)라고 두고 $k$의 홀짝성에 따라 경우를 나누어 보겠습니다.
$a_3 = k$ 이면, 조건 (가)에 의해 $a_4 = \frac{1}{2}k$ 입니다.
이때, $a_4$의 홀짝성을 알 수 없으므로 다시 경우를 나눕니다.
$a_3 = k$ 이면, 조건 (가)에 의해 $a_4 = k - 3$ 입니다.
홀수에서 홀수(3)를 빼면 짝수가 되므로, $a_4$는 반드시 짝수입니다. (또는 0)
따라서 $a_5 = \frac{1}{2}a_4 = \frac{1}{2}(k - 3)$ 입니다.
중간 결론 :
조건 $|a_3| = |a_5|$ 를 만족하는 $a_3$의 후보는 $-6, -3, 0, 1, 2$ 입니다.
우리는 $a_3$에서 $a_1$을 찾아야 하므로, 점화식을 역으로 계산하는 식을 세우면 편리합니다. 점화식 $a_n \to a_{n+1}$ 을 $a_{n+1} = \alpha$ 라고 할 때, $a_n$을 구하는 식으로 변형해 봅시다.
역추적 시 주의점 : 어떤 값 $\alpha$ 가 주어졌을 때, 이전 항 $a_n$ 은
1. $2\alpha$ (항상 가능)
2. $\alpha + 3$ (단, $|\alpha + 3|$ 이 홀수일 때만 가능)
이렇게 최대 2개의 가지(branch)를 가질 수 있습니다.
점화식을 하나의 함수 $f(x)$로 생각해보면, $a_{n+1} = f(a_n)$ 입니다. 역추적은 곧 역함수 $f^{-1}(x)$ 를 구하는 과정과 같습니다. 정의역에 따른 조건이 있으므로 역함수는 다가함수(Multi-valued function) 형태가 됩니다.
$f(x) = y$ 라 할 때, $x$를 $y$에 대해 풀어보면:
결과적으로 $a_n \in \{ a_{n+1} + 3 \text{ (단, } |a_{n+1}+3|\text{이 홀수)} ,\; 2a_{n+1} \}$ 집합의 원소를 찾는 명확한 알고리즘으로 정리할 수 있습니다.
이제 구해진 $a_3$의 5가지 후보 각각에 대하여 역추적을 수행하여 $a_1$을 구하고, $m=1, 2$일 때의 제약 조건을 통과하는지 확인합니다.
역추적 : $a_2$는 $2(0) = 0$ 또는 $0 + 3 = 3$ (홀수, 가능).
역추적 : $a_2$는 $2(1) = 2$ 또는 $1 + 3 = 4$ (짝수이므로 불가능). 따라서 $a_2 = 2$.
검증: $|a_2| = 2, |a_4| = 2 \implies |a_2| = |a_4|$ 가 성립해버림. 이는 $m$의 최솟값이 3이라는 조건에 위배(모순).
$\implies$ 이 가지는 버림.
역추적 : $a_2$는 $2(2) = 4$ 또는 $2 + 3 = 5$ (홀수, 가능).
역추적 : $a_2$는 $2(-3) = -6$ 또는 $-3 + 3 = 0$ (짝수이므로 불가능). 따라서 $a_2 = -6$.
검증: $|a_2| = 6, |a_4| = 6 \implies |a_2| = |a_4|$ 가 성립해버림. 모순.
$\implies$ 이 가지는 버림.
역추적 : $a_2$는 $2(-6) = -12$ 또는 $-6 + 3 = -3$ (홀수, 가능).
Step 4에서 걸러진 유효한 $a_1$ 의 값들은 다음과 같습니다.
문제에서 요구하는 것은 $|a_1|$ 의 값의 합입니다.
이웃하는 항들 사이의 관계식(점화식)과 초기항을 통해 수열을 정의하는 방법입니다. 본 문항은 점화식에 조건부 분기가 포함되어 있어 함수의 합성과 유사한 성격을 띱니다.
$a_n$의 일반항을 도출하기 어려운 비선형 점화식에서, 특정 항의 값이 주어졌을 때 이전 항들을 거슬러 올라가며 모든 가능성을 탐색하는 방법론입니다. 트리(Tree) 구조의 수형도를 그리는 것이 효과적입니다.
역추적 식 $a_n = a_{n+1} + 3$ 을 적용할 때, 계산된 결과값 $a_n$ 의 절댓값 $|a_n|$ 이 반드시 '홀수'인지 확인해야 합니다. 이 확인 과정을 빼먹으면 수형도에 불가능한 가지가 추가되어 오답으로 직결됩니다.
Step 4의 $a_3 = 1$ 인 경우를 다시 봅시다. $a_4 = -2$ 였고, $a_2$ 를 역추적할 때 $a_2 = 2(1) = 2$ 외에 $a_2 = 1 + 3 = 4$ 도 가능하다고 착각하는 경우가 많습니다.
증명: 점화식의 조건인 '$|a_n|$이 홀수인 경우'는 $a_{n+1} = a_n - 3$ 이 적용되기 위한 필요조건입니다. 역으로 연산하여 도출된 $a_n$이 이 전제 조건을 만족하지 못하면 그 연산 경로는 무효(Invalid)입니다.
성공적으로 찾아낸 6개의 $a_1$ 경로들을 트리 구조로 시각화한 것입니다. 노드를 클릭하거나 마우스를 올려 해당 값이 도출된 점화식 규칙을 확인하세요. x2는 짝수 조건 역연산, +3는 홀수 조건 역연산을 의미합니다.
1. 노드의 의미: 오른쪽(Root)에서 왼쪽($a_1$)으로 진행되며, 각 계층은 역추적하는 수열의 항($a_3 \to a_2 \to a_1$)을 나타냅니다. $a_3$의 후보 중 조건(나)를 통과한 3개의 값(0, 2, -6)에서만 출발합니다. (후보 1과 -3은 Step 4에서 모순이 발견되어 제거됨)
2. 간선(Edge)의 역연산 규칙:
x2 : $a_n = 2a_{n+1}$ 연산을 의미합니다. 정수에 2를 곱하면 항상 짝수이므로(또는 0), 점화식의 짝수 조건을 무조건 충족하여 제약 없이 가지가 뻗어나갑니다.
+3 : $a_n = a_{n+1} + 3$ 연산을 의미합니다. 단, 역산되어 도출된 값 $|a_n|$이 반드시 '홀수'일 때만 가지가 유효합니다. (예: $a_2=5$ 에서 역산한 $a_1 = 5+3=8$은 짝수이므로 홀수 조건에 위배되어 가지가 생성되지 않음)
3. 보이지 않는 가지치기(Pruning): 수형도에 표시되지 않은 숨은 오류 경로들이 있습니다. 예를 들어 $a_3=-6$ 에서 파생된 $a_2 = -6+3=-3$ 의 경우, 홀수 조건은 만족하지만 $|a_2|=|-3|=3$ 이고 $a_4=-3$ 이므로 $|a_2| = |a_4|$ 가 성립해버립니다. 이는 조건(나)의 '최솟값은 3'에 위배됩니다. 본 수형도는 이러한 모순된 경로들을 완벽하게 제거한 '최종 유효 경로(Valid Paths)'만을 시각화한 것입니다.