Bài Toán 3n + 1 (Collatz)

Nhập một số nguyên dương để xem chuỗi biến đổi về 1

Về bài toán Collatz

Bài toán Collatz, hay còn gọi là phỏng đoán $3n + 1$, là một trong những bài toán chưa có lời giải nổi tiếng nhất trong toán học. Quy luật của nó rất đơn giản. Bắt đầu với một số nguyên dương $n$ bất kỳ, ta áp dụng hàm:

$$f(n) = \begin{cases} n/2 & \text{nếu } n \equiv 0 \pmod 2 \\ 3n + 1 & \text{nếu } n \equiv 1 \pmod 2 \end{cases}$$

Nếu $n$ là số chẵn, chia nó cho 2: $n \rightarrow n/2$
Nếu $n$ là số lẻ, nhân nó với 3 và cộng thêm 1: $n \rightarrow 3n + 1$

Phỏng đoán cho rằng, dù bạn bắt đầu với bất kỳ số nguyên dương nào, quá trình này cuối cùng cũng sẽ luôn đạt tới chu trình lặp $4 \rightarrow 2 \rightarrow 1$ và quay về số $1$.

Có công thức tổng quát theo $n$ không?

Gọi quỹ đạo Collatz là $a_0, a_1, \dots, a_k$ với $a_0 = n$ và $a_k = 1$ (sau $k$ bước nhảy). Câu trả lời ngắn gọn: không — không tồn tại công thức đóng (closed-form) tổng quát theo $n$ cho giá trị $a_k$ hay số bước $k$. Lý do nằm ở chính bản chất chưa giải được của bài toán Collatz.

Vì sao không có công thức đóng

Muốn có công thức theo $n$ thì trước hết phải biết số bước $k(n)$ (thời gian dừng toàn phần) và từng giá trị $a_i$ trên quỹ đạo. Nhưng hiện không ai biết công thức đóng cho $k(n)$, cũng không có biểu thức dự đoán được dãy $a_i$. Đây đúng là trái tim của phỏng đoán Collatz: nếu tồn tại công thức như vậy, bài toán đã được giải.

Công thức "có điều kiện" theo dãy chẵn/lẻ

Nếu ta cho trước dãy chẵn/lẻ $\epsilon_i \in \{0,1\}$ (parity vector, với $\epsilon_i = 1$ nếu $a_i$ lẻ, $\epsilon_i = 0$ nếu $a_i$ chẵn) thì mỗi bước của bản đồ rút gọn $T(n) = n/2$ (chẵn) hoặc $(3n+1)/2$ (lẻ) đều viết được chung dưới dạng một phép biến đổi affine:

$$a_{i+1} = \frac{3^{\epsilon_i}\, a_i + \epsilon_i}{2}$$

Diễn giải từng bước. Lồng liên tiếp công thức trên vào chính nó, ta thấy hệ số của $n$ và của từng $\epsilon_j$ hiện ra theo một quy luật rõ ràng:

$$a_1 = \frac{3^{\epsilon_0}}{2}\,n + \frac{\epsilon_0}{2}$$ $$a_2 = \frac{3^{\epsilon_0+\epsilon_1}}{4}\,n + \frac{3^{\epsilon_1}\epsilon_0}{4} + \frac{\epsilon_1}{2}$$ $$a_3 = \frac{3^{\epsilon_0+\epsilon_1+\epsilon_2}}{8}\,n + \frac{3^{\epsilon_1+\epsilon_2}\epsilon_0}{8} + \frac{3^{\epsilon_2}\epsilon_1}{4} + \frac{\epsilon_2}{2}$$

Mỗi lần thế thêm một bước, số mũ của $3$ ở hệ số $n$ tăng theo tổng $\epsilon$ tính đến lúc đó, còn mẫu số lũy thừa $2$ tăng theo số bước đã đi qua — đúng là "tổng quát hóa" của quy luật này mà công thức đóng bên dưới nắm bắt lại, với $S_k = \epsilon_0 + \epsilon_1 + \dots + \epsilon_{k-1}$ là số bước lẻ tính từ $a_0$ đến $a_{k-1}$:

$$a_k = \frac{3^{S_k}}{2^{k}}\, n \;+\; \sum_{j=0}^{k-1} \epsilon_j\, 3^{\,S_k - S_{j+1}}\, 2^{\,j-k}$$

Ví dụ minh họa: $n = 7$. Quỹ đạo rút gọn (dùng $T$) của $7$ và vector chẵn/lẻ tương ứng là:

$i$	$a_i$	Chẵn/lẻ	$\epsilon_i$	$S_{i+1}$
0	7	lẻ	1	1
1	11	lẻ	1	2
2	17	lẻ	1	3
3	26	chẵn	0	3
4	13	lẻ	1	4
5	20	chẵn	0	4
6	10	chẵn	0	4
7	5	lẻ	1	5
8	8	chẵn	0	5
9	4	chẵn	0	5
10	2	chẵn	0	5
11	1	—	—	—

