Problems and Solutions #027

Problem #027

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

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

$$n_k=a_1{a}_2\cdots a_{k}00\cdots 0$$

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

$$n^{\ast }:=n_{k_2}-n_{k_1}$$

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

$$k_1+(2017-k_2)<2017$$

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