수학의 미스테리 (1) - 우박수 문제

원문 출처 : http://www.dogdrip.net/149993492 (글 : 테플로탁슬)

이미지 출처 : 책, 괴테 악마와 내기를 하다

악마가 당신에게 한 가지 내기를 제안한다

먼저 당신이 아무 숫자나 하나 제시한다

당신은 숫자가 홀수일 경우 그 수에 3배를 하고 1을 더한다

악마는 숫자가 짝수일 경우 그 수를 2로 나눈다

이런 식으로 계속 숫자를 바꿔 가는데,

만약 숫자가 계속 줄어 1이 나오면 악마가 이기며, 숫자가 계속 늘어나거나 같은 숫자가 계속 순환하면서 1이 나오지 않으면, 당신이 이긴다

당신은 이 내기를 받아들일 것인가? 

로타르 콜라츠 (1910-1990)

우박수 문제, 또는 콜라츠 추측이라 불리는 수학 문제를 게임으로 설명해 봤어

1937년, 수학자 로타르 콜라츠가 최초로 제시한 이 문제는,

정수론 분야에서 현재까지도 미해결된 문제 중 하나야

게임으로 비유해서 설명했듯이, 임의의 자연수 N으로 시작해.

숫자가 홀수면 3N+1, 짝수면 N을 2로 나누는 과정을 계속 반복해자는 거지.

직관적으로 생각하면 자연수는 홀수 아니면 짝수고,

나는 3배를 하는데 악마는 2분의 1로 줄이니까 내가 유리하지 않나 싶지만,

홀수를 3배하고 1을 더하면 짝수가 되는데 반해, 짝수를 2로 나눠도 짝수인 경우도 있어서 악마가 유리한 측면도 있어.

콜라츠는 N을 어떤 수로 시작해도, 결국 1로 떨어진다고 추측했어

아직 증명이 되지 않았고 반례도 발견되지 않았기 때문에 추측이라 불리지.

문제 자체는 초등학생도 이해하기 쉬운데 반해,

수학적인 증명은 문제가 제시된 이래 80년이 지났는데도 나타날 기미가 안 보여서 악명이 높은 문제야

출처 : 네이버 캐스트

3으로 시작하는 경우와, 7로 시작하는 경우를 예로 들어보자

3으로 시작하면 8번 만에 1이 되고,

7로 시작하면 16번 만에 1로 떨어지는 것을 확인할 수 있네

이처럼 모든 자연수에 대해서 유한 번의 과정을 거치면 1로 떨어지느냐, 아니면 1이 나오지 않는 수열이 있느냐가 문제인 거지.

현재 컴퓨터로 확인한 바에 의하면,

5 곱하기 10의 18승, 즉 500경까지는 모두 1로 떨어진다고 해

즉, 저 게임에서 내가 500경 이하의 수를 제시하면 내 패배는 확실하다는 거지

승산이 있으려면 500경보다 큰 수를 제시해야 겠지만, 이 역시 확인이 안 될 뿐이지, 

만약 콜라츠 추측이 참이라면 어떤 수를 제시해도 내기에 승산은 없겠네.

이 그래프는 27로 시작했을 때, 

숫자가 어디까지 커지는 지를 나타낸 그래프야

77번째 단계에서 9232 만큼 커지는 데, 이후에 급격하게 줄어들어서 결국 1이 되지

숫자가 커지고 작아지는 변화가 마치 우박 같다고 해서 우박수라는 이름이 붙었어

그럼 직접적인 증명 대신에, 확률을 이용해서 참일 확률이 높은지 거짓일 확률이 높은지 살펴보자

홀수에는 4로 나눈 나머지가 1인 홀수와 4로 나눈 나머지가 3인 홀수가 있어

다시 4로 나눈 나머지가 1인 홀수는 8로 나눈 나머지가 1인 홀수와, 8로 나눈 나머지가 5인 홀수로 나눌 수 있지

만약 홀수가 4로 나눈 나머지가 3이라고 하자

우박수 과정을 거치면,

파란 화살표는 3N+1 이고, 빨간 화살표는 2로 나눈 과정이야

4n+3은 6n+5로 커져서, 근사치로 6/4배 만치 커진다고 볼 수 있겠네

8로 나눈 나머지가 1인 홀수는, 과정을 거치면 6n+5로 줄어서, 근사치로 6/8배 만치 줄어들어

다시 8로 나눈 나머지가 5인 홀수는 16으로 나눈 나머지가 5인 홀수와 16으로 나눈 나머지가 13인 홀수로 나뉘지?

16으로 나눈 나머지가 13인 홀수는 6/16 배로 줄어드네

이렇게 확률적으로 숫자가 얼마나 커지고 얼마나 줄어드는지를 따져보면,

한 번 시행 했을 때 크기 변화의 기댓값을 구할 수 있어

계산을 해 보면 한 번 시행했을 때의 기댓값이 3/4배가 나오네

즉, 시행을 할 수록 숫자는 줄어든다고 볼 수 있으니까 1로 간다고 해도 어색할 게 없지

이렇게 보면 콜라츠 추측은 참이 아닐까?

아쉽게도 3N+1 을 3N-1 로 바꾸면 이러한 확률론적 접근이 아무 의미 없다는 것을 알 수 있어

3배를 한 다음에 1을 더하는 게 아니라 뺀다고 치고 과정을 반복하면,

5까지만 가도 1이 나오지 않는 순환이 나와 반례가 되지

5 뿐만 아니라 17로 시작해도 다시 17이 나와

근사적으로 3N+1과 3N-1은 크기 변화가 비슷하기 때문에 확률의 기댓값도 비슷하지만, 3N-1의 경우 반례를 확인하는 게 어렵지 않다는 거야.

500경 이상의 숫자 중에서, 이러한 반례가 하나만 존재해도 콜라츠 추측은 거짓이기 때문에,

추측의 참거짓을 증명하기 위해서는 직접적인 증명이 필요한 것이지

근데 재밌는 건, 3N-1 의 경우에도 수학자들이 1억까지 확인해 봤는데, 

5로 시작하는 경우와 17로 시작하는 경우 나오는 숫자들을 제외하고는, 3N+1 의 경우처럼 전부 1로 떨어진다고 해

즉, 아직까지 발견된 반례가 위에 나온 수열, 단 둘이라는 거야

1을 더하는 것과 1을 빼는 것이 어떤 차이가 있길래

한 쪽과 다르게 한 쪽은 순환이 발견되지 않는 걸까? 

폴 에어디시 (1913-1996)

이 문제에 500달러 현상금을 건 수학자 에어디시는,

우박수 문제에 대해 이렇게 말했어

"우리의 수학은 아직 이 문제를 풀 준비가 되어 있지 않습니다"

에어디시 사망 이후 20년이 지났지만,

아직 우리에겐 준비가 더 필요한 것 같네