Thử kiểm chứng công thức đóng tại $k = 3$: từ bảng, $\epsilon_0=\epsilon_1=\epsilon_2=1$ nên $S_1=1,\ S_2=2,\ S_3=3$. Thay vào:

$$a_3 = \frac{3^{3}}{2^{3}}\cdot 7 \;+\; \Big(1\cdot 3^{3-1}2^{-3} + 1\cdot 3^{3-2}2^{-2} + 1\cdot 3^{3-3}2^{-1}\Big) = \frac{189}{8} + \frac{9}{8} + \frac{6}{8} + \frac{4}{8} = \frac{208}{8} = 26$$

Khớp đúng với giá trị $a_3 = 26$ trong bảng — công thức đóng chỉ là cách "gói gọn" phép lồng affine ở trên, không có gì huyền bí hơn. Nhưng nó chỉ tính được khi đã biết trước vector $(\epsilon_i)$ — mà vector đó lại phụ thuộc $n$ theo cách không nắm bắt được (muốn biết $\epsilon_3$ ta phải biết $a_3$ chẵn hay lẻ, tức là phải chạy quỹ đạo thật sự). Nên đây không phải công thức đóng theo $n$, chỉ là công thức theo cấu trúc quỹ đạo đã biết.

Tóm lại: không có công thức tổng quát theo $n$ (nếu có thì phỏng đoán Collatz đã được giải); chỉ có công thức có điều kiện theo vector chẵn/lẻ, và nó đòi hỏi phải biết trước quỹ đạo thật sự của $n$.

Bài toán ngược: xuất phát từ $a_0 = 1$

Thay vì hỏi "$n$ bất kỳ có về $1$ không?", ta hỏi ngược lại: xuất phát từ $1$, những số nào đi tới $1$ được — tức tìm mọi tiền ảnh (predecessor) của $1$ qua hàm $f$, rồi tiền ảnh của tiền ảnh, cứ thế lùi mãi. Đây là cách "dựng cây Collatz" từ gốc.

Suy ra quy tắc nghịch đảo của $f$

Với $f(n) = n/2$ (n chẵn) hoặc $3n+1$ (n lẻ), muốn tìm mọi $n$ sao cho $f(n) = m$ ta xét hai trường hợp ngược lại:

$$n = 2m \quad \text{(luôn hợp lệ)} \qquad\qquad n = \frac{m-1}{3} \quad \text{(hợp lệ } \iff m \equiv 1 \!\!\pmod 3 \text{ và } n \text{ nguyên, lẻ)}$$

Nhánh $n = 2m$ luôn cho ra một số nguyên dương hợp lệ (vì nếu $n=2m$ thì $n$ chẵn và $f(n) = n/2 = m$ đúng) — nên mỗi số $m$ luôn có ít nhất một tiền ảnh. Nhánh còn lại chỉ xuất hiện khi $(m-1)/3$ vừa là số nguyên vừa là số lẻ (để khớp với giả thiết $n$ lẻ dùng công thức $3n+1$).

Khi nào có hai tiền ảnh?

Đặt $m = 3t + 1$ (điều kiện $m \equiv 1 \pmod 3$), khi đó tiền ảnh thứ hai chính là $n = t$. Ta cần $t$ lẻ. Xét $t$ theo modulo $2$:

$$t = 2s \Rightarrow m = 6s + 1 \ \ (t \text{ chẵn — không hợp lệ}) \qquad\qquad t = 2s+1 \Rightarrow m = 6s + 4 \ \ (t \text{ lẻ — hợp lệ})$$

Vậy kết quả rất gọn: $m$ có đúng hai tiền ảnh $\{2m,\ (m-1)/3\}$ khi và chỉ khi $m \equiv 4 \pmod 6$; mọi $m$ còn lại chỉ có một tiền ảnh duy nhất là $2m$. Vì nhánh nhân đôi luôn tồn tại, cây ngược không bao giờ "chết" — nó lùi vô hạn, chỉ thỉnh thoảng rẽ nhánh.

Dựng cây ngược từ $1$

Lùi trực tiếp từ $1$: tiền ảnh của $1$ chỉ có $2$ (vì $(1-1)/3 = 0$ không phải số dương); tiền ảnh của $2$ chỉ có $4$. Tới đây gặp lại chu trình $1 \to 4 \to 2 \to 1$ của bản đồ $f$, nên ta "cắt" chu trình và coi $4$ là gốc để cây rẽ nhánh tiếp ra phần còn lại của $\mathbb{Z}^+$:

