어떤 문제인가
이 문제는 주어진 독특한 관계식(귀납적 정의)을 만족하는 수열에서, 특정 값($a_k = 10$)을 갖는 항의 개수를 찾는 문제입니다.
이 문제를 해결하기 위해 사용할 핵심 개념은 다음과 같습니다:
- 수열의 규칙성 찾기: 처음 몇 개의 항을 직접 구해보며 규칙을 파악합니다.
- 이진법(Binary Representation)과의 연결: 인덱스 $n$을 2배($2n$) 하거나 4배($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단계: 이진법 규칙 발견하기
숫자들의 인덱스 $k$를 이진법으로 나타내면 놀라운 규칙이 보입니다!
- $a_{2n} = a_n + 1$ 은 이진수 표현에서 뒤에 `0`을 하나 붙이면 값이 1 증가한다는 뜻입니다.
- $a_{4n+1} = a_n + 4$ 와 $a_{4n+3} = a_n + 4$ 는 이진수 표현에서 뒤에 `01` 또는 `11`을 붙이면 값이 4 증가한다는 뜻입니다.
즉, 모든 자연수 $k$는 이진수로 나타냈을 때 가장 기본이 되는 시작점(Base)에서부터 뒤에 `0`을 붙이거나, `01` 또는 `11`을 붙여가며 만들어진다고 생각할 수 있습니다.
시작점(Base)은 다음 두 가지입니다:
- $a_1 = 1$ (이진수 `1`)
- $a_3 = 4$ (이진수 `11`)
어떤 수 $k$의 이진수 표현 뒤에 붙은 것들을 분석할 때:
- 붙인 `0`의 개수를 $N_0$라 하고,
- 붙인 `01` 또는 `11`의 개수를 $N_2$라고 해봅시다.
그러면 $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$의 개수)를 구해야 합니다.
`0` 블록은 1가지 형태(`0`)뿐이지만, 두 자리 블록은 `01`과 `11`의 2가지 선택지가 있습니다.
따라서 $N_2$개의 두 자리 블록 각각에 대해 2가지씩 선택할 수 있으므로 $2^{N_2}$를 곱해주어야 합니다.
또한, 이 블록들을 나열하는 순서에 따라 서로 다른 이진수가 만들어지므로 같은 것이 있는 순열(또는 조합)을 이용해 나열하는 경우의 수를 구합니다.
[경우 1] 시작점이 $a_1$인 경우의 수
- **$N_2 = 0, N_0 = 9$**:
`0`만 9개 나열하므로, 나열하는 방법은 $\binom{9}{0} = 1$가지입니다.
$$\text{경우의 수} = 1 \times 2^0 = 1$$
- **$N_2 = 1, N_0 = 5$**:
총 6개의 블록(두 자리 블록 1개, `0` 블록 5개)을 나열하는 방법은 $\binom{6}{1} = 6$가지이고, 두 자리 블록은 `01` 또는 `11` 중 선택할 수 있습니다.
$$\text{경우의 수} = 6 \times 2^1 = 12$$
- **$N_2 = 2, N_0 = 1$**:
총 3개의 블록(두 자리 블록 2개, `0` 블록 1개)을 나열하는 방법은 $\binom{3}{2} = 3$가지이고, 두 자리 블록 2개 각각에 대해 2가지씩 선택할 수 있습니다.
$$\text{경우의 수} = 3 \times 2^2 = 12$$
따라서 [경우 1]의 총 개수는 $1 + 12 + 12 = 25$개입니다.
[경우 2] 시작점이 $a_3$인 경우의 수
- **$N_2 = 0, N_0 = 6$**:
`0`만 6개 나열하므로, 나열하는 방법은 $\binom{6}{0} = 1$가지입니다.
$$\text{경우의 수} = 1 \times 2^0 = 1$$
- **$N_2 = 1, N_0 = 2$**:
총 3개의 블록(두 자리 블록 1개, `0` 블록 2개)을 나열하는 방법은 $\binom{3}{1} = 3$가지이고, 두 자리 블록은 2가지 선택지가 있습니다.
$$\text{경우의 수} = 3 \times 2^1 = 6$$
따라서 [경우 2]의 총 개수는 $1 + 6 = 7$개입니다.
5단계: 최종 합산
두 경우는 서로 겹치지 않으므로(시작하는 이진수가 `1`과 `11`로 다름), 두 경우의 수를 더해줍니다.
$$\text{전체 개수} = 25 + 7 = 32$$
답
$$32$$
확인해보기
위 풀이 과정을 잘 이해했는지 스스로 점검해 봅시다.
질문: 위와 동일한 규칙을 가진 수열 $\{a_n\}$에서, $a_k = 5$를 만족시키는 자연수 $k$의 개수는 몇 개일까요? (풀이 과정의 3단계와 4단계를 적용해 스스로 구해보세요!)