첫째항이 자연수인 수열이다 an이 홀수이면 a(n+1)=2^an이다 an이 짝수이면 a(n+1)=an/2이다 a6+a7=3이다 구하는 값은 조건을 만족하는 모든 a1의 값의 합이다

2024학년도 수능 수학 15번 풀이 | 점화식 역방향 추적과 홀짝 조건 [241115]

문제

문제 텍스트 객관식

첫째항이 자연수인 수열 $\{a_n\}$ $\{a_n\}$이 모든 자연수 $n$ $n$에 대하여

a_{n+1}= \begin{cases} 2^{a_n} & (a_n\text{이 홀수인 경우})\\ \dfrac{1}{2}a_n & (a_n\text{이 짝수인 경우}) \end{cases}

를 만족시킬 때, $a_6+a_7=3$ $a_6+a_7=3$이 되도록 하는 모든 $a_1$ $a_1$의 값의 합은? [4점]

① $139$ $139$
② $146$ $146$
③ $153$ $153$
④ $160$ $160$
⑤ $167$ $167$

정답

③

풀이

마지막 두 항이 만들 수 있는 쌍부터 적어보자

조건 $a_6+a_7=3$ $a_6+a_7=3$은 뒤쪽 값을 아주 작게 묶어 둔다.
첫째항이 자연수이고, 홀수이면 $2^{a_n}$ $2^{a_n}$, 짝수이면 $\frac12a_n$ $\frac12a_n$으로 가므로 모든 항은 자연수이다.
따라서 합이 $3$ $3$인 두 자연수 쌍은 $(a_6,a_7)=(1,2),\ (2,1)$ $(a_6,a_7)=(1,2),\ (2,1)$뿐이다.

이 두 쌍은 실제 점화식과도 맞다.
$1$ $1$은 홀수이므로 $1\mapsto 2^1=2$ $1\mapsto 2^1=2$이고, $2$ $2$는 짝수이므로 $2\mapsto \frac12\cdot2=1$ $2\mapsto \frac12\cdot2=1$이다.
따라서 $a_6=1$ $a_6=1$ 또는 $a_6=2$ $a_6=2$이면 $a_7$ $a_7$까지 자동으로 정해진다.
이제는 $a_6\in\{1,2\}$ $a_6\in\{1,2\}$가 되도록 하는 모든 $a_1$ $a_1$을 찾으면 된다.

다음 항에서 이전 항을 거꾸로 찾아보자

한 단계 뒤의 값이 $y$ $y$라고 하자.
이 $y$ $y$를 만든 이전 항 $x$ $x$는 두 갈래에서 올 수 있다.

먼저 $x$ $x$가 짝수였으면 $y=\frac{x}{2}$ $y=\frac{x}{2}$이므로 항상 $x=2y$ $x=2y$가 가능하다.
예를 들어 다음 항이 $8$ $8$이면 짝수 가지의 이전 항으로 $16$ $16$이 생긴다.

반면 $x$ $x$가 홀수였으면 $y=2^x$ $y=2^x$이다.
이때는 $y$ $y$가 $2$ $2$의 거듭제곱이어야 하고, 그 지수 $x$ $x$가 홀수여야 한다.
즉 $y=2^m$ $y=2^m$ 꼴에서 $m$ $m$이 홀수일 때만 이전 항 $m$ $m$이 하나 더 생긴다.

정리하면 거꾸로 한 단계 올라가는 규칙은 다음과 같다.

y\leftarrow 2y\quad\text{항상 가능}

그리고 $y=2^m$ $y=2^m$이며 $m$ $m$이 홀수이면 $y\leftarrow m$ $y\leftarrow m$도 추가된다.

아래 그림의 왼쪽 가지에는 $x=2y$ $x=2y$와 항상 가능 표시가 있고, 오른쪽 가지에는 $y=2^m$ $y=2^m$과 m 홀수만 표시가 붙어 있다.
이 두 표시가 역추적에서 후보를 넣는 기준이다.

다음 항 y에서 이전 항 후보를 2y 가지와 홀수 지수 m 가지로 나누는 규칙 그림 — 다음 항 $y$ $y$에서 $2y$ $2y$는 항상 이전 항 후보가 되고, $y=2^m$ $y=2^m$에서는 $m$ $m$이 홀수일 때만 후보가 추가된다.

여기서 $m$ $m$의 홀짝 확인이 중요하다.
$4=2^2$ $4=2^2$, $16=2^4$ $16=2^4$처럼 $2$ $2$의 거듭제곱이어도 지수가 짝수이면 홀수 가지에서 온 이전 항이 아니다.
홀수였던 이전 항만 $2^x$ $2^x$ 가지를 탈 수 있기 때문이다.

다음 그림은 이 기준을 $8$ $8$과 $16$ $16$에 적용한 것이다.
왼쪽 박스의 $8\leftarrow16,\ 3$ $8\leftarrow16,\ 3$에서는 $3$ $3$이 추가되고, 오른쪽 박스의 $16\leftarrow32$ $16\leftarrow32$에서는 4 제외가 따로 표시된다.