Mức	Các số ở mức này	Rẽ nhánh mới?
0	4	— (gốc, sau khi cắt chu trình)
1	8	nhánh kia của $4$ là $1$ — đã bị cắt vì thuộc chu trình
2	16	không ($8 \equiv 2 \pmod 6$)
3	32, 5	có ($16 \equiv 4 \pmod 6$)
4	64, 10	không ($32, 5 \not\equiv 4 \pmod 6$)
5	128, 21, 20, 3	có ($64 \equiv 4$, $10 \equiv 4 \pmod 6$)

Mỗi ô ở mức $5$ đều tự kiểm chứng được bằng mô phỏng phía trên: thử nhập $3, 20, 21, 128$ sẽ thấy quỹ đạo xuôi của từng số đều đi qua đúng nút cha của nó ở mức trước (ví dụ quỹ đạo của $3$ là $3 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1$).

Vậy chuyện gì xảy ra? Đi ngược từ $1$ không cho một dãy số như đi xuôi, mà cho một cây vô hạn, phân nhánh mỗi khi gặp số $\equiv 4 \pmod 6$. Nếu chứng minh được cây này (mở rộng đến vô cùng) chứa đúng một lần mọi số nguyên dương, điều đó tương đương với phỏng đoán Collatz đúng — vì khi đó mọi $n$ đều có đường xuôi về $1$. Nhưng chiều ngược lại không giúp giải bài toán: không ai chứng minh được cây phủ kín $\mathbb{Z}^+$; về lý thuyết vẫn có thể tồn tại số không bao giờ xuất hiện trong cây (nếu quỹ đạo xuôi của nó phân kỳ ra vô cực, hoặc rơi vào một chu trình khác ngoài $1 \to 4 \to 2$) — đó chính là hai khả năng còn bỏ ngỏ của phỏng đoán.

Biểu đồ đường đi của mọi số từ 1 đến n

Mỗi đường là quỹ đạo Collatz của một số bắt đầu; màu nhạt ứng với số nhỏ, màu đậm ứng với số lớn (đường của chính $n$ được vẽ đậm nhất, nét dày hơn để dễ nhận ra).

1

n

Đỉnh cao nhất

0

Thông tin khoa học

Lịch sử & tên gọi

Bài toán do nhà toán học Lothar Collatz nêu ra năm 1937. Do được nhiều người phát hiện lại độc lập, nó mang rất nhiều tên: bài toán $3n+1$, phỏng đoán Ulam, bài toán Kakutani, phỏng đoán Thwaites, thuật toán Hasse, hay bài toán Syracuse.

Thời gian dừng (stopping time)

Với quỹ đạo $\;n,\, f(n),\, f^2(n),\, \dots$, người ta định nghĩa hai đại lượng: thời gian dừng là chỉ số nhỏ nhất mà dãy tụt xuống dưới giá trị ban đầu; thời gian dừng toàn phần là chỉ số nhỏ nhất mà dãy đạt tới $1$.

$$\sigma(n) = \min\{\, k \ge 1 : f^k(n) < n \,\}$$ $$\sigma_\infty(n) = \min\{\, k \ge 0 : f^k(n) = 1 \,\}$$

Ví dụ kinh điển: $n = 27$

Tuy nhỏ, số $27$ lại có quỹ đạo rất dài: dãy leo lên tới đỉnh $9\,232$ trước khi tụt về $1$, tổng cộng $111$ bước (trong đó có $41$ bước qua số lẻ). Đây là lý do $27$ được chọn làm giá trị mặc định của mô phỏng phía trên.

Kiểm chứng bằng máy tính

Phỏng đoán đã được kiểm chứng đúng cho mọi số nguyên dương tới khoảng $2^{71} \approx 2{,}36 \times 10^{21}$ — tất cả đều hội tụ về $1$. Tuy vậy, việc kiểm chứng bằng máy không thay thế được một chứng minh tổng quát.

Tiến triển toán học

Riho Terras (1976): chứng minh hầu hết số nguyên dương có thời gian dừng hữu hạn.
John Conway (1972): chứng minh các dạng tổng quát tự nhiên của bài toán là không quyết định được (thuật toán), liên hệ với hệ FRACTRAN.
Terence Tao (2019): chứng minh "hầu hết quỹ đạo Collatz đạt tới giá trị gần như bị chặn" — một trong những kết quả quan trọng nhất về bài toán trong nhiều thập kỷ.

Độ khó: Paul Erdős từng nhận xét "Toán học có lẽ chưa sẵn sàng cho những bài toán như thế này" và treo giải thưởng $\$500$. Năm 2010, Jeffrey Lagarias gọi đây là "một bài toán cực kỳ khó, hoàn toàn nằm ngoài tầm với của toán học hiện nay".

Nguồn: Wikipedia — Collatz conjecture.

Bài Toán Collatz 3n + 1

Nhập một số nguyên dương và xem trực quan chuỗi biến đổi Collatz về 1 qua biểu đồ HTML5 Canvas: số bước nhảy, số lần chia đôi, số lần 3n+1 và đỉnh cao nhất của quỹ đạo.