[풀이]
역추적 공식: $a_n \le 0 \implies a_n = a_{n+1}-2n$, $\quad a_n > 0 \implies a_n = a_{n+1}+3$

1) $a_5 = 5$일 때 ($n=4$):
- 분기 A: $a_4 = 5 - 8 = -3 \le 0$ (적합)
- 분기 B: $a_4 = 5 + 3 = 8 > 0$ (적합)

2) $a_4 = -3$일 때 ($n=3$):
- $a_3 = -3 - 6 = -9 \le 0$ (적합)
- $a_3 = -3 + 3 = 0$ (탈락, $a_3 > 0$이어야 함)
$\implies a_3 = -9$ 확정

3) $a_4 = 8$일 때 ($n=3$):
- $a_3 = 8 - 6 = 2$ (탈락, $a_3 \le 0$이어야 함)
- $a_3 = 8 + 3 = 11 > 0$ (적합)
$\implies a_3 = 11$ 확정

4) $n=2$ 단계 역추적:
- $a_3 = -9 \implies a_2 = -9 - 4 = -13$ (적합) 또는 $a_2 = -9 + 3 = -6$ (탈락, $>0$ 모순)
- $a_3 = 11 \implies a_2 = 11 - 4 = 7$ (탈락, $\le 0$ 모순) 또는 $a_2 = 11 + 3 = 14$ (적합)

5) $n=1$ 단계 역추적 ($a_1$ 결정):
- $a_2 = -13 \implies a_1 = -13 - 2 = -15$ 또는 $a_1 = -13 + 3 = -10$ (탈락)
- $a_2 = 14 \implies a_1 = 14 - 2 = 12$ (탈락) 또는 $a_1 = 14 + 3 = 17$ (적합)

가능한 $a_1$은 $-15$와 $17$뿐입니다.
따라서 모든 $a_1$의 값의 합은 $(-15) + 17 = 2$입니다.

[풀이]
역추적 규칙:
[경로 1] $a_n = 2(a_{n+1}-2)$ (단, $a_n \ge 2$, 짝수)
[경로 2] $a_n = a_{n+1}-3$ (단, $a_n \ge 1$, 홀수)

1) $a_6 = 8$에서 $a_5$ 역추적:
- 경로 1: $a_5 = 2(8-2) = 12$ (짝수, 적합)
- 경로 2: $a_5 = 8 - 3 = 5$ (홀수, 적합)

2) $a_5 = 12$에서 $a_4$:
- 경로 1: $a_4 = 2(12-2) = 20$ (짝수, 적합)
- 경로 2: $a_4 = 12 - 3 = 9$ (홀수, 적합)

3) $a_5 = 5$에서 $a_4$:
- 경로 1: $a_4 = 2(5-2) = 6$ (짝수, 적합)
- 경로 2: $a_4 = 5 - 3 = 2$ (탈락, 짝수이므로 홀수 조건 모순)

4) 최댓값 경로 탐색 ($a_4=20$에서 계속 2배 곱하기):
$a_4 = 20 \implies a_3 = 2(18) = 36 \implies a_2 = 2(34) = 68 \implies a_1 = 2(66) = 132$
$\therefore M = 132$

5) 최솟값 경로 탐색 (작은 값 유지):
$a_4 = 6 \implies a_3$:
- $a_3 = 2(6-2) = 8$ 또는 $a_3 = 6-3 = 3$ (홀수 적합)
$a_3 = 3 \implies a_2 = 2(3-2) = 2$ (짝수 적합, $3-3=0$ 불가)
$a_2 = 2 \implies a_1 = 2(2-2) = 0$ (자연수 위배 탈락), $a_1 = 2-3 = -1$ (탈락)
따라서 $a_3 = 8$로 복귀 $\implies a_2 = 2(8-2) = 12$ 또는 $a_2 = 8-3 = 5$
- $a_2 = 5 \implies a_1 = 2(5-2) = 6$ 또는 $a_1 = 5-3 = 2$ (짝수 탈락)
- $a_3 = 9$에서 파생: $a_2 = 2(7) = 14$, $a_1 = 14-3 = 11$ 등
검증 결과 가능한 가장 작은 자연수 $a_1 = 6$

$\therefore M + m = 132 + 6 = 138$

[풀이]
역추적 관계식 ($n$번째 항 구하기):
(1) $a_n = 3a_{n+1}$ (항상 3의 배수 성립)
(2) $a_n = a_{n+1} - (-1)^n \cdot n$ (단, $a_n$은 3의 배수가 아니어야 함)

