Problems and Solutions #027

Problem #027

양의 정수 $n = a_{1} a_{2} a_{3} \cdots a_{2017}$이 $0$이 아닌 수 $a_i \in \{ 1,\,2,\, \ldots,\, 9\}$로만 이루어진 $2017$ 자리의 수라고 하자. 이 때, $n$ 자체가 $2017$으로 나누어 떨어지거나, 또는 적당히 $a_i$를 $0$으로 바꾸어 얻은 수가 $2017$로 나누어 떨어지게 할 수 있음을 증명하여라. (단, 모든 $a_i$를 $0$으로 바꾸는 것은 금지한다.)

우선 $n_0 = 0$으로 정의하자. 또한 임의의 $k = 1,\,2,\, \ldots,\, 2017$에 대하여, $n_k$가 $n$에서 앞에서부터 $k$자리 이후의 모든 자리를 $0$으로 바꾸어 얻은 수라 하자. 즉,

\[ n_k = a_{1} a_{2} \cdots a_{k} 0 0 \cdots 0 \]

과 같이 정의한다. 그러면 비둘기집의 원리(pigeon hole principle)에 의해 $2018$개의 정수 $n_0,\, n_1,\, n_2,\, \ldots,\, n_{2017}$ 중에서 법(modulo) $2017$에 대하여 합동인 두 수가 반드시 존재한다. 이 두 수를 $n_{k_1}$, $n_{k_2}$라 하자. 일반성을 잃지 않고 $k_2 > k_1$라 가정하면,

\[ n^* := n_{k_2} - n_{k_1} \]

은 $2017$로 나누어 떨어진다. 또한 $n^*$는 주어진 정수 $n$에서 앞에서부터 $k_1$개의 자리와 뒤에서부터 $(2017-k_2)$개의 자리를 $0$으로 바꾼 수이다. 또한 $k_2>k_1$이라 가정했으므로, 

\[ k_1 + (2017-k_2) < 2017 \]

이 되어, $n^*$은 $0$이 아님을 알 수 있다. 따라서 $n^* := n_{k_2} - n_{k_1}$은 문제의 주어진 조건을 만족하는 수이다.