11월의 퍼즐에 참여해주신 모든 분들께 감사드립니다.
11월의 퍼즐 정답자는 김일희, 정수현님 두 분입니다.
(정답과 해설을 함께 제출 해주신 분이 김일희님 한 명 뿐이었으나, 김일희님께서는 기존에 정답자로 선정되셨기 때문에 이외 가장 먼저 정답을 제출해주신 정수현님을 함께 선정하였습니다.)
이 아기자기한 문제는 1999년 루마니아 수학 올림피아드 팀 선발 문제였다.
1부터 차례대로 자연수를 나열해 보면, 9까지는 각 자리 숫자의 합이 증가하다가, 다음 수인 10에서는 합이 1로 줄고, 다시 11부터 19까지는 증가하다가, 다음 수인 20에서 감소한다. 그러고 28까지는 11의 배수 없이 이어지다가 29에서 \(2+9=11\)이 되어, 1부터 시작하면 28까지 28개의 수를 나열할 수 있다.
29를 건너뛰고 30부터 나열한다고 생각해 보면, 38에서 \(3+8=11\)이 되고, 39부터 시작하여도 47에서 \(4+7=11\)이 되어 연속된 수 10개도 나열할 수가 없다.
또 수가 1씩 커지는 상황을 보면, 각 자리 숫자의 합이 1씩 증가하다가 일의 자리가 9인 수 다음에 받아올림이 하나 생기면서 합이 증가하는 양상이 바뀐다.
이상의 관찰을 토대로 생각해 보면, 28개보다 더 많은 수를 나열하려면 9를 이용하여 받아올림이 일어나는 현상을 이용하여야 하고, 28보다 큰 수를 생각하는 대신 1보다 작은 쪽으로 수를 늘려가야 함을 알 수 있다. 즉, \(1, 2, 3, \dots\) 대신에 \(10\cdots01, 10\cdots02, 10\cdots03, \dots\)으로 생각하고, 앞에 작은 수를 나열하여
\[
9\cdots99, 10\cdots00, 10\cdots01, 10\cdots02, 10\cdots03, \dots
\]
으로 생각하는 식이다.
이렇게 하면 커지는 쪽으로는 \(10\cdots18\)까지 만들 수 있고, 작아지는 쪽으로는 9가 11개여서 각 자리 숫자의 합이 11의 배수가 되는 경우를 제외하면 \(9\cdots99\) 앞에 \(9\cdots98\), 그 앞에 \(9\cdots97\) 등을 만들 수 있다.
만약 9가 하나뿐인 \(97, 98, 99, 100, \dots, 118\)인 경우라면, \(9+2=11\)이므로 이 수열 앞에는 \(93, 94, 95, 96\)이 올 수 있다.
만약 9가 두 개인 \(997, 998, 999, 1000, \dots, 1018\)인 경우라면, \(9+9+3=22\)이므로 이 수열 앞에는 \(994, 995, 996\)이 올 수 있다.
이런 식으로 생각하면, 9가 다섯 개일 때,
\[
999990, 999991, \dots, 999998, 999999, 1000000, \dots, 1000018
\]
이 가능하고 이 앞에도 999989, 999988 등이 올 수 있다. 이때 \(9+9+9+9+8+0 = 44\)이므로, 가능한 최대 길이는
\[
999981, 999982, \dots, 999990, 999991, \dots, 999999, 1000000, \dots, 1000019
\]
으로 38개가 가능하다.
만약 9가 여섯 개라면, \(9+9+9+9+9+9+1 = 55\)이므로
\[
9999992, 9999993, \dots, 999999, 1000000, \dots, 1000018
\]
이 가능하지만 38개를 넘지는 못한다. 9가 일곱 개, 여덟 개, 아홉 개, 열 개인 경우도 마찬가지이다.
\(10\cdots01\) 꼴이 아닌 경우, 예를 들어 \(20\cdots01, 20\cdots02, \dots\)를 생각해 보면 큰 쪽으로는 \(20\cdots08\)까지 가능하고 작은 쪽으로 아무리 늘려도 38개를 넘을 수는 없다.
이상의 관찰로부터, 나열할 수 있는 연속한 자연수는 최대 38임을 알 수 있다.
다음은 11월의 정답자로 선정된 김일희님의 해설입니다.
십의 자리 이상이 동일하고 일의 자리가 0부터 9까지 연속한 10개의 수의 각 자릿수합을 11로 나눈 나머지를 보면, 0~9, 1~10, 2~0, 3~1, 4~2 … , 10~8 총 11가지 경우가 존재한다. 그 중에 0을 포함하지 않는 (11을 피하는) 경우는 1~10이 유일하고, 다른 경우들은 0이 하나씩 꼭 존재한다.
백의 자리 이상이 동일한 연속한 100개의 수의 각 자릿수합을 11로 나눈 나머지를 보면, 0~9, 1~10, 2~0, 3~1, 4~2 … , 10~8 을 circular order 로 본 수열의 일부가 된다. 여기서 0을 포함하지 않는 가장 긴 sub-sequence의 길이는 0~9, 1~10, 2~0 부분에서 처음과 끝의 나머지 0을 제거한 수열로 길이가 9 + 10 + 9 = 28이다.
따라서 더 긴 길이의 수열을 찾으려면 백의 자리가 바뀌는 것을 포함하는 수열만 생각해보면 된다. 만약 백의 자리가 바뀌기 전에 0~9, 1~10 으로 끝나고, 백의자리가 바뀐 뒤에 1~10, 2~0 으로 시작해서 1~10 을 두 번 사용할 수 있다면, 처음과 끝의 0을 제거한 1~9, 1~10, 1~10, 2~10 으로 길이가 38인 수열을 만들 수 있다.
실제로 999981 부터 1000018까지 총 38개의 연속한 수가 그런 예가 된다. 일반적으로는 (11n+6) 자리에서 (11n+7) 자리로 넘어갈때 동일한 예를 발견할 수 있다.
