수학동아 - 폴리매스

자유게시판

수학을 주제로 떠들어 보세요!

[수학 정보] 콜라츠 추측 증명?

pure math 2022.03.24 02:38 조회 1398

페이스북 트위터 카카오톡 카카오스토리 네이버블로그 네이버밴드

우선, 콜라츠 추측을 풀기 위해서는 간단하게 생각 할 수 있는데요, 모든 짝수가 홀수가 되니 우리는 홀수에 대해서만 보면 되고, 그것이 2ⁿ꼴이 되는 것만 확인하면 됩니다.

처음 수를 x(홀수)라 하면, 3x + 1이 되고, 3x + 1 $\equiv$ 1 (mod 3) 이 됩니다. 근데, 이 친구는 짝수입니다. 그래서 이 친구를 두 가지로 분류할 수 있는데,

1. 2²ⁿ*q (q $\equiv$ 1 (mod 3))

2. 2²ⁿ⁺¹*p (p $\equiv$ 2 (mod 3))

이 두가지 경우가 됩니다. 근데, 이 친구는 다시 각각 q, p로 가게 됩니다. 물론 홀수인 거죠. 이 과정이 계속 반복됩니다. 그래서, 이제 우리는 콜라츠 함수가

계속 감소하는지만 보면 됩니다.

1.경우에는 x > (3x + 1)/2²ⁿ 을 증명하면 됩니다. (3x+1)/2²ⁿ < 4x/4ⁿ < x / 4^n-1 <= x, 즉 x > (3x + 1)/2²ⁿ 이기에 증명이 됩니다.

2.경우에는 x > (3x+1)/2²ⁿ⁺¹ 을 증명하면 됩니다. 근데 이건 위의 방법과 같습니다. 그래서, 감소하게 됩니다. (+ 부등식을 만족 안하는 x(작은수)는 시행으로 증명)

고로, 이 콜라츠 함수는 "무조건" 감소합니다. 근데, 우리는 이 시행을 계속 할 수 있잖아요? (다시 경우로 돌아오기 때문) 고로, 무한히 감소하는 자연수에 관한 함수(수열)은 없으므로, 1까지 감소해야 합니다. 즉, 콜라츠 추측 증명!

이전글 수학난제같이 풉시다!

다음글 난제 모음집

추천 4 목록보기

댓글 작성하기

RedoC Lv.5 2022.03.24 02:53

@pure_math 홀수 x에 대해서 3x+1을 두 가지 경우 만으로 분류할 수 있다는 건 어떻게 도출되었나요?

댓글 작성하기 좋아요0 댓글수1
- pure math Lv.7 2022.03.24 02:57
  
  1.경우에서는 모듈러 3에 대해서 나머지가 1인 얘고
  
  2.은 나머지가 2인 것입니다 합동인 거죠!
  
  3에 대하여 두 경우가 있으니 그랬습니다!
  
  좋아요0
Horizontal Lv.5 2022.03.24 03:02

2번 경우가 잘못된 듯 합니다

n이 0일경우 x > (3x+1)/2 가 되고 이는 자명하게 틀림

댓글 작성하기 좋아요1 댓글수0
RedoC Lv.5 2022.03.24 03:06

혹시 그럼 3x-1 수열에 대해서 위 방식을 그대로 이용해서 1에 도달함을 증명할 수 있을까요?

