d라이브러리

요즘 과학 전문 채널이 생겨서 종종 즐겁게 시청하고 있습니다. 필자가 어렸을 때도 저런 방송이 있었으면 참 좋았겠다 하는 생각에 여러분들이 부러워지기도 합니다. 그런 한편, 수학 전문 채널은 왜 없을까 하는 생각도 들어서 아쉽기도 합니다. 그런데, 수학동아가 있더군요. 이번에도 즐거운 문제를 준비했습니다.


TOT 1983년 봄 O레벨 고등부 4번

원형으로 둘러앉은 아이들이 모두 각각 짝수개의 사탕을 갖고 있다. 모두 동시에 자기가 갖고 있는 사탕의 절반을 바로 오른쪽 아이에게 넘겨준다. 이 사탕 돌리기를 한 번 하고 났을 때 홀수개의 사탕을 갖게 된 아이는 어른으로부터 사탕 하나를 더 받아 짝수개가 되도록 한다. 이런 사탕 돌리기를 계속 반복하면 언젠가는 모든 아이가 같은 수의 사탕을 갖게 됨을 증명하여라.

쉽지 않은 문제이지만,‘도시대항 국제수학토너먼트(TOT)’문제답게 특별히 요구되는 지식은 없습니다. 문제의 상황에 대한 충분한 관찰과 발견, 그리고 그것을 수학적인 논리로 증명하는 능력만 있으면 됩니다. 우선 충분한 관찰을 해봅시다. 처음에 주어진 사탕의 개수에 따라 많은 실험을 해보면 문제의 결과는 항상 성립하는데, 모든 아이가 같은 수의 사탕을 갖게 되기까지는 상당한 시간이 필요할수 있음을 느낄 수 있습니다. 가장 많은 사탕을 가진 아이의 사탕의 개수를 2M, 가장 적은 사탕을 가진 아이의 사탕의 개수를 2m이라 하겠습니다. 대체로 2M과 2m의 차이가 차차 줄어든다는 것을 알 수 있지만, 그 차이가 매 작업마다 줄어드는 것은 아닙니다.
매 작업마다 줄어드는 것이 아니더라도, 언젠가 줄어든다면 결국 그 차이는 0이 될 것입니다. 그럼 과연 언제쯤이면 줄어든다고 말할 수 있을까요?


고봉균 선생님의 풀이

쉽게 파악되는 사실부터 천천히 정리해봅시다.

(1) m은 줄어들지 않는다. M은 커지지 않는다.

위의 명제는 쉬운 사실이므로 확인은 여러분에게 맡기겠습니다. 이제 M≠m일 때, M과 m의 차이가 언젠가는 줄어드는 것을 확인해야 합니다. M이 언젠가 줄어들거나 m이 언젠가 늘어난다는 것을 확인하고 싶은데, M이 언젠가 반드시 줄어드느냐 하는 것은 사실은 참이 아닙니다. M은 다음과 같이 처음부터 끝까지 전혀 줄어들지 않는 경우가 (아주 많이) 존재합니다.
 

M이 줄어들지 않을 수 있는 주요한 이유는 사탕의 개수가 홀수가 되었을 때 사탕 하나를 더 받는다는 조건 때문으로 보입니다. 반면에, m은 틀림없이 언젠가 반드시 커지는 것으로 보입니다. 그것을 확인해야겠습니다. 먼저, 각 아이가 가진 사탕의 개수는 때로 줄어들 수 도 있지만, 다음의 사실은 늘 성립합니다.


(2) 2m개보다 많은 사탕을 가졌던 아이는 늘 2m개보다 많은 사탕을 가지게 된다.

이 아이가 가졌던 사탕의 개수를 2a라 하면(a>;m), 오른쪽으로 a개를 주고 왼쪽에서 m개 이상을 받으므로, 새 사탕의 개수는 최소 a+m>;m+m으로 (2a보다 작을 수는 있지만 그렇다 하더라도) 역시 2m보다는 많습니다. 그 새로운 개수를 2a′이라 하면, a′>;m이므로 같은 논리로 반복되겠지요. 이제 m이 언젠가는 커진다는 것을 확인할 때가 되었습니다. m이 한 번의 작업으로 커지는 것은 아니지만, (2)에 의해 새로 최소 개수의 사탕을 가진 아이로 합류되는 경우는 없음을 확인했습니다. 즉, 2m개의 사탕을 가진 아이의 수는 늘어나지 않습니다.


(3) 최소 개수 2m개의 사탕을 가진 아이의 수는 (매 작업마다) 줄어든다.

최소 개수 2m개의 사탕을 가진 아이가 다음번에도 사탕의 개수가 그대로 2m개로 유지되는 경우는 그왼쪽의 아이도 2m개의 사탕을 가지고 있었을 때뿐입니다. M>;m이라서 모든 아이가 2m개씩의 사탕을 가진 것은 아니므로, 이 최소 개수의 사탕을 가진 아이들이 여러 명 연속해 있어도, 그 중 가장 왼쪽에있는 아이, 즉 그보다 왼쪽에는 더 이상 최소 개수의 사탕을 가진 친구가 없는 아이가 존재합니다. 그 아이는 한 번 작업하면 더 이상 최소 개수의 사탕을 가진 아이가 아니게 됩니다. 즉, 한 번 작업할 때마다 최소 개수의 사탕을 가진 아이들의 열의‘길이’가 반드시 줄어듭니다. 따라서, (3)이 틀림없이 성립함을 알 수 있습니다.

이제 증명이 거의 다 되었습니다. 최소 개수의 사탕을 가진 아이의수가 줄어들다 보면, 언젠가는 0명이 될 테고, 그것은 m이 증가했음을 뜻하니까요. 굳이 전체 작업 횟수를 대충 계산해본다면, 아이들이 모두 n명이라 할 때, m이 유지되지 못하는 데에 n번의 작업이면충분하므로, (M-m)n번의 작업이면 틀림없이 모든 아이들이 같은 개수의 사탕을 갖게 됩니다.