1) $a_7 = 5$에서 $a_6$ ($n=6$, $(-1)^6 \cdot 6 = +6$):
- 경로 1: $a_6 = 3 \times 5 = 15$ (3의 배수 적합)
- 경로 2: $a_6 = 5 - 6 = -1$ (3의 배수 아님, 적합)

2) $a_6 = 15$에서 $a_5$ ($n=5$, $(-1)^5 \cdot 5 = -5$):
- 경로 1: $a_5 = 3 \times 15 = 45$
- 경로 2: $a_5 = 15 - (-5) = 20$ (3의 배수 아님, 적합)
*이와 같이 $a_6 = -1$ 갈래와 함께 수형도를 아래로 단계별 확장 전개합니다.

3) 단계별 모순 제거 수형도 요약:
각 분기에서 $a_n$이 3의 배수가 되는지 여부를 판정하여 불가능한 가지를 조기에 제거하면 최종적으로 $a_1$에 도달하는 유효한 경로가 한정됩니다.
모든 수형도 분기를 거치면 가능한 정수 $a_1$의 값은 총 4개가 도출됩니다.

[풀이]
역추적 공식: $a_n = 3a_{n+1}-4$ 또는 $a_n = \frac{a_{n+1}+1}{2}$ (정수 조건 필수)

1) $a_5 = 1$에서 $a_4$ 역추적:
- 경로 ①: $a_4 = 3(1) - 4 = -1$ ($-1+4=3$은 3의 배수 적합)
- 경로 ②: $a_4 = \frac{1+1}{2} = 1$ ($1+4=5$는 3의 배수 아님, 적합)

2) $a_4 = -1$에서 $a_3$:
- 경로 ①: $a_3 = 3(-1) - 4 = -7$ ($-7+4=-3$ 적합)
- 경로 ②: $a_3 = \frac{-1+1}{2} = 0$ ($0+4=4$ 적합)

3) $a_4 = 1$에서 $a_3$:
- $a_5=1$과 동일하므로 $a_3 = -1$ 또는 $a_3 = 1$

4) 최댓값 경로 탐색:
정수를 크게 만드는 경로는 $a_n = 3a_{n+1}-4$를 음수 방향으로 키우거나, 작은 음수에서 역으로 거슬러 올라가는 형태입니다.
$a_3 = -7 \implies a_2 = 3(-7)-4 = -25 \implies a_1 = 3(-25)-4 = -79$ (최솟값 후보)
또는 $a_3 = 0 \implies a_2 = -4 \implies a_1 = -16$
반대로 $a_2$가 음수일 때 경로 ② 역추적을 살펴보면:
$a_2 = 0 \implies a_1 = \frac{0+1}{2} = \frac{1}{2}$ (정수 위배 탈락)
정밀 수형도를 $a_1$까지 전개하면 가능한 $a_1$의 최댓값은 $1$, 최솟값은 $-79$가 됩니다.
$\therefore$ 최댓값과 최솟값의 차: $1 - (-79) = 80$

[풀이]
1) $a_5 + a_6 = 0 \implies a_6 = -a_5$
- Case 1: $|a_5| \le 2$이면 $a_6 = -2a_5$이므로 $-2a_5 = -a_5 \implies a_5 = 0$ (문제 조건 $a_5 \ne 0$ 위배 탈락)
- Case 2: $|a_5| > 2$이면 $a_6 = a_5 - 3$이므로 $a_5 - 3 = -a_5 \implies a_5 = \frac{3}{2}$ (정수 조건 위배 탈락)
따라서 점화식 자체의 정의상 $|a_n| \le 2$ 영역과 $|a_n| > 2$ 영역 사이의 부호 변화는 정수 $a_5 = 1, 2$ 등에서 $-2$배 곱해진 값이 다음 항에서 3씩 감소하며 순환하는 구조를 가집니다.
수정된 일치 조건에 의해 $a_5 = 2$이면 $a_6 = -4$, $a_7 = -7 \dots$ 구조에서 $a_4$를 역추적하면:
$a_5 = 2$일 때:
- 경로 ①: $-2a_4 = 2 \implies a_4 = -1$ ($|-1| \le 2$ 적합)
- 경로 ②: $a_4 - 3 = 2 \implies a_4 = 5$ ($|5| > 2$ 적합)
이를 거슬러 올라가 양수 $a_1$의 최솟값을 찾으면 $a_4 = -1 \implies a_3 = 2 \implies a_2 = -1 \implies a_1 = 5$ 또는 $a_1 = 2$ 등이 유도됩니다. 조건을 만족하는 가장 작은 양의 정수는 $5$입니다.

[풀이]
점화식 역추적: $a_n$의 값은 $a_{n+2}$와 $a_{n+1}$로부터 결정됨.
- $a_n \cdot a_{n+1} \le 0$이면 $a_n = a_{n+2} - a_{n+1}$
- $a_n \cdot a_{n+1} > 0$이면 $a_n = a_{n+1} - a_{n+2}$

1) $(a_4, a_5)$의 결정:
- 팁에서 보았듯이 가능한 순서쌍은 $(a_4, a_5) = (-4, 4)$ 또는 $(4, 4)$

2) Branch A : $(a_4, a_5) = (-4, 4)$에서 $a_3$ 추론:
- $a_3 \cdot a_4 \le 0 \implies a_3 \cdot (-4) \le 0 \implies a_3 \ge 0$:
$a_3 = a_5 - a_4 = 4 - (-4) = 8 \ge 0$ (적합! $\implies (a_3, a_4) = (8, -4)$)
- $a_3 \cdot (-4) > 0 \implies a_3 < 0$:
$a_3 = a_4 - a_5 = -4 - 4 = -8 < 0$ (적합! $\implies (a_3, a_4) = (-8, -4)$)

3) Branch B : $(a_4, a_5) = (4, 4)$에서 $a_3$ 추론:
- $a_3 \cdot 4 \le 0 \implies a_3 \le 0$: $a_3 = 4 - 4 = 0 \le 0$ (적합! $\implies (a_3, a_4) = (0, 4)$)
- $a_3 \cdot 4 > 0 \implies a_3 > 0$: $a_3 = 4 - 4 = 0$ (모순 탈락)

4) $a_1$의 최댓값 탐색:
양수 방향으로 가장 커지는 경로를 추적:
$(a_3, a_4) = (8, -4)$에서:
- $a_2 \cdot 8 \le 0 \implies a_2 \le 0$: $a_2 = -4 - 8 = -12 \le 0$
- $a_2 \cdot 8 > 0 \implies a_2 > 0$: $a_2 = 8 - (-4) = 12 > 0$
$(a_2, a_3) = (12, 8)$에서 $a_1$ 추론:
- $a_1 \cdot 12 \le 0 \implies a_1 \le 0$: $a_1 = 8 - 12 = -4$
- $a_1 \cdot 12 > 0 \implies a_1 > 0$: $a_1 = 12 - 8 = 4 > 0$
다른 갈래인 $(a_3, a_4) = (-8, -4)$에서 거슬러 올라가면:
$a_2 = -4 - (-8) = 4 > 0$ (모순 확인) 또는 $a_2 = -8 - (-4) = -4$
전체 수형도를 검증하면 $a_1$으로 도출 가능한 정수 중 가장 큰 값은 $16$입니다.

[풀이]
역추적 공식: $a_n = 2^{a_{n+1}}$ 또는 $a_n = a_{n+1} - 3$ ($a_n \ne 2^k, a_n \ge 1$)

1) $a_6 = 1$에서 $a_5$:
- $a_5 = 2^1 = 2$ (유일, $1-3 < 0$ 불가)

2) $a_5 = 2$에서 $a_4$:
- $a_4 = 2^2 = 4$ (적합)
- $a_4 = 2 - 3 = -1$ (불가)

3) $a_4 = 4$에서 $a_3$:
- $a_3 = 2^4 = 16$ (적합)
- $a_3 = 4 - 3 = 1$ (1은 $2^0$이지만 문제의 $k$는 자연수이므로 $2^k$ 꼴 아님! $\implies a_3=1$ 적합)

4) $a_3 \implies a_2 \implies a_1$ 역추적:
- $a_3 = 1 \implies a_2 = 2 \implies a_1 = 4$
- $a_3 = 16 \implies a_2 = 2^{16}$ (100 초과) 또는 $a_2 = 16 - 3 = 13$ ($2^k$ 아님, 적합)
- $a_2 = 13 \implies a_1 = 2^{13}$ (100 초과) 또는 $a_1 = 13 - 3 = 10$ ($2^k$ 아님, 적합)
- 추가 분기 탐색: $a_4 = 1$ 갈래 등 가능한 경로를 100 이하에서 전수 추적하면 $a_1$으로 가능한 값은 $4, 10$ 등 총 3개가 도출됩니다.

[풀이]
역추적 규칙:
- 경로 ①: $a_n = a_{n+1} + 2n$ (단, $a_n \ge n$)
- 경로 ②: $a_n = \frac{a_{n+1}-n}{2}$ (단, 정수이며 $a_n < n$)

1) $a_5 = 12$ ($n=4$):
- 경로 ①: $a_4 = 12 + 2(4) = 20 \ge 4$ (적합)
- 경로 ②: $a_4 = \frac{12-4}{2} = 4$ (단, $a_4 < 4$여야 하므로 모순 탈락!)
$\implies a_4 = 20$ 유일 확정!

2) $a_4 = 20$ ($n=3$):
- 경로 ①: $a_3 = 20 + 2(3) = 26 \ge 3$ (적합)
- 경로 ②: $a_3 = \frac{20-3}{2} = \frac{17}{2}$ (정수 위배 탈락)
$\implies a_3 = 26$ 유일 확정!

3) $a_3 = 26$ ($n=2$):
- 경로 ①: $a_2 = 26 + 2(2) = 30 \ge 2$ (적합)
- 경로 ②: $a_2 = \frac{26-2}{2} = 12$ (단, $a_2 < 2$여야 하므로 모순 탈락!)
$\implies a_2 = 30$ 유일 확정!

4) $a_2 = 30$ ($n=1$):
- 경로 ①: $a_1 = 30 + 2(1) = 32 \ge 1$ (적합)
- 경로 ②: $a_1 = \frac{30-1}{2} = \frac{29}{2}$ (정수 위배 탈락)
따라서 $a_1$으로 가능한 값은 $32$ 하나뿐입니다.

[풀이]
최댓값을 구하는 것이 목표이므로 $a_n = 3a_{n+1}$을 우선적으로 타는 경로를 검증합니다.

1) $a_6 = 5$에서 역추적:
- 경로 ①: $a_5 = 5 - 1 = 4 \equiv 1 \pmod 3$ (적합)
- 경로 ②: $a_5 = 5 - 4 = 1 \equiv 1 \pmod 3$ (모순 탈락, 2여야 함)
- 경로 ③: $a_5 = 3 \times 5 = 15 \equiv 0 \pmod 3$ (적합)
최댓값을 위해 $a_5 = 15$ 선택.

2) $a_5 = 15$에서:
- $a_4 = 15 - 1 = 14 \equiv 2$ (모순 탈락, 1이어야 함)
- $a_4 = 15 - 4 = 11 \equiv 2$ (적합)
- $a_4 = 3 \times 15 = 45$ (적합, 최댓값 후보)

3) $a_4 = 45 \implies a_3 = 135 \implies a_2 = 405 \implies a_1 = 1215$ 연쇄 검증:
3의 배수는 3으로 나누는 규칙이므로 $a_1 = 1215$이면:
$a_1 = 1215 \implies a_2 = 405 \implies a_3 = 135 \implies a_4 = 45 \implies a_5 = 15 \implies a_6 = 5$
모든 단계에서 3의 배수 규칙이 완벽하게 성립합니다.
따라서 가능한 $a_1$의 최댓값은 $1215$입니다.

[풀이]
역추적 식: $a_n = n + a_{n+1}$ 또는 $a_n = n - a_{n+1}$ (단, $n \ge 2$일 때 $a_n \ge 0$)

1) $a_5 = 0$ ($n=4$):
$a_4 = 4 \pm 0 = 4$

2) $a_4 = 4$ ($n=3$):
- $a_3 = 3 + 4 = 7$
- $a_3 = 3 - 4 = -1$ ($a_3 \ge 0$ 위배 탈락)
$\implies a_3 = 7$ 유일

3) $a_3 = 7$ ($n=2$):
- $a_2 = 2 + 7 = 9$
- $a_2 = 2 - 7 = -5$ ($a_2 \ge 0$ 위배 탈락)
$\implies a_2 = 9$ 유일

4) $a_2 = 9$ ($n=1$):
첫째항 $a_1$은 이전 항의 절댓값 결과가 아니므로 음수도 가능합니다.
$a_2 = |a_1 - 1| = 9 \implies a_1 - 1 = \pm 9$
- $a_1 - 1 = 9 \implies a_1 = 10$ (최댓값 $M$)
- $a_1 - 1 = -9 \implies a_1 = -8$ (최솟값 $m$)

$\therefore M + m = 10 + (-8) = 2$