댓글 작성하기 좋아요0 댓글수6
- pure math Lv.7 2022.03.24 03:12
  
  A PHP Error was encountered
  
  Severity: Warning
  
  Message: mkdir(): Permission denied
  
  Filename: libraries/Common.php
  
  Line Number: 202
  
  Backtrace:
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
  Line: 202
  Function: mkdir
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
  Line: 236
  Function: getLatexImg
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view_comment_list.php
  Line: 200
  Function: parseLatexImg
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view.php
  Line: 343
  Function: view
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/controllers/ver3/Contents.php
  Line: 558
  Function: view
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/index.php
  Line: 315
  Function: require_once
  
  A PHP Error was encountered
  
  Severity: Warning
  
  Message: file_put_contents(/DATA/upload/polymath/latex/7541d65e0e0f1643ceaae082a34750f6.gif): failed to open stream: No such file or directory
  
  Filename: libraries/Common.php
  
  Line Number: 213
  
  Backtrace:
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
  Line: 213
  Function: file_put_contents
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
  Line: 236
  Function: getLatexImg
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view_comment_list.php
  Line: 200
  Function: parseLatexImg
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view.php
  Line: 343
  Function: view
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/controllers/ver3/Contents.php
  Line: 558
  Function: view
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/index.php
  Line: 315
  Function: require_once
  
  A PHP Error was encountered
  
  Severity: Warning
  
  Message: mkdir(): Permission denied
  
  Filename: libraries/Common.php
  
  Line Number: 202
  
  Backtrace:
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
  Line: 202
  Function: mkdir
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
  Line: 236
  Function: getLatexImg
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view_comment_list.php
  Line: 200
  Function: parseLatexImg
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view.php
  Line: 343
  Function: view
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/controllers/ver3/Contents.php
  Line: 558
  Function: view
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/index.php
  Line: 315
  Function: require_once
  
  A PHP Error was encountered
  
  Severity: Warning
  
  Message: file_put_contents(/DATA/upload/polymath/latex/7541d65e0e0f1643ceaae082a34750f6.gif): failed to open stream: No such file or directory
  
  Filename: libraries/Common.php
  
  Line Number: 213
  
  Backtrace:
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
  Line: 213
  Function: file_put_contents
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
  Line: 236
  Function: getLatexImg
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view_comment_list.php
  Line: 200
  Function: parseLatexImg
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view.php
  Line: 343
  Function: view
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/controllers/ver3/Contents.php
  Line: 558
  Function: view
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/index.php
  Line: 315
  Function: require_once
  
  A PHP Error was encountered
  
  Severity: Warning
  
  Message: mkdir(): Permission denied
  
  Filename: libraries/Common.php
  
  Line Number: 202
  
  Backtrace:
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
  Line: 202
  Function: mkdir
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
  Line: 236
  Function: getLatexImg
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view_comment_list.php
  Line: 200
  Function: parseLatexImg
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view.php
  Line: 343
  Function: view
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/controllers/ver3/Contents.php
  Line: 558
  Function: view
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/index.php
  Line: 315
  Function: require_once
  
  A PHP Error was encountered
  
  Severity: Warning
  
  Message: file_put_contents(/DATA/upload/polymath/latex/7541d65e0e0f1643ceaae082a34750f6.gif): failed to open stream: No such file or directory
  
  Filename: libraries/Common.php
  
  Line Number: 213
  
  Backtrace:
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
  Line: 213
  Function: file_put_contents
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
  Line: 236
  Function: getLatexImg
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view_comment_list.php
  Line: 200
  Function: parseLatexImg
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view.php
  Line: 343
  Function: view
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/controllers/ver3/Contents.php
  Line: 558
  Function: view
  
  File: /volume1/web/PhpstormProjects/www_polymath_co_kr/index.php
  Line: 315
  Function: require_once
  
  어...위의 저의 친구가 제시한 문제 땜에 일단은 이거부터...
  
  3x+1=2p일때(p=홀수)(p $\equiv$ 2)인 것인데..3x+1 $\equiv$ 2(mod 4)이고, 3x $\equiv$ 1 (mod 4)이며, x = 3 + 4q 꼴이 될 것입니다.여기에만 증명을..
  
  좋아요0
- pure math Lv.7 2022.03.24 03:13
  
  추가로, 한번 더 콜라츠 함수를 적용하면 p = 6q + 5가 나오네요.
  
  좋아요0
- RedoC Lv.5 2022.03.24 03:16
  
  참고로 3x-1은 무한히 감소합니다만 1에 도달하지는 않습니다. 예를 들어, x에 5를 대입하면
  
  5 → 14 → 7 → 20 → 10 → 5
  
  이라는 루프가 생성되어 1에 도달하지 않습니다. 즉 무한히 감소한다는 사실은 1에 도달할 수 있다는 것과는 다릅니다.
  
  좋아요0
- pure math Lv.7 2022.03.24 03:18
  
  오호
  
  좋아요0
- pure math Lv.7 2022.03.24 03:24
  
  @RedoC
  
  추가로, 위의 제 친구가 쓴 오류에서, 그 오류가 무한히 존재하는 수는 없습니다.
  
  f(x) = 3x + 2라 한다면, fⁿ(x) = 모두 홀수 가 되게 만드는 x는 없기 때문입니다. (n은 임의의 자연수)
  
  좋아요0
- pure math Lv.7 2022.03.24 03:53
  
  @RedoC
  
  홀수 x에 대하여, 그 x가 4q + 3꼴일 때에, (단 q = 홀수)(오류의 주 원인) 증가되는 시행의 횟수 = q = 2q'+1, q' = 2q''+1........이라 하였을 때, q'(n번)가 짝수가 되기까지 필요한 시행의 개수 = n+1(q'(n번)할때의 n)입니다!
  
  좋아요0
수학동아 Lv.8 2022.03.24 17:49

2번 경우에는 n=0일 수 있기 때문에, 1번 경우와 똑같이 할 수 없습니다.

같은 방법을 쓰면 (3x+1)/2²ⁿ⁺¹ < 8x/4ⁿ*2 < x / 4^n-1 <= x, 즉 x > (3x + 1)/2²ⁿ⁺¹이 되는데, 마지막 부등호가 n이 0이 되면 성립하지 않습니다.

그래서 이렇게 증명을 하려면 4n-1꼴의 수에 콜라츠 함수를 계속 사용하면 4n+1꼴이 된다는 걸 증명해야 합니다.

댓글 작성하기 좋아요0 댓글수1
- pure math Lv.7 2022.03.25 00:17
  
  아 그건 증명했어요 근데 뒤에가 문제네요;
  
  좋아요0