Giới thiệu chung
Đây là bài toán “nguy hiểm nhất” trong toán học, một bài toán mà các nhà toán học trẻ được cảnh báo không nên lãng phí thời gian vào đó. Nó là một giả thuyết đơn giản mà ngay cả những nhà toán học giỏi nhất thế giới cũng chưa thể giải được. Paul Erdős, một nhà toán học nổi tiếng, đã từng nói: “Toán học chưa chín muồi đủ cho những câu hỏi như thế này.”
Quy trình hoạt động của bài toán
Quy trình như sau: hãy chọn bất kỳ số nào—ví dụ, số bảy. Nếu số đó là số lẻ, nhân nó với 3 và cộng thêm 1. Như vậy, 3 × 7 bằng 21, và cộng 1 được 22. Nếu số đó là số chẵn, chia nó cho 2. Do đó, 22 chia cho 2 bằng 11. Ta tiếp tục áp dụng hai quy tắc này:
- Số 11 là số lẻ, nên nhân 3 và cộng 1 để được 34.
- Số 34 là số chẵn, nên chia cho 2 được 17.
- Số 17 là số lẻ, nhân 3 và cộng 1 cho ra 52.
- Số 52 là số chẵn, chia cho 2 được 26.
- Số 26 là số chẵn, chia cho 2 được 13.
- Số 13 là số lẻ, nhân 3 và cộng 1 cho ra 40.
- Số 40 là số chẵn, chia cho 2 cho ra 20; 20 chia cho 2 được 10; 10 chia cho 2 được 5.
- Số 5 là số lẻ, nên nhân 3 và cộng 1 cho ra 16.
- Số 16 là số chẵn, chia cho 2 cho ra 8; 8 chia cho 2 được 4; 4 chia cho 2 được 2; và 2 chia cho 2 được 1.
Khi đã đạt đến số 1, quá trình tiếp tục: số 1 là số lẻ, nên nhân 3 và cộng 1 cho ra 4, sau đó 4 chuyển thành 2 và quay trở lại 1, tạo thành một vòng lặp. Giả thuyết khẳng định rằng mọi số nguyên dương, nếu áp dụng các quy tắc này lặp đi lặp lại, cuối cùng sẽ rơi vào vòng lặp 4–2–1.
Các tên gọi khác của bài toán
Giả thuyết này thường được gọi là Giả thuyết Collatz, được đặt theo tên nhà toán học người Đức Lothar Collatz, người có thể đã đưa ra giả thuyết này vào những năm 1930. Tuy nhiên, bài toán có nhiều câu chuyện khởi nguồn và nhiều tên gọi khác nhau. Nó còn được gọi là Giả thuyết Ulam, Bài Toán Kakutani, Giả Thuyết “We”, Thuật Toán của Hass, Bài Toán Syracuse và đơn giản là 3n + 1.
Sự “tai tiếng” của bài toán
Tại sao 3×+1 lại nổi tiếng (hay còn “tai tiếng”) trong giới chuyên gia toán học? Có lẽ nó không nổi tiếng theo nghĩa tích cực, mà là nổi tiếng vì sự “khó chịu” khi ai đó công khai cho biết mình đang nghiên cứu bài toán này. Các số được tạo ra theo quy tắc 3×+1 được gọi là “số mưa đá” vì chúng tăng giảm như những hạt mưa đá trong mây dông, dù cuối cùng tất cả đều rơi xuống 1 — hoặc ít nhất là chúng ta tin như vậy. Ta có thể hình dung các số này như biểu diễn độ cao (tính theo mét) so với mặt đất. Ví dụ, số 26 bắt đầu từ 26 mét và sau khi áp dụng 3×+1, nó có thể tăng lên tới 40 mét, mất 10 bước để đạt đến 1 (được gọi là “thời gian dừng hoàn toàn”). Ngược lại, số 27 “nhảy lò cò” đến mức có thể leo lên tới 9.232 mét — cao hơn cả đỉnh Everest — và mất 111 bước để giảm xuống 1 và vào vòng lặp 4–2–1.
Những nỗ lực nghiên cứu và lời khuyên
Con đường mà các số theo đuổi rất khác nhau, thậm chí với các số chẵn liên tiếp nhau cũng có thể khác nhau rõ rệt. Vậy làm thế nào để bắt đầu tiến bộ với bài toán này? Các nhà toán học đã vật lộn với nó suốt nhiều thập kỷ, và có người đùa rằng nó được phát minh ra bởi người Nga để làm chậm khoa học phương Tây—vì dường như ai cũng chỉ “ngồi ngắm” mà chẳng có tiến triển gì với một bài toán mà ngay cả trẻ em ở trường cũng có thể hiểu được. Jeffrey Lagarias, được coi là chuyên gia hàng đầu về 3×+1, đã từng khuyên tôi khi tôi còn là sinh viên năm cuối: “Đừng làm bài toán này nếu bạn muốn có sự nghiệp. Hãy làm những bài toán ‘chân’ để khẳng định bản thân.” Tuy nhiên, Alex Kovach đã không nghe lời khuyên đó và cùng với Yakov Sinai nghiên cứu các đường đi của “số mưa đá.”
Phân tích tính chất “ngẫu nhiên” của chuỗi số
Liệu có thể tìm ra được những mẫu hình nào trong các đường đi đó không? Rõ ràng, tất cả đều cuối cùng về 1, nhưng hành trình đi đến đó thì sao? Mẫu hình dường như rất ngẫu nhiên. Với một số lớn được chọn ngẫu nhiên, chuỗi số ban đầu tăng lên rồi đột nhiên giảm xuống mức mà chi tiết không thể nhận ra được ở quy mô đó. Tuy nhiên, khi lấy logarit của các số, ta thấy được một đồ thị “lượn sóng” có xu hướng giảm—giống như thị trường chứng khoán trong một ngày tồi tệ. Cả hai hiện tượng đều là ví dụ của chuyển động Brownian hình học, nghĩa là khi loại bỏ xu hướng tuyến tính, các dao động trở nên ngẫu nhiên, như việc tung đồng xu ở mỗi bước (mặt “sấp” khiến chuỗi tăng, mặt “ngửa” khiến nó giảm). Qua thời gian dài, trong khi thị trường chứng khoán có xu hướng tăng, chuỗi 3×+1 lại có xu hướng giảm theo thống kê.
Phân bố chữ số đầu và định luật Benford
Một cách khác để phân tích 3×+1 là xem xét chữ số đầu của mỗi số trong chuỗi. Bắt đầu với một số “hạt giống”, ta đếm xem có bao nhiêu số trong chuỗi bắt đầu bằng 1, 2, 3, …, và sau đó xây dựng một biểu đồ tần số (histogram). Khi quá trình này được lặp lại với ngày càng nhiều chuỗi số, biểu đồ dần dần ổn định theo một mẫu hình nhất định. Ví dụ, với một tỷ chuỗi số đầu tiên, khoảng 30% các số bắt đầu bằng số 1, xấp xỉ 17% bắt đầu bằng số 2, khoảng 12% bắt đầu bằng số 3, và tần số giảm dần với các chữ số cao hơn, với dưới 5% số bắt đầu bằng số 9. Mẫu hình này không chỉ xuất hiện trong 3×+1; nó có mặt ở nhiều dữ liệu khác như dân số các quốc gia, giá trị các công ty, hằng số vật lý, và cả dãy số Fibonacci. Đây được gọi là định luật Benford, thậm chí còn được dùng để phát hiện gian lận: nếu các con số trên tờ khai thuế của bạn tuân theo định luật Benford, khả năng cao bạn đang trung thực. Tuy nhiên, mặc dù định luật này áp dụng cho chuỗi 3×+1, nó không khẳng định rằng mọi chuỗi số cuối cùng đều rơi vào vòng lặp 4–2–1.
Tại sao dường như mọi dãy số đều “chùng xuống”?
Ban đầu, thật lạ khi nghĩ rằng tất cả các số đều sẽ về 1. Rõ ràng, khi một số lẻ được nhân với 3 và cộng 1, nó có vẻ như sẽ tăng, trong khi các số chẵn lại bị chia đôi. Điểm mấu chốt là mỗi khi một số lẻ được xử lý (nhân 3 và cộng 1), nó ngay lập tức trở thành số chẵn và sau đó bị chia cho 2. Như vậy, các số lẻ không thực sự được “nhân ba” mà về hiệu quả chỉ tăng lên khoảng 3⁄2. Với các số lớn, phần “+1” trở nên không đáng kể, và 3⁄2 là mức tăng tối đa trong một bước. Tuy nhiên, nếu xét từ số lẻ này đến số lẻ kế tiếp trong chuỗi, ta nhận thấy rằng sau khi nhân và cộng, số đó trở thành số chẵn, và 50% trường hợp chỉ cần chia 2 là ngay lập tức ra số lẻ. Ở một phần tư trường hợp, có thể chia cho 4 trước khi xuất hiện số lẻ kế tiếp; ở một phần tám trường hợp, chia cho 8, và cứ thế. Khi lấy trung bình nhân theo cấp số nhân, hệ số trung bình từ số lẻ này sang số lẻ kế là 3⁄4 – nhỏ hơn 1 – nên về mặt thống kê, chuỗi 3×+1 có xu hướng giảm thay vì tăng.
Biểu diễn dạng đồ thị có hướng
Ví dụ, hãy xem số 341. Nhân 3 và cộng 1 cho ra 1.024, sau đó số này được chia cho 2 liên tiếp—mười lần cho đến khi đạt 1. Một cách để hình dung những đường đi này là vẽ một đồ thị có hướng, trong đó mỗi số nối với số kế tiếp trong chuỗi. Nếu giả thuyết đúng, mọi số đều được kết nối trong đồ thị này, với mọi nhánh cuối cùng đều chảy về “dòng chính” của vòng lặp 4–2–1. Một số nhà toán học còn thay đổi cách biểu diễn này bằng cách xoay đồ thị: xoay ngược chiều kim đồng hồ đối với số lẻ và xoay cùng chiều kim đồng hồ đối với số chẵn. Kết quả là một cấu trúc hữu cơ giống như rạn san hô hay rong biển, và bằng cách điều chỉnh góc xoay, ta có thể tạo ra những hình dạng đẹp mắt và tinh vi.
Khả năng bác bỏ giả thuyết
Có hai khả năng khiến giả thuyết sai. Thứ nhất, có thể tồn tại một số “hạt giống” nào đó khởi đầu một chuỗi số tăng vô hạn, không chịu lực “hấp dẫn” số học kéo chúng xuống. Thứ hai, có thể tồn tại một vòng lặp kín của các số, tách biệt khỏi đồ thị chính, mà không nối với vòng lặp 4–2–1. Cho đến nay, dù đã kiểm tra cật lực mọi số cho tới 2⁶⁸ (khoảng 2,95 × 10²⁰), không có số nào bác bỏ được giả thuyết. Thậm chí, các tính toán cho thấy nếu có một vòng lặp khác ngoài 4–2–1, nó cũng phải chứa ít nhất 186 tỷ số, khiến khả năng tồn tại của nó là rất thấp (dù chưa được chứng minh tuyệt đối).
Nỗ lực chứng minh và những kết quả từng bước
Nhiều hướng nghiên cứu đã được đề xuất để chứng minh giả thuyết. Một ý tưởng là vẽ đồ thị phân tán với số “hạt giống” trên trục hoành và một số trong chuỗi trên trục tung. Nếu ta có thể chứng minh rằng trong mọi chuỗi 3×+1 luôn có một số nhỏ hơn số hạt giống ban đầu, thì theo đó, mọi chuỗi số cuối cùng cũng phải giảm xuống 1 – vì quá trình này sẽ lặp lại với các số ngày càng nhỏ hơn. Mặc dù điều này chưa được chứng minh hoàn toàn, nhưng đã có những bước tiến đáng kể. Năm 1976, Rho Teras đã chứng minh rằng hầu hết các chuỗi Collatz đều cuối cùng giảm xuống dưới giá trị ban đầu. Năm 1979, giới hạn này được giảm xuống sao cho hầu hết các số giảm xuống dưới x^(0.869), và năm 1994, con số này lại được hạ thấp hơn đến dưới x^(0.7925). Ở đây, “hầu hết các số” có ý nghĩa kỹ thuật: khi xét các số tiến về vô hạn, tỷ lệ các số cuối cùng giảm xuống dưới giá trị ban đầu tiến về 1. Sau đó, vào năm 2019, nhà toán học lừng danh Terence Tao đã chứng minh rằng 3×+1 còn tuân theo những tiêu chí nghiêm ngặt hơn—hầu hết các số cuối cùng đều giảm xuống dưới bất kỳ hàm số f(x) nào (với điều kiện f(x) tiến về vô hạn khi x tiến về vô hạn), dù hàm đó tăng chậm đến mức nào (ví dụ như log x, log log x, hoặc log log log x). Trong một buổi nói chuyện công khai năm 2020, Tao cho biết kết quả này là “gần như tốt nhất” mà ta có thể đạt được để chứng minh giả thuyết Collatz mà không cần chứng minh trực tiếp.
Tại sao vẫn chưa có chứng minh hoàn chỉnh?
Dù có những kết quả ấn tượng, giả thuyết vẫn chưa được chứng minh. Có thể ta tự hỏi tại sao không thể chứng minh được—liệu giả thuyết có thật sự đúng không? Có lẽ, lý do mà mọi người cố gắng chứng minh là bởi vì hầu như không ai tìm kiếm các phản ví dụ. Tôi nhớ rằng hai năm trước, tôi đã vật lộn suốt ba năm để chứng minh một mệnh đề nào đó, đến khi cuối cùng phát hiện ra một phản ví dụ, từ đó nhận ra cách diễn đạt đúng, và chỉ sau một tháng tôi mới chứng minh được mệnh đề đúng. Có lẽ, ta nên dành nhiều năng lượng hơn cho việc tìm kiếm phản ví dụ thay vì chỉ cố gắng chứng minh. Hãy nhớ số 27, con số “leo” lên tới 9.232; một đồ thị của các số hạt giống từ 1 đến 10.000 cho thấy rằng dù nhiều chuỗi đạt đỉnh ở mức vừa phải, nhưng có những chuỗi (như chuỗi bắt đầu từ 9.663) lại vọt lên tới 27 triệu. Tuy nhiên, chưa có ai chứng minh được rằng có thể tồn tại một số nào đó mà cuối cùng tăng về vô hạn, hay một vòng lặp kín khác (ngoài 4–2–1) có thể tồn tại.
Những điều kỳ lạ khi áp dụng với số âm
Điều thú vị là, khi áp dụng quy tắc 3×+1 cho các số âm, không chỉ có một hoặc hai mà có đến ba vòng lặp độc lập, với các giá trị bắt đầu như –7 và –5. Tại sao lại có các vòng lặp rời rạc ở phía số âm mà không có ở phía số dương? Một trong những bằng chứng thuyết phục nhất ủng hộ giả thuyết là bằng chứng của Tao rằng hầu hết các số có trong chuỗi của chúng một số hạng nào đó đạt đến giá trị “arbitrarily small” (cực nhỏ). Tuy nhiên, chứng minh rằng hầu hết các số thỏa mãn tiêu chí này không tương đương với việc chứng minh rằng tất cả các số đều như vậy. Ví dụ, giữa 1 và 100 có 10 số chính phương (10%), nhưng giữa 1 và 1.000 chỉ có 31 số (3,1%); khi số tăng, tỷ lệ số chính phương càng giảm dần, mặc dù ta biết chính xác vị trí của chúng.
Vấn đề “không gian” của các số chưa được kiểm tra
Cho đến nay, mọi số từ 1 đến 2⁶⁸ đều được kiểm tra và đều tuân theo giả thuyết Collatz. Tuy nhiên, trên tổng thể các số tự nhiên, 2⁶⁸ chỉ là một con số rất nhỏ. Ví dụ, Giả thuyết Paa, được George Paa đưa ra năm 1919, khẳng định rằng đa số các số tự nhiên đến một số nhất định có số lượng ước số nguyên tố lẻ là số lẻ. Giả thuyết này sau đó đã bị bác bỏ vào năm 1958 bởi C. Brian Haselgrove, người đưa ra một phản ví dụ có giá trị xấp xỉ 1.1845 × 10³⁶¹—lớn hơn hơn 10.000 lần so với tất cả các số đã được kiểm tra trong 3×+1. Một cách để hiểu 3×+1 là coi nó như một chương trình đơn giản chạy trên máy Turing, trong đó số hạt giống là đầu vào. Việc máy tính “xử lý” mọi đầu vào trên một băng kéo dài 2⁶⁸ không có nghĩa là nó sẽ luôn biến đầu vào đó thành số 1. Thực ra, thật dễ để thiết kế một số có hành vi tùy ý trong một số bước hữu hạn, nhưng sau đoạn hữu hạn đó, ta không còn kiểm soát được gì. Mọi số được kiểm tra cho đến nay cuối cùng đều “rơi” xuống 1. Nếu tồn tại một phản ví dụ, thì gần như không thể nào đoán được, vì không gian các khả năng quá rộng để có thể tìm kiếm bằng phương pháp dò mần.
Suy tư về khả năng chứng minh và tính “khó giải” của bài toán
Tôi đã theo đuổi Team 3×+1 trong suốt 20 năm, rồi bắt đầu tự hỏi: Chúng ta thực sự biết được gì? Rất khó để chứng minh một mệnh đề nếu mệnh đề đó sai. Có lẽ mọi người vật lộn với bài toán này bởi vì nó không thực sự đúng—và việc kiểm tra đến số 2⁶⁰ chỉ là một bằng chứng hạn chế. Ngay cả khi các kết quả thống kê là đúng, chúng cũng không loại trừ khả năng tồn tại một đường đi “dịch chuyển” về phía tăng vô hạn trong chuỗi 3×+1. Một khả năng khác là bài toán này có thể là bài toán “không quyết định được”. Vào năm 1987, John Conway đã tạo ra một phiên bản tổng quát của 3×+1 có tên là Fractran—một “máy toán học” mà ông chứng minh được là Turing complete. Điều này có nghĩa là nó có thể thực hiện bất kỳ phép tính nào mà máy tính hiện đại có thể làm, nhưng đồng thời cũng ngụ ý rằng nó bị chi phối bởi vấn đề “dừng” (halting problem) – tức là có khả năng máy sẽ không bao giờ dừng chạy và do đó không cho ra kết quả. Mặc dù điều này không chứng minh rằng 3×+1 cũng bị ảnh hưởng bởi vấn đề dừng, nhưng nó gợi ý rằng có thể ta sẽ không bao giờ chứng minh được giả thuyết Collatz là đúng hay sai một cách dứt khoát.
Bài học về sự “phức tạp” của toán học
Trong trường học, chúng ta được dạy rằng mình biết rất nhiều điều, nhưng trên thực tế, nhiều điều đó chỉ là những giả định chưa được chứng minh. Hãy xem xét bài toán có vẻ “vặt vãnh” này: liệu chúng ta có thực sự giải được nó không? Bài toán 3×+1 cho thấy rằng toán học thực sự vô cùng khó khăn. Thậm chí, tất cả những điều ta có thể giải được dường như đều là những điều kỳ diệu, và ta chẳng có lý do gì để đòi hỏi phải có lời giải cho mọi bí ẩn trong toán học. Suốt cuộc đời tôi, tôi luôn nghĩ rằng các con số là những thực thể vô cùng đều đặn, đầy mẫu hình, đối xứng và lặp lại, nhưng giờ tôi mới nhận ra rằng các con số thực sự kỳ quặc đến mức nào. Từ một phép toán đơn giản, lại có thể bộc lộ ra một cấu trúc hữu cơ tinh vi như rạn san hô. Liệu tất cả các con số có kết nối với cấu trúc này, hay lại có một “sợi chỉ” mảnh mai, riêng biệt trôi ra vô tận? Có lẽ đó chính là lý do tại sao Paul Erdős đã nói “toán học chưa chín muồi đủ cho những câu hỏi như thế này.”
Lời kết và thông điệp truyền cảm hứng
Điều tôi yêu thích ở bài toán 3×+1 là đây là một bài toán hầu như bất cứ ai cũng có thể hiểu và tự mình thử nghiệm. Việc tự mình tìm hiểu và giải quyết vấn đề chính là cách học hiệu quả nhất.