8의 이전 후보는 16과 3이고 16의 이전 후보는 32이며 4는 제외되는 예시 그림 — $8=2^3$ $8=2^3$에서는 $3$ $3$이 추가되지만, $16=2^4$ $16=2^4$에서는 $4$ $4$가 제외되어 $32$ $32$만 이전 후보로 남는다.

가능한 값을 집합으로 모아가자

가능한 $a_k$ $a_k$의 값을 $S_k$ $S_k$라고 쓰자.
$S_6=\{1,2\}$ $S_6=\{1,2\}$에서 시작해 위 규칙을 다섯 번 적용하면 $S_1$ $S_1$이 나온다.
점화식이 여러 이전 항을 같은 다음 항으로 보낼 수 있으므로, 각 다음 항마다 가능한 이전 항을 모두 모아 집합으로 합치는 방식이다.
이러면 같은 값이 중복되어도 한 번만 남고, 가능한 이전 항은 빠지지 않는다.

먼저 $S_6=\{1,2\}$ $S_6=\{1,2\}$이다.
$1\leftarrow2$ $1\leftarrow2$, $2\leftarrow4,1$ $2\leftarrow4,1$이므로 $S_5=\{1,2,4\}$ $S_5=\{1,2,4\}$이다.

다시 한 단계 거꾸로 가면

\begin{aligned} 1&\leftarrow 2,\\ 2&\leftarrow 4,\ 1,\\ 4&\leftarrow 8 \end{aligned}

이다.
$4=2^2$ $4=2^2$이지만 지수 $2$ $2$가 짝수이므로 $2$ $2$를 홀수 가지의 이전 항으로 새로 추가하지 않는다.
따라서 $S_4=\{1,2,4,8\}$ $S_4=\{1,2,4,8\}$이다.

이제 $S_4$ $S_4$에서 $S_3$ $S_3$으로 간다.

\begin{aligned} 1&\leftarrow 2,\\ 2&\leftarrow 4,\ 1,\\ 4&\leftarrow 8,\\ 8&\leftarrow 16,\ 3 \end{aligned}

여기서 $3$ $3$은 $8=2^3$ $8=2^3$이고 지수 $3$ $3$이 홀수라서 추가된다.
그래서 $S_3=\{1,2,3,4,8,16\}$ $S_3=\{1,2,3,4,8,16\}$이다.

한 번 더 올라가면

\begin{aligned} 1&\leftarrow 2,\\ 2&\leftarrow 4,\ 1,\\ 3&\leftarrow 6,\\ 4&\leftarrow 8,\\ 8&\leftarrow 16,\ 3,\\ 16&\leftarrow 32 \end{aligned}

이므로 $S_2=\{1,2,3,4,6,8,16,32\}$ $S_2=\{1,2,3,4,6,8,16,32\}$이다.
$16=2^4$ $16=2^4$에서는 지수 $4$ $4$가 짝수이므로 $4$ $4$를 홀수 가지의 이전 항으로 추가하지 않는다.

마지막 한 단계에서 새로 생기는 홀수 후보를 확인하자

이제 $S_2$ $S_2$의 각 값에서 $a_1$ $a_1$ 후보를 만든다.

\begin{aligned} 1&\leftarrow 2,\\ 2&\leftarrow 4,\ 1,\\ 3&\leftarrow 6,\\ 4&\leftarrow 8,\\ 6&\leftarrow 12,\\ 8&\leftarrow 16,\ 3,\\ 16&\leftarrow 32,\\ 32&\leftarrow 64,\ 5 \end{aligned}

마지막 줄의 $5$ $5$는 $32=2^5$ $32=2^5$이고 지수 $5$ $5$가 홀수라서 들어온다.
같은 이유로 $8=2^3$ $8=2^3$에서는 $3$ $3$이 들어오지만, $4=2^2$ $4=2^2$, $16=2^4$ $16=2^4$에서는 지수가 짝수라서 $2,4$ $2,4$를 새 후보로 더하지 않는다.

따라서 가능한 첫째항은

S_1=\{1,2,3,4,5,6,8,12,16,32,64\}

이다.
합을 구하면

1+2+3+4+5+6+8+12+16+32+64=153

이므로 정답은 $153$ $153$이다.

비슷한 유형에서 가져갈 관찰

귀납적으로 정의된 수열에서 뒤쪽 항의 조건이 매우 작게 주어지면, 마지막 조건이 허용하는 값을 먼저 적어 본다.
특히 이 문제처럼 한 값이 여러 이전 값에서 나올 수 있는 규칙에서는, 다음 항 $y$ $y$를 기준으로 가능한 이전 항을 모두 모아야 한다.

이때 $y\leftarrow 2y$ $y\leftarrow 2y$는 항상 생기는 가지이고, $y=2^m$ $y=2^m$에서 $m$ $m$이 홀수일 때만 $y\leftarrow m$ $y\leftarrow m$이 추가된다.
이 홀짝 조건을 빠뜨리면 $4=2^2$ $4=2^2$, $16=2^4$ $16=2^4$ 같은 곳에서 불필요한 후보를 넣게 된다.