과학

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

devil.jpg

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



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

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

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

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


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

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

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




collatz.jpg

로타르 콜라츠 (1910-1990)


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

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

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


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

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


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

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

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


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

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


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

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





3.jpg

7.jpg

출처 : 네이버 캐스트


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


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

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

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


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

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

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

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

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



27.jpg

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

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

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

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



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


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

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


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

우박수 과정을 거치면,



4-3.jpg


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

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



8-1.jpg

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

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



16-13.jpg

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


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

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



3-4.jpg


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

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


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




5.jpg


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

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

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



17.jpg


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

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


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

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


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

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

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


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

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



erdos.jpg

폴 에어디시 (1913-1996)


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

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


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


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

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



21개의 댓글

2018.01.04
씹노잼 글보다 이런게 제일 좋더라
0
2018.01.04
막짤아재 얼굴에서 갑수아재가 보인다
0
2018.01.05
와 디게 간단한데 증명을 못하겠네
0
2018.01.05
뮈라는겨
0
2018.01.05
0으로 합시다! 이겼다 ㅋㅋ
0
2018.01.05
@심령치료
굿 ㅋㅋ
0
2018.01.05
@심령치료
자연수가 아니라서 fail
0
2018.01.09
@팜코코
0도 자연수 취급한다던데?!
0
2018.01.05
에어디시 쫄보자식 '우리의 수학' 운운 하면서 500달러 밖에 안걸었네
0
2018.01.05
먼가 상금의 규모가 너무 작지않나 생각했다
0
2018.01.05
막짤아재 나 고딩때 수학선생이 ㅈㄴ 좋아했던 사람인데 뭐하는사람이었는지는 모름ㅋ
0
2018.01.05
참 희안한게 3n-1이 5와 17에서 안그랬으면 이야 이걸? 했을텐데
0
2018.01.05
@11년산고인물
난 오히려 3n-1 일 때 반례가 나와서 이야 이걸? 싶음 ㅋㅋ
0
2018.01.05
@테플로탁슬
말이 좀 애매했는데
저 반례가 백만단위에서 나왔으면
3n+1도 졸라 큰 숫자에서 반례가 있을거임!!
했을거 같다고
0
2018.01.05
@11년산고인물
아하 ㅋㅋ
개인적인 생각으론 둘 다 더 이상 반례가 없었으면 좋겠음
0
2018.01.06
풀었음
0
2018.01.06
수학글 넘모조아
0
2018.01.06
4딸라
0
2018.01.06
직관적으로 모든 자연수가 1이 된다는 건 알았는데 증명은 어떻게 해야함?
0
2018.01.07
이런거 볼떄마다 악마는 수학을 잘할것 같다
0
2018.01.07
@한 첸치
는 생각이 든다
0
무분별한 사용은 차단될 수 있습니다.
번호 제목 글쓴이 추천 수 날짜
526 [과학] 위드 코로나와 코로나 백신 관련 응급의학과 전문의 글 (긴글) 36 바이코딘 45 3 일 전
525 [과학] <강력의 탄생> - 추천합니다 6 미분가능하지않은... 5 5 일 전
524 [과학] 오싹오싹 우주 근황의 조금 더 자세하고 정확한 설명.physics 21 샤킬오닐 16 7 일 전
523 [과학] 코로나 백신과 혈전증에 대한 응급의학과 전문의 글 10 바이코딘 9 9 일 전
522 [과학] 앗싸식 팩트 체크 : MBTI는 그냥 말장난, 조크, 혈액형 성격... 31 커뮤질은인생의낭비 6 22 일 전
521 [과학] 한반도 형성 모델 8 白猫 4 2021.09.06
520 [과학] 인류 발전은 정체되었는가? 119 월급받으며개드립하기 22 2021.09.02
519 [과학] 자바로 프로그래밍에 입문할래요: 3.3. 자료형 설계하기 (4) 스비니 5 2021.08.21
518 [과학] 자바로 프로그래밍에 입문할래요: 3.3. 자료형 설계하기 (3) 3 스비니 3 2021.08.17
517 [과학] 자바로 프로그래밍에 입문할래요: 3.3. 자료형 설계하기 (2) 2 스비니 0 2021.08.15
516 [과학] 자바로 프로그래밍에 입문할래요: 3.3. 자료형 설계하기 (1) 9 스비니 1 2021.08.12
515 [과학] 자바로 프로그래밍에 입문할래요: 3.2. 자료형 생성하기 (3) 스비니 0 2021.08.11
514 [과학] 희귀 혈전등에 대한 아스트라제네카 코로나 19 백신 접종의 ... 18 매콤챱스 5 2021.08.10
513 [과학] 자바로 프로그래밍에 입문할래요: 3.2. 자료형 생성하기 (2) 2 스비니 2 2021.08.09
512 [과학] 엔트로피는 감소할 수 있는가? 43 Kuqi 21 2021.08.08
511 [과학] 자바로 프로그래밍에 입문할래요: 3.2. 자료형 생성하기 (1) 3 스비니 2 2021.08.05
510 [과학] 자바로 프로그래밍에 입문할래요: 3.1. 자료형 (4) 11 스비니 3 2021.08.04
509 [과학] 자바로 프로그래밍에 입문할래요: 3.1. 자료형 (3) 2 스비니 3 2021.08.02
508 [과학] SF스압) 최후의질문 / 원래는..(How It Happened) 16 기타치는고라니 17 2021.07.31
507 [과학] [양자역학 3부] 슈뢰딩거의 고양이에 대해서. 28 기타치는고라니 3 2021.07.30