역추론을 이용해 $a_1$이 될 수 있는 값들의 개수를 찾습니다. $a_n = 3a_{n+1}$ 또는 $a_n = a_{n+1}+2$ 입니다.

$a_4$ 구하기: $a_5=1$.

• $a_4=3 \times 1 = 3$. 이 규칙은 $a_4$가 3의 배수일 때 사용. $3$은 3의 배수이므로 성립.
• $a_4=1+2=3$. 이 규칙은 $a_4$가 3의 배수가 아닐 때 사용. $3$은 3의 배수이므로 모순.

따라서 $a_4=3$ 입니다. (1개)

$a_3$ 구하기: $a_4=3$.

• $a_3=3 \times 3 = 9$. 조건: $a_3$은 3의 배수. $9$는 3의 배수이므로 성립.
• $a_3=3+2=5$. 조건: $a_3$은 3의 배수가 아님. $5$는 3의 배수가 아니므로 성립.

$a_3$는 $9$ 또는 $5$입니다. (2개)

$a_2$ 구하기:

$a_2$는 $27, 11, 15, 7$이 가능합니다. (총 4개)

$a_1$ 구하기:

• $a_2=27$: $a_1=81, 29$ (2개)
• $a_2=11$: $a_1=33, 13$ (2개)
• $a_2=15$: $a_1=45, 17$ (2개)
• $a_2=7$: $a_1=21, 9$ (2개)

각각의 $a_2$ 값에 대해 2개의 $a_1$ 값이 유효하게 존재합니다. 따라서 가능한 $a_1$의 총 개수는 $2+2+2+2 = 8$개 입니다.

역추론 규칙은 $a_n = a_{n+1}/2$ 또는 $a_n=a_{n+1}+5$ 입니다. $a_{10}=100$ 입니다.

핵심 관찰: 5로 나눈 나머지
만약 $a_{n+1}$이 5의 배수이면, $a_n$의 가능성은 다음과 같습니다.
– $a_n = a_{n+1}+5$: 5의 배수 + 5의 배수 = 5의 배수.
– $a_n = a_{n+1}/2$: 5의 배수를 2로 나눔. 정수이려면 $a_{n+1}$은 10의 배수여야 함. 결과는 5의 배수.
$a_{10}=100$은 5의 배수이므로, 귀납적으로 모든 가능한 정수 $a_n$ ($n<10$)은 5의 배수입니다.

단순화된 문제로 변환
$a_n=5b_n$으로 치환합시다. $a_{10}=100 \implies b_{10}=20$.
– $5b_{n+1} = 2(5b_n) \implies b_{n+1}=2b_n$. – $5b_{n+1} = 5b_n – 5 \implies b_{n+1}=b_n-1$.
역추론 규칙은 $b_n=b_{n+1}/2$ 또는 $b_n=b_{n+1}+1$ 입니다. $a_2$의 합은 $5 \times (b_2\text{의 합})$ 입니다.

$b_2$ 구하기 (역추론):

• $b_{10}=20$
• $b_9 \in \{10, 21\}$
• $b_8 \in \{5, 11, 22\}$ (21/2는 정수 아님)
• $b_7 \in \{6, 12, 11, 23\}$ (5/2, 11/2는 정수 아님)
• $b_6 \in \{3, 7, 6, 13, 12, 24\}$ (11/2, 23/2는 정수 아님)
• $b_5 \in \{4, 8, 14, 7, 13, 25\}$ (3/2, 6/2, 12/2 가능)
• $b_4 \in \{2, 5, 9, 15, 8, 14, 26\}$ (7/2, 13/2는 정수 아님)
• $b_3 \in \{1, 3, 6, 10, 16, 9, 15, 27\}$ (5/2, 8/2, 14/2, 26/2 가능)
• $b_2 \in \{2, 4, 7, 11, 17, 10, 16, 28\}$ (1/2, 3/2, 6/2, 9/2, 15/2, 27/2 가능)

가능한 $b_2$ 값들의 집합은 $\{2, 4, 7, 10, 11, 16, 17, 28\}$ 입니다.
$b_2$ 값들의 합 = $2+4+7+10+11+16+17+28 = 95$.

따라서 $a_2$가 될 수 있는 모든 값들의 합은 $5 \times 95 = 475$ 입니다.

일반항의 패턴을 찾기 위해 항을 순서대로 나열합니다.

• $a_1 = k$
• $a_2 = -a_1+2 = -k+2$
• $a_3 = -a_2+3 = -(-k+2)+3 = k+1$
• $a_4 = -a_3+4 = -(k+1)+4 = -k+3$
• $a_5 = -a_4+5 = -(-k+3)+5 = k+2$

패턴을 보면, 홀수 항은 $a_{2m-1}=k+(m-1)$, 짝수 항은 $a_{2m}=-k+(m+1)$ 입니다.

