07. 중국 장군의 병사 헤아리기
<알고리즘 행성 여행자들을 위한 안내서>
오래된 수학적 마술 트릭으로 이야기를 시작해보자. 구글이 있기 훨씬 전, 앞을 보지 못하는 한 중국 장군이 있었다. 전설에 따르면, 이 장군에겐 엄청난 병력을 자랑하는 부대가 있었다. 전투가 시작되기 전, 병사들의 수는 3만 명쯤 됐다. 전투가 끝난 다음 날 아침, 장군은 병사들이 얼마나 남아 있는지 알고 싶었다. 장군은 앞을 보지 못했기 때문에 학교 체육수업 때 하는 것처럼 병사들에게 스스로 번호를 외치도록 했다.
그런데 이 병사들은 수를 3만까지 셀 수 없었다. 이들은 100까지 아니 사실 35까지밖에 셀 줄 몰랐다. 장군은 어떤 기적을 행해야 전투 후 남은 병사들의 수를 헤아릴 수 있을까? 병사들이 35까지밖에 셀 수 없고, 장군이 이미 3세기에 쓰여진 중국 수학책에 나오는 숫자 이론의 계(corollary), 즉 그 유명한 중국인의 나머지 정리(Chinese remainder theorem)를 잘 알고 있다면 가능하다. 이 이론의 명칭은 앞 못 보는 중국 장군이 전투 후에 살아남은 나머지 병사들의 수를 헤아렸기 때문에 붙여진 게 아니라, 나누기를 할 때 남아 있는 나머지와 관련이 있기 때문에 붙여졌다.
초등학교 때의 기억을 떠올려보자. 소수점 다음에 오는 자리들에 대해 배우기 전, 계산이 얼마나 쉬웠는가? 21을 5로 나누면 몫은 4이고 나머지 1이 남는다. 분명한 건, 1이 더 이상 4로 나눠지지 않는다는 사실이다. 추억의 수학 책을 뒤적여보자. 나머지는 나눈 그 숫자보다 언제나 더 작다(5로 나눴는데 나머지가 8이 나온다면, 부디 그 나머지를 한 번 더 나눠주길 바란다). 나머지는 숫자의 특성이다. 우리는 2로 나누기를 했을 때의 나머지를 통해 그 숫자의 특성을 파악할 수 있다. 이때 2는 그 숫자가 짝수인지 아니면 홀수인지 알려준다. 이렇듯 어떤 숫자를 다양한 약수로 나누면서 나머지를 관찰하면, 그 숫자의 다양한 특성이 파악된다. 심지어 나머지만 살펴봐도 그 숫자가 어떤 것인지 알 수 있는 경우도 있다. 나머지는 숫자의 지문이다.
중국 장군 이야기로 돌아가보자. 우리는 1부터 30,030 사이의 모든 숫자를 확실하게 알아낼 수 있다. 그 숫자를 26, 33, 그리고 35로 나누었을 때의 나머지를 알기만 한다면 말이다. 1과 30,030 사이의 모든 숫
자는 26, 33, 35, 이 세 가지 숫자와 관련해 나머지의 조합이 모두 다르다. 이 세 가지 숫자 외에 다른 숫자들로도 이런 이야기를 할 수 있다. 다만 그 숫자들이 서로 공통 약수를 가지고 있지 않고, 그 숫자들의 곱이 최소한 우리가 찾는 수만큼 크다는 사실이 보장되어야 한다(이것이 바로 중국인의 나머지 정리다). 이 경우에는 이런 조건들이 충족된다. 26은 2 곱하기 13이고, 33은 3 곱하기 11, 35는 5 곱하기 7이다. 그러니까 공통 약수가 없다. 그 곱, 즉 26 곱하기 33 곱하기 35는 30,030이다.
앞 못 보는 장군에겐 이 나머지 정리가 구원군이나 마찬가지다. 장군은 병사들에게 일단 26까지 차례대로 세어 나가라고 지시한다. 그래서 병사들은 일반적으로 숫자를 셀 때처럼 앞사람보다 숫자를 하나씩 더 높여서 외친다. 앞사람이 26을 외친 경우에는 이야기가 달라진다. 이때 다음 병사는 다시 1을 외친다. 이런 방법으로 장군은 마지막 병사의 외침을 통해서 26으로 나눈 나머지를 알게 된다. 그런 다음에는 다시 다음 숫자 세기가 시작된다. 이번엔 33까지만 외친다. 그리고 마지막으로 35까지 숫자 세기를 한다. 그런데 작은 문제가 있다. 장군은 이제 자신의 병력을 분명히 규정해주는 나머지에 대해선 다 알고 있지만, 그 병력 자체의 정확한 숫자는 아직도 모르고 있다. 지도는 있지만 길은 아직 없는 것과 마찬가지다. 이 나머지들로부터 숫자를 규정해내는 알고리즘이 없는 것이다.
그런데 주어진 나머지 숫자들의 조합을 통해 그에 해당하는 최소의 숫자를 알아볼 수 있는 쉽고 빠른 알고리즘이 있다. 이건 일종의 유클리드 알고리즘(Euclidean algorithm: 주어진 두 자연수 사이의 최대 공약수를 구하는 알고리즘)의 확대 버전이다. 우리는 알고리즘과 기준의 공생관계를 잘 알고 있다. 중국인의 나머지 정리는 알고리즘이 아니다. 이건 수학적 진술일 뿐이다. 이 이론은 얼마 되지 않는 특징들, 즉 나머지들을 토대로 해서 매우 커다란 수를 규정하기 위한 기준을 제공한다. 그 기준은 두 개의 알고리즘 사이에 꽉 맞물려 있다. 나머지를 규정하기 위한 분할식 숫자 헤아리기가 그 첫 번째 알고리즘이다. 다른 하나는 여기에선 설명하지 않은 것인데, 나머지에 맞는 가장 작은 수를 찾아내기 위한 알고리즘이다.
이를 위해선 확실하게 공식화되어 있는 두 가지 조건이 반드시 충족돼야 한다. 첫째, 차례대로 헤아리기 위한 숫자들(예컨대, 26, 33, 35)에 공통 약수가 있어서는 안 된다. 둘째, 그 곱이 우리가 찾는 숫자만큼 커야 한다. 솔직히 말해, 첫 번째는 수학적으로 검증 가능한 조건이다. 하지만 두 번째 조건은 비수학적인 논의가 필요하다. 전투 전 병사들의 수가 30,030명보다 적었던 것은 아닐까? 어쩌면 절반은 숨어 있었을지도 모른다.
100까지 세지 못하는 병사들은 장군이 내린 결론이 옳은지에 대해 논의할 능력이 되지 않는다. 하지만 그 전제조건에 대해서는 다들 충분히 논의해볼 수 있다. 한편 수학과 알고리즘이 잘못 연결되면 스스로 무능해지는 결과를 초래할 수 있으며, 그로 인해 순식간에 위험에 빠질 수도 있다. 전투가 끝난 후 병사 29,206명이 남았다고 해보자. 이 부대는 예전과 거의 똑같이 강력하다. 병사들은 26까지 여러 번 세고 나서 이렇게 말한다. “나머지가 8입니다.” 이번에는 33으로 센다. 이번엔 나머지가 1이다. 그런 다음 마지막으로 세 번째 숫자 35로 다시 세는 과정에서 병사 한 명이 집중력이 떨어져 그만 하나를 더 많이 센다. 그래서 원래는 나머지가 16이어야 하는데, 17이 나오고 만다. ‘별일 아닐 거야’라고 병사들은 속으로 생각한다. ‘거의 다 있잖아. 하나 더 많은 건 중요하지 않지.’ 그러나 그 마지막 숫자를 들은 장군의 얼굴은 얼어붙고 만다. 그러고는 거의 도망이나 다름없는 퇴군을 명령한다. 나머지가 8, 1, 그리고 17인 숫자는 892이기 때문이다.
중국인의 나머지 정리를 이용한 이 신기한 숫자 세기는 사실 매우 예민한 사안이다. 조금만 오차가 있어도 그 결과가 세계를 바꿔놓을 수도 있기 때문이다. 하지만 확실하게 정의된 전제조건들이 있고, 그 조건들이 충족되기만 한다면, 수학적 확실성으로 이루어진 이 방법은 정답을 내놓는다. 만일에 대비해 알고리즘에 오류 경고 기능을 넣을 수도있다. 그냥 두 번 헤아려서 검산하게 할 수도 있다. 하지만 이런 것들로 근본적인 문제가 크게 달라지지는 않는다. 알고리즘은 여전히 눈 먼 장군과 비슷하다. 알고리즘은 올바른 데이터가 입력될 때에만 제대로 기능한다. 그렇기 때문에 그 결과에 대한 책임은 우리에게 있다.
