콜라츠 추측
우박처럼 오르내리다 1로 떨어집니다
아무 수나 하나 고르세요. 짝수면 반으로 나누고, 홀수면 세 배 한 뒤 1을 더합니다. 그것을 계속 되풀이합니다.
27로 시작해 보세요. 111까지 치솟았다가 떨어지고, 다시 9232까지 뛰어오릅니다. 우박이 구름 속에서 오르내리듯 합니다. 1937년에 던져진 이 물음을 지금까지 아무도 풀지 못했습니다. 이 수는 결국 어디로 갈까요?
이야기
Jacobs, Konrad
CC BY-SA 2.0 de · 위키미디어 공용
수를 하나 고르세요. 짝수면 반으로 나누고, 홀수면 3배 하고 1을 더합니다. 그리고 되풀이합니다.
7로 해 봅시다. 7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1.
올라갔다 내려갔다 하다가 결국 1에 닿습니다. 그래서 우박 수라고도 부릅니다. 우박이 구름 속에서 오르내리다 떨어지는 것 같아서입니다.
어떤 수로 시작해도 1에 닿는 것 같습니다. 컴퓨터로 어마어마하게 큰 수까지 확인했습니다. 모두 1에 닿았습니다.
그런데 아무도 증명하지 못했습니다. 규칙은 초등학생도 이해합니다. 그런데 세계 최고의 수학자들이 백 년 가까이 손을 대지 못했습니다.
수학자 에르되시는 이렇게 말했습니다. “수학은 아직 이런 문제를 다룰 준비가 되어 있지 않다.”
실용은 없습니다. 규칙은 초등학생도 아는데 백 년 가까이 아무도 못 풀었습니다.
그래도 값집니다 — 「간단해 보이는 것이 반드시 쉬운 것은 아니다」를 가장 또렷하게 보여 주는 문제입니다. 컴퓨터로 2의 68제곱까지 확인했지만, 확인은 증명이 아닙니다.
계단 넷 — 같은 사실을 네 깊이로
수를 골라 직접 따라간다
숫자 7을 골라 규칙을 따라가 봅니다. 홀수이니 가 되고, 짝수이니 반으로 나누어 11, 다시 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1이 됩니다.
구름 속에서 우박이 오르내리듯 숫자가 커졌다 작아지다 마침내 1에 닿는 신기한 여정을 다른 숫자로도 직접 손으로 계산해 보세요.
짝수면 반으로, 홀수면 3배+1
그러고도 결국 1 로 떨어집니다.
몇 걸음에 닿나 표로
시작하는 수에 따라 1에 도달하는 단계 수(우박수 길이)가 천차만별입니다. 숫자 27은 겨우 두 자리 수이지만 무려 111단계를 거치며 최고 9232까지 치솟은 뒤에야 1로 떨어집니다.
컴퓨터로 이 넘는 천문학적인 수까지 전부 확인해 보았지만 예외 없이 모두 1로 돌아왔습니다. 하지만 모든 수에 대해 참이라고 말하려면 단 하나의 예외도 없다는 논리적 증명이 필요합니다.
어디까지 치솟나
그런데도 지금까지 시험한 모든 수가 1 에 닿았습니다.
왜 어려운가·이진법으로 보기
콜라츠 수열을 이진법으로 변환해 보면 홀수 연산 은 비트열을 섞고 늘리며, 짝수 연산 은 하위 비트를 지우는 동역학계(Dynamical System)의 카오스적 성질을 띱니다.
수학자 테렌스 타오(Terence Tao)는 2019년 거의 모든 자연수에 대해 콜라츠 수열이 시작 값보다 훨씬 작은 값으로 도달한다는 것을 편미분방정식과 확률론적 기법으로 증명하여 현대 수학의 가장 위대한 진전을 이루어냈습니다.
왜 내려올까요
두 걸음에 평균 ×3/2 ÷2 = ×0.866 — 그래서 줄어드는 쪽으로 기웁니다.
미해결 문제의 얼굴
20세기 최고의 수학자 폴 에르되시는 콜라츠 추측을 두고 "수학은 아직 이런 문제를 풀 준비가 되어 있지 않다"고 경고했습니다.
단순한 규칙 뒤에 계산 불가능성(Undecidability)과 튜링 완전성, 튜링 기계의 정지 문제(Halting Problem)와 유사한 논리적 장벽이 숨어 있을 가능성이 제기되며 정수론과 이론 컴퓨터 과학의 극한 경계에 서 있습니다.
아직 아무도 못 풀었습니다
에르되시가 말했습니다 — 「수학은 아직 이런 문제에 준비가 안 돼 있다.」
풀어 보기
우박 수열 따라가기. 자연수 에 대해 짝수이면 , 홀수이면 을 취한다.
(1) 숫자 6으로 시작할 때 1에 도달할 때까지 거치는 수열을 순서대로 모두 쓰시오.
(2) 수열이 1에 도달한 후 계속 연산을 적용할 때 순환하는 세 숫자의 주기를 쓰시오.
(3) 역으로 1단계 연산 후에 16이 될 수 있는 직전의 자연수 두 개를 모두 구하시오.
(3) 짝수 연산 에서 , 홀수 연산 에서 가 나옵니다.
답과 풀이 보기
(1)
여덟 걸음입니다. 6 은 짝수라 절반, 3 은 홀수라 — 올라갔다 내려갔다 하며 우박처럼 떨어집니다.
(2) — 주기 3 입니다.
1 은 홀수라 , 4 는 절반이 2, 2 는 절반이 1. 여기 들어오면 영원히 이 셋을 돕니다.
(3) 32 와 5 입니다.
· 짝수였다면
· 홀수였다면 — 5 는 실제로 홀수이므로 됩니다.
⭐ 늘 둘인 것은 아닙니다. 이 3 의 배수가 되는 일은 없으므로, 이를테면 12 의 앞자리는 24 하나뿐입니다.
1937 년 콜라츠가 낸 이 물음은 지금까지 까지 전부 1 로 떨어졌습니다. 그런데 모든 수가 그렇다는 증명은 아직 없습니다. 에르되시는 말했습니다 — 수학은 아직 이런 물음에 답할 준비가 되어 있지 않다.
여기 「풀어 보기」는 기본 한 벌입니다. 더 풀어 보고 싶으면 행복수학의 그 단원으로 건너가세요.
더 멀리
「쉬운데 아무도 못 푸는 문제」는 수학의 얼굴 가운데 하나입니다.
- 골드바흐 추측 · 쌍둥이 소수 — 역시 말은 쉬운데 아직 미해결입니다
- 분산 계산 — 자원자들의 컴퓨터가 지금도 큰 수를 검사하고 있습니다
- 직접 해 보기 — 27로 시작하면 111걸음이나 걸리고 9232까지 올라갑니다
이어지는 장
짝수면 반으로 나누고 홀수면 3배에 1을 더하는 단순한 계산을 반복할 뿐인데 끝내 1로 떨어지는 우박수의 여정은, 네 자리 수의 뺄셈을 되풀이하여 신비로운 수 6174에 도달하는 제16장 과 함께 수의 순환과 수렴이 품은 깊은 수수께끼를 보여 줍니다.
영감을 받은 곳
독일의 수학자 로타어 콜라츠(Lothar Collatz)가 1937년 함부르크 대학교 시절 구상하여 수학계에 제시한 문제로, '3n+1 문제' 또는 '우박수(Hailstone sequence)'라는 이름으로 널리 알려져 있습니다.