Thập niên $1950$ , giới toán học thế giới lưu truyền một hiện tượng toán học kì lạ mà thú vị sau đây : Lấy một số tự nhiên $x$ , nếu là số chẵn thì chia đôi $\frac{x}{2}$ , nếu lẻ thì nhân $3$ rồi cộng $1$ tức là $3x+1$ , cứ tiếp tục như vậy bao giờ cũng sẽ thu được số $1$ .
Chẳng hạn : lấy $x=6$ làm như trên thì $\frac{6}{2}=3,3.3+1=10,\frac{10}{2}=5,5.3+1=16,\frac{16}{2}=8,\frac{8}{2}=4,\frac{4}{2}=2,\frac{2}{2}=1$
Hiện tượng toán học thú vị này gây cảm hứng cho rất nhiều người yêu thích toán học . Một nhá toán học Mĩ nói : "có một thời trong các trường đại học Mĩ , hiện tượng này trở thành hấp dẫn nhất , sinh viên khoa Toán và khoa Máy tính gần như ai cũng nghiên cứu nó . "
Có người hình dung quá trình tính toán là các giọt nước trong mây , dưới tác dụng của luồng không khí trên cao , gặp lạnh nước sẽ đóng băng , thể tích ngày càng lớn , cuối cùng biến thành mưa đá . Rồi cuối cùng biến thành $1$ . Ví vậy người ta đặt cho quá trình này cái tên trừu tượng : ý tưởng " mưa đá " hoặc số " mưa đó " .
Các nhà nghiên cứu phát hiện một cách vừa kinh ngạc vừa mừng vui dù phải thực hiện bao nhiêu phép tính thì cuối cùng vẫn về $ 4 \to 2 \to 1$ . Để kiểm tra nên bắt đầu từ $1.3+1=4,\frac{4}{2}=2,\frac{2}{2}=1$ tức là phải qua $4$ đến $2$ rồi mới đến $1$ .
Giáo viên và sinh viên ở đại học Tokyo ( Nhật Bản ) đã kiểm tra từng số của tất cả các số tự nhiên đến $2^{40}$ vẫn không tìm thấy ngoại lệ , đều kết thúc bằng $4 \to 2 \to 1$ .
Như vậy đây là sự ngẫu nhiên hay một quy luật tất yếu ? Vấn đề này vẫn chưa có câu trả lời thuyết phục .
Sư biến đổi các số tự nhiên ở trên trong thực tế là lặp lại hàm số
$$C(x)=\begin{cases} & \frac{x}{2}\text{ if } x= 2k \\ & 3x+1 \text{ if } x= 2k+1 \end{cases}$$
Vấn dề là , bắt đầu từ một số tự nhiên $x$ bất kì , trải qua phép lặp hàm số $C(x)$ một số lần hữu hạn ( sau đây gọi tắt là lặp $C$ ) , cuối cùng có một nhóm số tuần hoàn $(4,2,1)$ không ?Hoặc nói cách khác là cuối cùng có được $1$ không ?
Có người cho rằng ý tưởng này do L.Collatz đưa ra tại Hội nghị Toán học thế giới năm $1950$ nhưng có người lại nói do B.Thwaiter ( Anh ) , R.V.Andree ( Nga ) , Hans , Neolamu ( Mỹ ), ... đưa ra , chưa ai xác nhận chính xác người đưa ra đầu tiên , do vậy nhiều tài liệu gọi nó là vấn đề $3x+1$ .
Điều lôi cuốn người ta là ở chỗ trong quá trình lặp $C$ hễ gặp lũy thừa của $2$ là bài giải kết thúc , mà lũy thừa của $2$ thì nhiều vô cùng , do vậy người ta cho rằng chỉ cần quá trình lặp $C$ đủ dài nhất định sẽ gặp lũy thừa của $2$ .
Năm $1992$ , G.T.Leavens và M.Vermulen đã kiểm tra các số tự nhiên đến $5,6.10^{13}$ vẫn thấy đúng quy luật .
Vấn đề $3x+1$ thật đơn giản , ngay cả học sinh tiểu học cũng hiểu được , thế mà các nhà toán học , ngay cả các nhà toán học nổi tiếng cũng chưa giải quyết được . Học giả R.K.Guy gọi đây là " Đề toán khó thế giới " và khuyên mọi người không nên toan tính giải quyết vấn đề này . Người ta đưa ra nhiều giải thưởng , số tiền thưởng ngày càng tăng cao hơn nhưng vẫn chưa ai giải quyết được . Đến nay ta tạm chấp nhân cách nói của nhà toán học nổi tiếng Paul Erdos : " Toán học còn chưa đủ chính chắn để giải quyết vấn đề 3x+1" . Có người đề nghị lấy vấn đề $3x+1$ làm bài toán sau định lý lớn Fermat .
Cái khó của vấn đề $3x+1$ là tính phức tạp được biểu hiện ra trong quá trình lặp nhiều lần C . Để thuận tiện khi trình bày ta gọi dãy số khi thu được lặp nhiều lần $C$ đối với số $x$ là dãy số $C$ của số $x$ .
Tính phức tạp của vấn đề trước tiên là tính không quy tắc của độ lớn các chữ trong trong dãy số $C$ . Chẳng hạn , lặp $111$ lần đối với số $x=27$ cuối cùng vẫn được $1$ nhưng dao động lên xuống $42$ lần , Tuy vậy người ta vẫn tìm thấy một " cái gì đó " có tính quy luật trong sự hỗn loạn mất trật tự này .
Nhằm nghiên cứu quy luật dãy số $C$ , người ta đã làm thống kê như sau : Đặt $u,v$ là hai số lẻ thu được liên tiếp trong quá trình lặp $C$ , hiển nhiên $\frac{1}{2}(3u+1)$ vừa có thể là số lẻ vừa có thể là chẵn , hai khả năng này mỗi cái chiếm một nửa $\frac{1}{2}$ . Do đó $u$ qua một lần lặp $C$ thì được số lẻ $v$ , tức là khả năng của $\frac{3u+1}{2}=v$ là $\frac{1}{2}$ , cũng tức là khả năng của $u$ qua một lần thay đổi tăng dần bằng khoảng $\frac{3}{2}(\frac{u}{v} \approx \frac{3}{2})$ ban đầu là $\frac{1}{2}$ . Nhưng khả năng của $\frac{1}{2}(3u+1)$ là số chẵn cũng là $\frac{1}{2}$ . Lúc này thay một lần nữa sẽ được $\frac{1}{4}(3u+1)$ nó vừa là số lẻ cũng có thể là số chẵn . Từ đó $\frac{1}{4}(3u+1)=v$ , tức là khả năng của sự tăng dần bằng khoảng $\frac{3}{4}(\frac{u}{v} \approx \frac{3}{4})$ ban đầu là $\frac{1}{2}.\frac{1}{2}=\frac{1}{4}$ . Cũng vây , khả năng của $\frac{1}{4}(3u+1)$ là số chẵn cũng là $\frac{1}{4}$ . Thay một lần nữa được $\frac{1}{8}(3u+1)$ nó vừa có thể là lẻ cũng có thể là chẵn . Từ đó $\frac{1}{8}(3u+1)=v$ khả năng của sư tăng dần bằng khoảng $\frac{3}{8}$ ban đầu $\frac{1}{4}.\frac{1}{2}=\frac{1}{8}$ . Cứ tiếp tục như vậy , khả năng tăng dần bình quân từ một số lẻ $u$ để được số lẻ $v$ là :
$$r = (\frac{3}{2})^{\frac{1}{2}}.(\frac{3}{4})^{\frac{1}{4}}.(\frac{3}{8})^{\frac{1}{8}}...=\frac{3}{4}$$
Điều này chứng tỏ trong quá trình lặp $C$ , khả năng tăng dần bình quân độ lớn của hai số lẻ liên tiếp là $\frac{3}{4}$ , tức là xu thế bình quân tổng thể hạ thấp xuống , do vậy sự lặp $C$ sớm muộn sẽ dẫn đến $1$ . Đây là quy luật mang tính thống kê nhưng quan trọng trong việc chứng minh vấn đề $3x+1$ .
Còn một điều thú vị nữa là : Rất nhiều số tự nhiên liên tiêp có cùng một chiều dài đoạn lặp $C$ như nhau . Chẳng hạn $N = 8s+4,8s+5$ ( $s$ là số tự nhiên túy ý) qua ba lần lặp $C$ đều được $6s+4$ , do đó chiều dài đoạn lặp $C$ của hai số tự nhiên liên tiếp là như nhau . Chẳng hạn $17$ số tự nhiên liên tiếp từ $7083$ đến $7099$ đều có chiều dài đoạn lặp $C$ là như nhau . Năm $1976$ nhà toán học Colunborge người Mỹ lại phát hiện được $52$ số tự nhiên liên tiếp có cùng một chiều dài đoạn lặp $C$ như nhau .
Qua nghiên cứu người ta đã tìm được
+ Khi $x$ là số nguyên dương sẽ xuất hiện tuần hoàn $(4,2,1)$
+ Khi $x=0$ sẽ xuất hiện tuần hoàn $(0)$
+ Khi $x=-1,-2,-3,-4$ sẽ xuất hiện tuần hoàn $(-1,-2)$
+ Khi $x=-5$ sẽ xuất hiện tuần hoàn $(-5,-14,-7,-20,-10)$
+ Khi $x=-6,-7,...-16$ sẽ xuất hiện tuần hoàn $(-17,-50,-25,-74,-37,-110,-55,-164,-82,-41,-122,-61,-182,-91,-272,-138,-68,-34)$
+ Khi $x=-17$ sẽ xuất hiện tuần hoàn ( blo bla mọi người tính nhé )
+ Khi $x < -17$ sẽ không xuất hiện tuần hoàn .
Năm $1978$ có người phỏng đoán : Nếu lặp $C$ cho tất cả số nguyên thì chỉ có thể nhận được $5$ loại tuần hoàn nói trên. Người ta kiểm tra cho các số nguyên âm đến $-10^{8}$ thì phỏng đoán này vẫn đúng . Tuy vậy vẫn chưa có một chứng minh cho trường hợp tổng quát .
Người ta lại đưa ra hàm số đơn giản hơn :
$$C(x)=\frac{3x+1}{2^{e(x)}}$$
Trong đó $e(x)$ là các lũy thừa của ước nguyên tố $2$ trong phân tích thành các ước nguyên tố của $3x+1$ .
Trường hợp tổng quát đặt $a,b$ là các số nguyên dương lẻ $a>1$ thì
$$C(x)=\frac{ax+b}{2^{e(x)}}$$
Trong đó $x$ lấy số lẻ dương , nếu lấy $a=3,b=1$ thì về vấn đề $3x+1$ , điều đặc biệt là nếu $(a,b)$ mà khác $(3,1)$ thì lặp $C$ sẽ không xuất hiện số $1$ ( thần kì ! )
Nếu lấy $r= bt$ ( $t$ là số lẻ dương bất kì )
$$C(r).2^{e(r)}=ar+b=(at+1)b$$
Nếu $b>1$ thì tất cả $C(r)$ đều chia hết cho $b$ và như vậy không bao giờ xuất hiên $1$ .
Nếu $b=1$ thi khi $a$ là số chẵn , $C(x)=ax+1$ luôn lẻ và dãy $C$ tăng dần , lặp $C$ không thể có $1$ được . Còn khi $a$ là số lẻ , sẽ tồn tại một số lẻ dương $r$ nào đó mà $C(r)=\frac{ar+1}{2^{e(r)}}$ không xuất hiện $1$
Năm $1978$ , R.E.Crandall đã chứng minh $a=5,181,1093$ thì phỏng đoán nếu trên đúng .
+ Khi $a=5$ thì $C(r)=\frac{5r+1}{2^{e(r)}}$ , lấy $r=13$ thì dãy xuất hiện tuần hoàn $(33,83,13)$ không xuất hiện $1$
+ Khi $a=181$ thì $C(r)=\frac{181r+1}{2^{e(r)}}$ , lấy $r=27$ thì xuất hiện tuần hoàn $(611,27)$ không xuát hiện $1$
+ Khi $a=1093$ thì $C(s) = \frac{1093s+1}{2^{e(s)}}$ , lấy $s= \frac{2^{364p}-1}{1093}$ trong đó $p$ là số tự nhiên bất kì thì $1093s+1=2^{364p}$ vì vậy $e(s)=364p,C(s)=1$
Như vậy đây là nhóm số duy nhất xuất hiện $1$ , còn đối với bất cứ số lẻ dương $s$ khác , lặp $C$ có thể kéo dài vô hạn mà không đạt được $1$ .
Có người đã lấy $a=7$ và thực hiện việc lặp $r=3$ vượt qua số $10^{2000}$ mà vẫn chưa thấy dấu hiệu lặp lại ( tuần hoàn) nào . Xem ra phỏng đoán $7x+1$ rất có thể là chính xác nhưng chưa ai chứng minh được bằng lý thuyết ,
Thập niên $1930$ , khi L.Collatz đang học đại học , ông đã say mê nghiên cứu vấn đề $3x+1$ . Trong cuốn số ghi chép để ngày $1-7-1932$ ông đã nghiên cứu hàm số $F(x)=\frac{2x}{3},\frac{4x-1}{3},\frac{4x+1}{3}$ lần lượt tương ứng với $x$ chia $3$ dư $0,1,2$
Các kết quả tính được cho thấy rằng với $x$ bằng $2,3$ thì sinh ra tuần hoàn $(2,3)$ , với $x=4,5,6,7,9$ thì sinh ra tuần hoàn $(5,7,9,6,4)$ còn $x=8$ thì ông chưa thấy xuất hiên tuần hoàn , mặc dù đã thực hiện khá nhiều phép tính . Vấn đề này được coi là " vấn đề Collatz nguyên thủy " .
Vấn đề ngược lại với vấn đề Collatz nguyên thủy là hàm $G(x)$ xác định
$$G(x) = \frac{3x}{2}$$ khi $x$ chẵn
$$G(x)=\frac{3x-1}{4}$$ khi $x$ chia $4$ dư $3$
$$G(x)=\frac{3x+1}{4}$$ khi $x$ chia $4$ dư $1$ ,
Đang làm nhiều người quan tâm . Tính toán như hàm $F(x)$ ta được bốn nhóm số tuần hoàn $(1),(2,3),(4,6,9,7,5),(44,66,99,74,111,83,62,93,70,105,79,59)$ tuy vậy nhóm tuần hoàn còn nữa hay không thì vẫn chưa ai trả lời được .
Trích từ : Tuyển tập những vấn chưa toán học chưa có lời giải - Nguyễn Bá Đô
Bài viết đã được chỉnh sửa nội dung bởi bangbang1412: 26-01-2017 - 23:17
