d라이브러리

좋은 수학올림피아드 문제를 만들어낸다는 것은 굉장히 어려운 일입니다. 그동안 기출된 수많은 문제들을 다 제외하고서 새로운 문제를 출제하는 것조차 힘든데, 멋지고 재미있기까지 해야 하니까요. 대부분의 나라에서 그런 출제의 어려움을 겪고 있는데, 좋은 문제가 끊임없이 출제되는 나라가 있습니다. 그것은 러시아입니다. 러시아에서는 국가 대회에서는 물론이고 도시대항 국제수학토너먼트(TOT)나 시도 대회에 이르기까지 거의 모든 대회에서 훌륭한 문제들이 출제됩니다. 우수한 출제위원이 매우 많다는 것이지요. 이것은 ‘수학동아리’로 대변되는 러시아의 독특한 학생 수학클럽 문화에 의한 것으로 보입니다. 러시아에서는 대학 교수들이나 대학생들이 자신들의 당연한 임무인 것처럼 수학동아리들을 운영하며 학생들에게 수학을 공부하고 경쟁하는 즐거움을 전수해왔습니다. 한국에서는 KAIST 수학문제연구회가 그러한 역할을 담당해온 대표적인 단체인데, 비유하자면 러시아에는 KAIST 수학문제연구회와 같은 팀이 매우 많았던 것이지요.

TOT(도시대항 국제수학토너먼트) 1992년 가을 중등부 O레벨 3번
임의의 자연수 M에 대해, M의 배수들 중에 (십진법으로) 자릿수의 합이 홀수인 수가 존재함을 증명하여라.

아주 당연해 보이는 것을 묻고 있는 문제입니다. M의 배수는 무한히 많고, 그 각각은 자릿수의 합이 홀수 아니면 짝수인데, 계속 M을 더하며 자리가 늘어남에 따라 자릿수가 아주 다양하게 나타날 거라서 자릿수의 합이 짝수인 것만 나타나기는 어려울 테니까요. 그런데, 그것을 증명하라고 요구하고 있습니다. 사실 이런 당연해 보이는 사실을 묻는 문제가 어려운 문제일 때가 많습니다.

한편, ‘M의 배수들 중에 자릿수의 합이 짝수인 수가 존재함’을 보이라고 했다면 그것은 문제가 아주 쉬울 겁니다. M을 두 번 연속해서 이어 쓴 수(즉, M이 n자리의 수이면 M·${10}^{n}$+M)를 생각하면 바로 그런 수가 되니까요. 그렇지만 자릿수의 합이 홀수인 배수는 이런 식으로는 만들어지지 않아서 좀 더 어렵습니다.

그럼 이 문제의 분석을 시작해봅시다. M 스스로의 자릿수의 합이 홀수이면 M 자신도 M의 배수라서 이미 원하는 수를 찾은 것이 됩니다.

따라서, M의 자릿수의 합이 짝수일 때만 보면 됩니다. 간단한 경우부터 살펴보며 힌트를 얻어내야 할 테니, 먼저 M이 한 자리의 수일 때를 살펴봅시다. 그럼, M이 한 자리의 짝수일 때만 고려하면 됩니다. M에 M을 계속 더하다가 처음으로 두 자리의 수가 될 때는 $\overline{1a}$꼴이 되고, 그때 a는 짝수이므로 자릿수의 합 1+a는 홀수가 되어 원하는 수를 찾았습니다.

이제 M이 두 자리의 수일 때를 생각해봅시다. 두 자리의 수만 되어도 M에 M을 계속 더하며 관찰할 때, 양상이 아주 다양해서 원하는 수를 딱 잘라 찾아내기가 쉽지 않음을 느끼게 됩니다. 예를 들어 M=22라면, 22,44, 66, 88, 110, 132, 154, 176, 198, 220, 242, 264, 286 다음 308에서나 처음 그런 수가 나타납니다.

좀 큰 수라도 상관없으니, 늘 일정한 패턴으로 말할 수 있는 예를 생각해야 일반화된 풀이를 할 수 있겠습니다. 2200에서 22를 뺀 2178과, 22000에서 22를 뺀 21978을 생각하면, 자릿수로 9 하나만 추가되었으므로 계산해보지 않아도 둘은 자릿수의 합의 홀짝이 다름을 확신할 수 있습니다. 이것이면 좋은 풀이를 만들 수 있겠습니다.

고봉균 선생님의 풀이

M이 n자리 이하의 수라고 하자. 두 수 A=(${10}^{n-1}$)M = ${10}^{n}$(M-1)+(${10}^{n}$-M), B=(${10}^{n-1}$-1)M = ${10}^{n-1}$(M-1)+9·${10}^{n}$+(${10}^{n}$-M)를 비교하면, B는 A에서 ${10}^{n}$10n자리에 9를 끼워 넣은 것이므로, 자릿수의 합이 9만큼 더 크다. 즉, 자릿수의 합의 홀짝이 다르므로, A와 B 둘 중 하나는 자릿수 합이 홀수인 M의 배수이다. 물론 이것과 다른 풀이도 얼마든지 있을 수 있습니다.