어떤 문제인가
이 문제는 주어진 독특한 관계식(귀납적 정의)을 만족하는 수열에서, 특정 값($a_k = 10$)을 갖는 항의 개수를 찾는 문제입니다.
이 문제를 해결하기 위해 사용할 핵심 개념은 다음과 같습니다:
- 수열의 규칙성 찾기: 처음 몇 개의 항을 직접 구해보며 규칙을 파악합니다.
- 인덱스를 거꾸로 줄여 가기: 주어진 관계식은 인덱스 $n$을 2배 하거나($2n$), 4배 하고 1 또는 3을 더하는($4n+1$, $4n+3$) 연산으로 되어 있습니다. 방향을 뒤집어 인덱스를 계속 줄여 가면 어디에 도착하는지를 살펴봅니다.
- 중복순열과 조합: 규칙을 일반화한 뒤, 조건을 만족하는 경우의 수를 구하기 위해 경우의 수 개념을 사용합니다.
단계별 풀이
1단계: 처음 몇 개의 항을 구하며 규칙 탐색하기
먼저 주어진 식을 이용해 앞부분의 항들을 직접 구해봅시다.
- $a_1 = 1$
- $a_3 = 4$
이제 관계식을 적용해 봅시다.
- $a_{2n} = a_n + 1$ (짝수 항은 이전 항에 1을 더함)
- $a_{4n+1} = a_n + 4$
- $a_{4n+3} = a_n + 4$
이 식들을 이용해 $a_1$부터 $a_{16}$까지 구해볼게요.
- $a_2 = a_1 + 1 = 2$
- $a_3 = 4$ (주어짐)
- $a_4 = a_2 + 1 = 3$
- $a_5 = a_{4(1)+1} = a_1 + 4 = 5$
- $a_6 = a_{2(3)} = a_3 + 1 = 5$
- $a_7 = a_{4(1)+3} = a_1 + 4 = 5$
- $a_8 = a_{2(4)} = a_4 + 1 = 4$
- $a_9 = a_{4(2)+1} = a_2 + 4 = 6$
- $a_{10} = a_{2(5)} = a_5 + 1 = 6$
- $a_{11} = a_{4(2)+3} = a_2 + 4 = 6$
- $a_{12} = a_{2(6)} = a_6 + 1 = 6$
- $a_{13} = a_{4(3)+1} = a_3 + 4 = 8$
- $a_{14} = a_{2(7)} = a_7 + 1 = 6$
- $a_{15} = a_{4(3)+3} = a_3 + 4 = 8$
- $a_{16} = a_{2(8)} = a_8 + 1 = 5$
2단계: 인덱스를 거꾸로 줄여 가며 규칙 발견하기
위 계산에서 우리가 실제로 한 일은 인덱스에 다음 세 가지 연산 중 하나를 적용하는 것이었습니다.
- 인덱스를 2배 한다: $n \to 2n$, 이때 항의 값은 $1$ 커집니다.
- 인덱스를 4배 하고 1을 더한다: $n \to 4n+1$, 이때 항의 값은 $4$ 커집니다.
- 인덱스를 4배 하고 3을 더한다: $n \to 4n+3$, 이때 항의 값은 $4$ 커집니다.
이번에는 방향을 뒤집어, 어떤 자연수 $k$에서 출발해 인덱스를 거꾸로 줄여 봅시다. 자연수 $k$를 4로 나눈 나머지를 보면 줄이는 방법이 매 단계 단 하나로 정해집니다.
- $k$가 짝수이면 $k = 2n$ 꼴뿐이므로 $n = \dfrac{k}{2}$로 줄이고, 값에서 $1$을 뺍니다.
- $k$가 홀수이고 4로 나눈 나머지가 1이면 $k = 4n+1$ 꼴이므로 $n = \dfrac{k-1}{4}$로 줄이고, 값에서 $4$를 뺍니다.
- $k$가 홀수이고 4로 나눈 나머지가 3이면 $k = 4n+3$ 꼴이므로 $n = \dfrac{k-3}{4}$로 줄이고, 값에서 $4$를 뺍니다.
한 번 줄일 때마다 인덱스는 반드시 작아지므로 이 과정은 언젠가 멈추는데, 더 이상 줄일 수 없는 인덱스는 $1$과 $3$ 둘뿐입니다. $k=1$은 위 세 꼴 어디에도 해당하지 않고, $k=3$은 $3 = 4 \times 0 + 3$이어서 $n=0$이 되는데 $0$은 자연수가 아니므로 관계식을 되돌려 쓸 수 없기 때문입니다.
1단계에서 구한 값으로 확인해 봅시다.
- $16 \to 8 \to 4 \to 2 \to 1$: 2배 연산을 4번 되돌린 것이므로 $a_{16} = a_1 + 1 \times 4 = 5$입니다.
- $13 = 4 \times 3 + 1 \to 3$: 4배 연산을 1번 되돌린 것이므로 $a_{13} = a_3 + 4 = 8$입니다.
이제 이 과정을 다시 뒤집으면, 모든 자연수 $k$는 시작점 $1$ 또는 $3$에서 출발해 위 세 연산을 차례로 적용한 결과로 딱 한 가지 방법으로 만들어진다는 것을 알 수 있습니다. 거꾸로 줄이는 방법이 매 단계 하나뿐이었으므로, 서로 다른 연산 순서는 반드시 서로 다른 $k$를 만들고 같은 $k$가 두 번 만들어지는 일도 없습니다.
시작점은 다음 두 가지입니다:
- $a_1 = 1$
- $a_3 = 4$
어떤 수 $k$를 만들 때 사용한 연산을 셀 때:
- 인덱스를 2배 하는 연산의 횟수를 $N_0$라 하고,
- 인덱스를 4배 하는 연산($4n+1$ 또는 $4n+3$)의 횟수를 $N_2$라고 해봅시다.
2배 연산은 값을 $1$씩, 4배 연산은 값을 $4$씩 올리므로 $a_k$의 값은 다음과 같이 계산됩니다:
$$a_k = (\text{시작점의 값}) + 1 \times N_0 + 4 \times N_2$$
3단계: $a_k = 10$이 되는 조건 세우기
우리가 원하는 것은 $a_k = 10$이 되는 $k$의 개수입니다. 시작점에 따라 두 가지 경우로 나누어 방정식을 풀어봅시다. ($N_0, N_2$는 0 이상의 정수)
[경우 1] 시작점이 $a_1 = 1$인 경우
$$1 + N_0 + 4N_2 = 10 \implies N_0 + 4N_2 = 9$$
이 방정식을 만족하는 음이 아닌 정수 쌍 $(N_0, N_2)$를 구합니다.
- $N_2 = 0$ 일 때, $N_0 = 9$
- $N_2 = 1$ 일 때, $N_0 = 5$
- $N_2 = 2$ 일 때, $N_0 = 1$
[경우 2] 시작점이 $a_3 = 4$인 경우
$$4 + N_0 + 4N_2 = 10 \implies N_0 + 4N_2 = 6$$
이 방정식을 만족하는 음이 아닌 정수 쌍 $(N_0, N_2)$를 구합니다.
- $N_2 = 0$ 일 때, $N_0 = 6$
- $N_2 = 1$ 일 때, $N_0 = 2$
4단계: 각 경우의 수 계산하기
이제 각 쌍에 대해 실제로 만들 수 있는 $k$의 개수를 구해야 합니다.
2배 하는 연산은 $n \to 2n$ 한 가지뿐이지만, 4배 하는 연산은 $n \to 4n+1$과 $n \to 4n+3$의 2가지 선택지가 있습니다.
따라서 $N_2$번의 4배 연산 각각에 대해 2가지씩 선택할 수 있으므로 $2^{N_2}$를 곱해주어야 합니다.
또한, 두 종류의 연산을 어떤 순서로 적용하느냐에 따라 서로 다른 $k$가 만들어지므로, 전체 $N_0 + N_2$번의 연산 가운데 4배 연산이 들어갈 자리를 고르는 조합의 수를 함께 곱해줍니다.
[경우 1] 시작점이 $a_1$인 경우의 수
- $N_2 = 0, N_0 = 9$:
2배 연산만 9번 적용하므로, 순서를 정하는 방법은 $\binom{9}{0} = 1$가지입니다.
$$\text{경우의 수} = 1 \times 2^0 = 1$$
- $N_2 = 1, N_0 = 5$:
총 6번의 연산(4배 연산 1번, 2배 연산 5번)에서 4배 연산의 자리를 고르는 방법은 $\binom{6}{1} = 6$가지이고, 그 4배 연산은 $4n+1$ 또는 $4n+3$ 중 선택할 수 있습니다.
$$\text{경우의 수} = 6 \times 2^1 = 12$$
- $N_2 = 2, N_0 = 1$:
총 3번의 연산(4배 연산 2번, 2배 연산 1번)에서 4배 연산의 자리를 고르는 방법은 $\binom{3}{2} = 3$가지이고, 4배 연산 2번 각각에 대해 2가지씩 선택할 수 있습니다.
$$\text{경우의 수} = 3 \times 2^2 = 12$$
따라서 [경우 1]의 총 개수는 $1 + 12 + 12 = 25$개입니다.
[경우 2] 시작점이 $a_3$인 경우의 수
- $N_2 = 0, N_0 = 6$:
2배 연산만 6번 적용하므로, 순서를 정하는 방법은 $\binom{6}{0} = 1$가지입니다.
$$\text{경우의 수} = 1 \times 2^0 = 1$$
- $N_2 = 1, N_0 = 2$:
총 3번의 연산(4배 연산 1번, 2배 연산 2번)에서 4배 연산의 자리를 고르는 방법은 $\binom{3}{1} = 3$가지이고, 그 4배 연산은 2가지 선택지가 있습니다.
$$\text{경우의 수} = 3 \times 2^1 = 6$$
따라서 [경우 2]의 총 개수는 $1 + 6 = 7$개입니다.
5단계: 최종 합산
어떤 $k$든 인덱스를 거꾸로 줄여 가면 도착하는 시작점이 $1$인지 $3$인지 하나로 정해지므로 두 경우는 서로 겹치지 않습니다. 따라서 두 경우의 수를 더해줍니다.
$$\text{전체 개수} = 25 + 7 = 32$$
답
$$32$$
확인해보기
위 풀이 과정을 잘 이해했는지 스스로 점검해 봅시다.
질문: 위와 동일한 규칙을 가진 수열 $\{a_n\}$에서, $a_k = 5$를 만족시키는 자연수 $k$의 개수는 몇 개일까요? (풀이 과정의 3단계와 4단계를 적용해 스스로 구해보세요!)