문제의 조건:

1. $a_9 > 100$
2. $a_i \le 100$ for $i=1, 2, \dots, 8$

조건 1 해결:
$a_9$는 홀수 항이므로 $m=5$일 때, $a_9 = a_{2\cdot5-1} = k+(5-1) = k+4$.
$k+4 > 100 \implies k > 96$.

조건 2 해결:
$a_1$부터 $a_8$까지의 항들이 100 이하가 되어야 합니다. 이 중 $k$값을 가장 크게 제한하는 것은 $k$가 포함된 양수 항, 즉 홀수 항입니다.

• $a_1=k \le 100$
• $a_3=k+1 \le 100 \implies k \le 99$
• $a_5=k+2 \le 100 \implies k \le 98$
• $a_7=k+3 \le 100 \implies k \le 97$

짝수 항들은 $-k$를 포함하므로, 자연수 $k$에 대해 항상 $a_{2m} \le 100$ 조건을 만족합니다.
예: $a_8=-k+5 \le 100 \implies -k \le 95 \implies k \ge -95$. (자연수 k는 항상 만족)

종합:
두 조건을 모두 만족하는 $k$의 범위는 $96 < k \le 97$ 입니다.
이 범위를 만족하는 자연수 $k$는 $97$ 하나뿐입니다.
따라서 자연수 $k$의 개수는 1개입니다.

역추론을 통해 $a_5, a_4, \dots, a_1$을 구합니다. $S_5$를 최대로 만들려면 각 항 $a_k$가 가능한 한 커야 합니다. 역추론 규칙은 $a_n = a_{n+1}+7$ 또는 $a_n = (1-a_{n+1})/2$ 입니다.

$a_5$ 구하기: $a_6=11$.

• $a_5 = 11+7=18$. 이 규칙은 $a_5>0$일 때 사용. $18>0$이므로 성립.
• $a_5 = (1-11)/2 = -5$. 이 규칙은 $a_5 \le 0$일 때 사용. $-5 \le 0$이므로 성립.

$S_5$를 최대로 하려면 $a_5$가 커야 하므로 $a_5=18$ 경로를 우선 탐색합니다.

$a_4$ 구하기: $a_5=18$.

• $a_4 = 18+7=25$. ($25>0$ 성립)
• $a_4 = (1-18)/2 = -8.5$. (정수/자연수 조건은 없지만, 이후 계산이 복잡)

$a_4=25$가 더 크므로 이 경로를 선택합니다.

$a_3$ 구하기: $a_4=25 \implies a_3=25+7=32$.

$a_2$ 구하기: $a_3=32 \implies a_2=32+7=39$.

$a_1$ 구하기: $a_2=39 \implies a_1=39+7=46$.

이 경로, 즉 모든 항이 양수인 경로는 $(a_1, a_2, a_3, a_4, a_5) = (46, 39, 32, 25, 18)$ 입니다.
이때 $S_5 = 46+39+32+25+18 = 160$.

다른 경로가 더 큰 합을 만드는지 확인해야 합니다. 만약 어느 단계에서 $a_n = (1-a_{n+1})/2$ 경로를 택하면 이전 항은 음수가 되어 값이 작아집니다. 그 다음 항은 $-2a_n+1$이 되어 값이 커질 수 있지만, 전반적으로 양수 경로를 계속 따르는 것이 각 항의 값을 크게 유지하는 데 유리합니다. 예를 들어 $a_5=-5$ 경로를 택하면,
$a_4$ 구하기: $a_5=-5$.

• $a_4=-5+7=2$. ($2>0$ 성립)
• $a_4=(1-(-5))/2=3$. ($3>0$ 성립)

두 경우 모두 $a_5=18$에서 파생된 $a_4=25$보다 훨씬 작습니다. 따라서 이전 항들도 작아져 합이 최대가 되기 어렵습니다.
따라서 $S_5$의 최댓값은 160입니다.

역추론 규칙은 $a_n=a_{n+1}+\sqrt{2}$ (이전항 $a_n$이 유리수) 또는 $a_n=\pm\sqrt{a_{n+1}}$ (이전항 $a_n$이 무리수) 입니다.

$a_3$ 구하기: $a_4=18$.

• $a_3=18+\sqrt{2}$. 이 규칙은 $a_3$이 유리수일 때 사용. $18+\sqrt{2}$는 무리수이므로 모순.
• $a_3=\pm\sqrt{18} = \pm 3\sqrt{2}$. 이 규칙은 $a_3$이 무리수일 때 사용. $\pm 3\sqrt{2}$는 무리수이므로 성립.

따라서 $a_3$는 $3\sqrt{2}$ 또는 $-3\sqrt{2}$ 입니다.

$a_2$ 구하기: