[해답] 특별한 10자리 숫자

아래의 문제에 대한 해답을 생각해 보자.

$0$부터 $9$까지 $10$개의 숫자를 단 한번씩만 사용하여 다음의 규칙을 만족하는 $10$자리의 숫자를 만들어라: 모든 $1 \leq n \leq 10$에 대하여, 이 숫자의 앞에서부터 $n$자리 까지가 $n$으로 나누어 떨어진다.

이 문제의 조건을 만족하는 숫자를 단순한 무차별 대입(brute force) 방법으로 해결하고자 하면 최대 $10! = 3628800$ 가지의 경우의 수를 확인해 보아야만 한다. 따라서 이 경우의 수를 줄이기 위하여 문제를 조금 더 논리적으로 접근해 보자.

우선 이 문제의 조건을 만족하는 숫자를

\[ a_{1} \, a_{2} \, a_{3} \, a_{4} \, a_{5} \, a_{6} \, a_{7} \, a_{8} \, a_{9} \, a_{10} \]

이라 하자. 먼저 이 숫자는 $10$으로 나누어 떨어져야 하므로 $a_{10} = 0$이어야만 함을 쉽게 알 수 있다. 또한 $a_{1} \, a_{2} \, a_{3} \, a_{4} \, a_{5}$가 $5$로 나누어 떨어진다는 사실로부터 $a_{5}$는 $5$ 또는 $0$임을 알 수 있고, 이미 $a_{10} = 0$임을 알고 있으므로 $a_{5} = 5$임을 알 수 있다.

\[ a_{1} \, a_{2} \, a_{3} \, a_{4} \, 5 \, a_{6} \, a_{7} \, a_{8} \, a_{9} \, 0 \]

또한 $a_{1} \, a_{2}$, $a_{1} \, a_{2} \, a_{3} \, a_{4}$, $a_{1} \, a_{2} \, a_{3} \, a_{4} \, a_{5} \, a_{6}$, $a_{1} \, a_{2} \, a_{3} \, a_{4} \, a_{5} \, a_{6} \, a_{7} \, a_{8}$이 (각각 $2$, $4$, $6$, $8$로 나누어 떨어지므로)모두 짝수여야만 한다는 사실로부터 $a_{2},\, a_{4},\, a_{6},\, a_{8} \in \{ 2,\, 4,\, 6,\, 8 \}$을 얻는다. 따라서 자동적으로 $a_{1},\, a_{3},\, a_{7},\, a_{9} \in \{ 1,\, 3,\, 7,\, 9 \}$라는 사실 또한 얻을 수 있다.

이정도 까지만 풀이를 진행하면 확인해야 하는 숫자의 경우의 수가 $4! \times 4! = 576$ 정도 밖에는 되지 않는다. 그래도 손으로 일일히 확인하기에는 꽤 큰 수이다. 이 경우의 수를 조금 더 줄이기 위해 계속 논리를 전개해 보자.

먼저 $4 \mid a_{1} \, a_{2} \, a_{3} \, a_{4}$이므로 (이 때, $p \mid q$는 "$q$가 $p$로 나누어 떨어짐"을 의미하는 수학적 용어이다.) $4$의 배수 판정법에 의하여 $4 \mid a_{3} \, a_{4}$이고, $a_{3}$은 홀수이므로 $a_{4} \in \{ 2,\, 6 \}$를 얻는다. 또한 $8 \mid a_{1} \, a_{2} \, a_{3} \, a_{4} \, a_{5} \, a_{6} \, a_{7} \, a_{8}$라는 사실로부터 ($8$의 배수는 $4$의 배수이고 따라서 $4$의 배수 판정법에 의하여) $4 \mid a_{7} \, a_{8}$를 얻고, $a_{7}$은 홀수이므로 $a_{8} \in \{ 2,\, 6 \}$를 얻는다. 결과적으로 $\{a_{4},\, a_{8} \} = \{ 2,\, 6\}$, $\{a_{2},\, a_{6} \} = \{ 4,\, 8\}$임을 알 수 있다.

