문제

모든 항이 정수인 수열 $\{a_n\}$이 모든 자연수 $n$에 대하여 다음 규칙을 만족한다.

$|a_m|=|a_{m+2}|$인 자연수 $m$의 최솟값이 $3$일 때, 가능한 모든 수열에 대한 $|a_1|$의 값의 합을 구하여라.

먼저 7 하나만 넣어 보자

문제의 규칙을 다시 떠올리자. 홀수면 3을 빼고, 짝수면 절반으로 나눈다. 7에서 시작하면 위 그림처럼 7 → 4 → 2 → 1 → −2로 움직인다.

두 칸 떨어진 수끼리 비교하면 7과 2는 다르고, 4와 1도 다르지만, 2와 −2는 절댓값이 같다. 세 번째 수에서 시작한 비교가 처음 맞는다.

예시의 2 자리를 a₃로 바꾸자

방금 예시에서 2는 세 번째 수였다. 일반적으로는 먼저 $a_3$가 두 칸 뒤 $a_5$와 같은 절댓값이 되는 경우를 찾는다.

단, 그보다 앞선 두 비교에서는 아직 같으면 안 된다. 그림을 식으로 옮기면 딱 세 줄이다.

홀수에서는 두 값만 돌아온다

$x=a_3$가 홀수라면 첫 칸은 $x-3$이고, 이 값은 짝수다. 따라서 두 번째 칸에서는 절반이 된다.

홀수 출발에서는 $-3,1$ 두 값만 두 칸 뒤 같은 절댓값으로 돌아온다.

짝수에서는 가운데 값만 보면 된다

이제 $x$가 짝수 또는 0이라고 하자. 첫 칸 뒤의 값을 $y=x/2$라 두면 경우가 단순해진다.

$y$가 홀수면 다음 값은 $y-3$이므로 $|2y|=|y-3|$에서 $x=-6,2$. $y$가 짝수 또는 0이면 다음 값은 $y/2$이므로 $|2y|=|y/2|$에서 $x=0$만 남는다.

앞 장의 홀수 두 값과 합치면 이것이 두 칸 뒤 절댓값이 돌아오는 정수의 전부다.

자취를 거꾸로 따라가며 너무 이른 후보를 지운다

다음 항이 $z$였다면 직전 항은 두 갈래다. 짝수에서 절반이 된 $2z$, 또는 홀수에서 3을 뺀 $z+3$이다. 두 번째 갈래는 $z$가 짝수일 때만 열린다.

이 규칙으로 $a_3\in E$가 되게 하는 $a_2$를 모두 만든다. 그런데 $a_2\in E$이면 이미 $m=2$에서 먼저 맞으므로 지워야 한다.

한 번 더 거꾸로 올라가면 초항이 나온다

같은 역방향 규칙을 남은 네 값에 한 번 더 적용한다.

이 여섯 값은 모두 $E$ 밖이므로 $m=1$에서도 먼저 맞지 않는다. 앞에서 $a_2$도 걸렀으니 첫 성립 위치는 정확히 3이다.

답

이 문제는 수열을 앞으로 오래 생성하는 문제가 아니라, 처음 맞는 상태를 만든 뒤 역방향 가지를 거르는 문제였다.