이제 $3 \mid a_{1} \, a_{2} \, a_{3}$, $6 \mid a_{1} \, a_{2} \, a_{3} \, a_{4} \, a_{5} \, a_{6}$이므로 $3$의 배수 판정법을 각각 적용하면 $3 \mid a_{1}+a_{2}+a_{3}$, $3 \mid a_{1}+a_{2}+a_{3}+a_{4}+a_{5}+a_{6}$를 얻는다. 따라서 $3 \mid a_{4}+a_{5}+a_{6}$임을 알 수 있다. 여기서 $a_{5} = 5$이고 $a_{4} \in \{ 2,\, 6\}$, $a_{6} \in \{ 4,\, 8\}$이므로 문제의 조건을 만족하는 $a_{4} \, a_{5} \, a_{6}$은 258 또는 654 뿐임을 알 수 있다. 일단 $a_{4}$와 $a_{6}$가 정해지면 $a_{2}$와 $a_{6}$ 또한 자동으로 결정되므로 문제의 조건을 만족하는 숫자는 아래의 두가지 경우

\[ a_{1} \, 4 \, a_{3} \, 2 \, 5 \, 8 \, a_{7} \, 6 \, a_{9} \, 0 \]

\[ a_{1} \, 8 \, a_{3} \, 6 \, 5 \, 4 \, a_{7} \, 2 \, a_{9} \, 0 \]

중에 하나임을 알 수 있다.

이제 경우의 수는 $4! + 4! = 48$가지로 줄어든다. 조금만 더 논리를 전개해 보도록 하자.

먼저 첫번째 경우를 살펴보자.

\[ a_{1} \, 4 \, a_{3} \, 2 \, 5 \, 8 \, a_{7} \, 6 \, a_{9} \, 0 \]

이제 $8 \mid 8 \, a_{7} \, 6$과 $3 \mid a_{7} \, 6 \, a_{9}$라는 사실로부터 $a_{7} =9$, $a_{9} = 3$이여야만 함을 알 수 있다. 하지만 이 경우 두가지 경우의 수가 나오는데,

\[ 1 \, 4 \, 7 \, 2 \, 5 \, 8 \, 9 \, 6 \, 3 \, 0 \]

\[ 7 \, 4 \, 1 \, 2 \, 5 \, 8 \, 9 \, 6 \, 3 \, 0 \]

위 두가지 경우 모두 앞에서 부터 $7$자리 까지가 $7$의 배수가 아니게 된다. 따라서 첫번째 경우는 문제의 조건을 만족하지 못함을 알 수 있다.

이제 두번쨰 경우를 살펴보자.

\[ a_{1} \, 8 \, a_{3} \, 6 \, 5 \, 4 \, a_{7} \, 2 \, a_{9} \, 0 \]

이제 $8 \mid 4 \, a_{7} \, 2$와 $3 \mid a_{7} \, 2 \, a_{9}$라는 사실로부터 $a_{7} \, a_{9} = \{ 31,\, 37,\, 73,\, 79\}$임을 알 수 있고, 각각의 경우에 대하여 $a_{1}$과 $a_{3}$에 대한 경우의 수를 생각해 보면 최종적으로 아래의 $8$개의 후보만이 남는다.

\[ 5 \, 8 \, 7 \, 6 \, 5 \, 4 \, 3 \, 2 \, 1 \, 0 \]

\[ 7 \, 8 \, 5 \, 6 \, 5 \, 4 \, 3 \, 2 \, 1 \, 0 \]

\[ 1 \, 8 \, 5 \, 6 \, 5 \, 4 \, 3 \, 2 \, 7 \, 0 \]

\[ 5 \, 8 \, 1 \, 6 \, 5 \, 4 \, 3 \, 2 \, 7 \, 0 \]

\[ 1 \, 8 \, 5 \, 6 \, 5 \, 4 \, 7 \, 2 \, 3 \, 0 \]

\[ 5 \, 8 \, 1 \, 6 \, 5 \, 4 \, 7 \, 2 \, 3 \, 0 \]

\[ 1 \, 8 \, 3 \, 6 \, 5 \, 4 \, 7 \, 2 \, 9 \, 0 \]

\[ 3 \, 8 \, 1 \, 6 \, 5 \, 4 \, 7 \, 2 \, 9 \, 0 \]

이 중에서 앞에서 부터 $7$자리의 까지가 $7$의 배수인 수는 마지막 $3816547290$이 유일하다. 따라서 문제의 조건을 모두 만족하는 숫자는 $3816547290$이고 이 수는 유일하게 존재함을 알 수 있다.