Số Graham là một số nguyên cụ thể, hữu hạn, xuất hiện trong một bài toán tô màu của nhà toán học Ronald Graham, và lớn tới mức không có cách nào viết nó ra bằng chữ số, kể cả viết dưới dạng tháp luỹ thừa. Muốn mô tả nó phải dùng ký hiệu mũi tên của Donald Knuth, lặp lại 64 tầng. Vậy mà người ta vẫn biết chắc chữ số cuối cùng của nó là 7.
Bài toán sinh ra số Graham
Năm 1971, Ronald Graham và Bruce Rothschild nghiên cứu một câu hỏi thuộc lý thuyết Ramsey, nhánh toán học hỏi rằng: hệ thống lớn tới mức nào thì trật tự buộc phải xuất hiện, dù ta cố xáo trộn ra sao.
Hình dung bài toán thế này. Lấy một khối lập phương nhiều chiều (siêu lập phương) có n chiều, nó có 2ⁿ đỉnh. Nối mọi cặp đỉnh bằng một đoạn thẳng. Tô mỗi đoạn bằng một trong hai màu, đỏ hoặc xanh, tuỳ ý. Câu hỏi: số chiều n nhỏ nhất là bao nhiêu để dù tô thế nào cũng luôn tìm được bốn đỉnh nằm trên cùng một mặt phẳng mà cả sáu đoạn nối chúng cùng một màu?
Graham và Rothschild chứng minh được con số n đó tồn tại. Họ không tìm ra nó chính xác, mà chỉ kẹp nó giữa hai giới hạn: không nhỏ hơn 6, và không lớn hơn một con số khổng lồ. Con số mà ngày nay gọi là "số Graham" là một cận trên do Graham đưa ra trong công trình chưa công bố, được nhà phổ biến toán học Martin Gardner giới thiệu trong chuyên mục của ông trên tạp chí Scientific American tháng 11 năm 1977. Năm 1980, sách kỷ lục Guinness ghi nhận nó là con số lớn nhất từng được dùng trong một chứng minh toán học nghiêm túc.
Ký hiệu mũi tên của Knuth: bậc thang của các phép toán
Để hiểu số Graham, phải đi qua từng nấc phép toán. Mỗi nấc là phép lặp của nấc trước:
- Cộng lặp lại là nhân: 3 × 3 = 3 + 3 + 3 = 9.
- Nhân lặp lại là luỹ thừa: 3³ = 3 × 3 × 3 = 27. Knuth viết là 3↑3.
- Luỹ thừa lặp lại là tháp luỹ thừa (còn gọi tetration): 3↑↑3 = 3^(3^3) = 3²⁷ = 7.625.597.484.987.
- Tháp lặp lại: 3↑↑↑3 = 3↑↑(3↑↑3), tức một tháp toàn số 3 cao 7.625.597.484.987 tầng.
Donald Knuth, tác giả bộ sách The Art of Computer Programming, đưa ra ký hiệu mũi tên này năm 1976. Mỗi mũi tên thêm vào không làm số to hơn "một chút", mà làm nó nhảy lên một cõi khác.
| Biểu thức | Nghĩa | Cỡ lớn |
|---|---|---|
| 3↑3 | 3³ | 27 |
| 3↑↑2 | 3³ | 27 |
| 3↑↑3 | 3²⁷ | khoảng 7,6 nghìn tỷ |
| 3↑↑4 | 3 mũ 7,6 nghìn tỷ | có khoảng 3,6 nghìn tỷ chữ số |
| 3↑↑5 | 3 mũ (3↑↑4) | số chữ số của nó đã không viết ra được |
| 3↑↑↑3 | tháp 3 cao 7,6 nghìn tỷ tầng | vượt xa mọi đại lượng vật lý |
| 3↑↑↑↑3 | g₁, tầng đầu của số Graham | không mô tả được bằng tháp luỹ thừa |
Để có cảm giác: 3↑↑4 có khoảng 3,6 nghìn tỷ chữ số. In ra với khổ chữ 3.000 chữ số mỗi trang thì cần khoảng 1,2 tỷ trang, chất thành chồng cao hơn núi Everest nhiều lần. Đó mới chỉ là tháp bốn tầng. Còn 3↑↑↑3 là tháp cao hơn bảy nghìn tỷ tầng.
Sáu mươi tư tầng: định nghĩa số Graham
Bây giờ mới tới số Graham. Nó được dựng qua 64 bước:
- g₁ = 3↑↑↑↑3, tức ba với bốn mũi tên. Riêng con số này đã lớn hơn 3↑↑↑3 không biết bao nhiêu lần, vì nó là 3↑↑↑(3↑↑↑3).
- g₂ = 3 ↑…↑ 3 với số mũi tên bằng g₁. Không phải bốn mũi tên, mà là g₁ mũi tên.
- g₃ dùng g₂ mũi tên.
- Cứ thế cho tới g₆₄. Số Graham chính là g₆₄.
Chỗ khó hình dung nhất là bước 2. Ở bước 1, số mũi tên là bốn, một con số đếm trên đầu ngón tay. Ở bước 2, số mũi tên đã là một con số mà không có tháp luỹ thừa nào trong vũ trụ chứa nổi. Và ta lặp việc đó 63 lần.
Một hình ảnh hay được nhắc: nếu bạn cố nhớ toàn bộ chữ số của số Graham trong đầu, khối thông tin đó sẽ vượt giới hạn lượng thông tin tối đa mà một vùng không gian cỡ cái đầu có thể chứa theo vật lý (giới hạn Bekenstein), và về lý thuyết vùng đó sẽ sụp thành hố đen. Đây là cách nói vui để nhấn mạnh, nhưng phần cốt lõi là đúng: không thể lưu trữ các chữ số của số Graham ở bất cứ đâu trong vũ trụ quan sát được.
Vì sao vẫn biết chữ số cuối là 7
Nghe thì vô lý: không viết được số mà lại biết chữ số cuối. Nhưng bạn có thể tự kiểm phần cốt lõi bằng tay.
Xét chữ số tận cùng của các luỹ thừa của 3: 3¹ = 3, 3² = 9, 3³ = 27, 3⁴ = 81, 3⁵ = 243. Tận cùng lặp lại theo chu kỳ 4: 3, 9, 7, 1, 3, 9, 7, 1… Vậy chữ số cuối của 3ᵏ chỉ phụ thuộc vào k chia 4 dư mấy.
- Số mũ trên cùng của mọi tháp số 3 đều là một luỹ thừa lẻ của 3.
- Luỹ thừa lẻ của 3 chia 4 luôn dư 3 (vì 3 ≡ −1 theo mô-đun 4, mũ lẻ thì vẫn là −1).
- Vậy chữ số cuối là chữ số cuối của 3³ = 27, tức là 7.
Dùng cùng lối lập luận với chu kỳ dài hơn, người ta tính được hàng chục, hàng trăm chữ số cuối. Các tháp số 3 đủ cao thì các chữ số cuối "đóng băng", không đổi dù tháp cao thêm. Mười chữ số tận cùng của số Graham là …2464195387. Nhiều người đã viết chương trình tính tới hàng nghìn chữ số cuối. Còn chữ số đầu tiên thì không ai biết, và gần như chắc chắn sẽ không bao giờ biết.
Đáp án thật của bài toán nhỏ hơn rất nhiều
Điều thú vị: số Graham chỉ là cận trên, tức "đáp án chắc chắn không vượt quá số này". Đáp án thật có thể nhỏ hơn đến mức khó tưởng tượng.
| Năm | Kết quả | Ghi chú |
|---|---|---|
| 1971 | Đáp án ít nhất là 6 | Graham và Rothschild |
| 1977 | Cận trên g₆₄ được phổ biến | Martin Gardner, Scientific American |
| 2003 | Đáp án ít nhất là 11 | Geoffrey Exoo |
| 2008 | Đáp án ít nhất là 13 | Jerome Barkley |
| Từ 2014 trở đi | Cận trên được hạ xuống còn nhỏ hơn số Graham rất xa | nhiều nhóm tác giả, vẫn là số rất lớn |
Vậy đáp án nằm đâu đó từ 13 trở lên, dưới một cận trên tuy đã hạ nhiều nhưng vẫn khổng lồ. Graham từng nói ông nghĩ đáp án thật có thể khá nhỏ. Khoảng cách giữa "ít nhất 13" và "nhiều nhất là con số mấy chục tầng mũi tên" cho thấy một nét đặc trưng của lý thuyết Ramsey: chứng minh trật tự tồn tại thì dễ hơn rất nhiều so với chỉ ra chính xác lúc nào nó xuất hiện.
Số Graham có phải số lớn nhất không
Không. Không có số tự nhiên lớn nhất, vì lấy bất kỳ số nào cộng thêm 1 là có số lớn hơn. Số Graham chỉ đặc biệt ở chỗ nó là một con số được dùng thật trong chứng minh, chứ không phải bịa ra cho to. Sau này toán học còn gặp những số lớn hơn nó rất nhiều, cũng sinh ra từ bài toán thật, như TREE(3) trong lý thuyết đồ thị.
So với những số lớn có tên quen thuộc hơn, khoảng cách là khó tả. Googol là 10¹⁰⁰, googolplex là 10 mũ googol, đều chỉ là tháp hai, ba tầng, nhỏ hơn 3↑↑5. Số Graham ở một tầng phép toán hoàn toàn khác.
Góc nhìn hôm nay: tự chơi với mũi tên
Muốn cảm được số Graham, cách tốt nhất là tự tính vài nấc nhỏ. Thử 2↑↑3 = 2^(2^2) = 16, 2↑↑4 = 2¹⁶ = 65.536, 2↑↑5 = 2^65.536, một số có 19.729 chữ số. Rồi thử 2↑↑↑3 = 2↑↑(2↑↑2) = 2↑↑4 = 65.536. Bạn sẽ thấy số 2 tăng chậm hơn số 3 rất nhiều ở nấc đầu, nhưng chỉ vài bước là đã chạm những số không viết ra nổi.
Một mẹo hay: bất kỳ biểu thức nào có dạng 2↑…↑2 (hai số 2, bao nhiêu mũi tên cũng được) đều bằng 4. Hãy thử chứng minh, đó là bài tập nhỏ giúp nắm vững định nghĩa đệ quy của mũi tên.
Đọc thêm: chuyên mục của Martin Gardner trên Scientific American đã được tập hợp thành nhiều tuyển tập sách; các video phỏng vấn chính Ronald Graham (ông mất năm 2020) trên các kênh phổ biến toán học vẫn là cách dễ nghe nhất để hiểu bài toán siêu lập phương từ người đặt ra nó.
Câu hỏi thường gặp
Số Graham là gì?
Số Graham là một cận trên trong bài toán tô màu cạnh của siêu lập phương thuộc lý thuyết Ramsey, do Ronald Graham đưa ra và Martin Gardner phổ biến năm 1977. Nó được định nghĩa bằng ký hiệu mũi tên Knuth qua 64 tầng, bắt đầu từ g₁ = 3↑↑↑↑3, và lớn tới mức không thể viết ra.
Số Graham lớn hơn googolplex bao nhiêu?
Lớn hơn tới mức không so sánh được bằng phép chia hay số mũ. Googolplex là 10^(10^100), chỉ là một tháp ba tầng và còn nhỏ hơn 3↑↑5. Riêng tầng đầu g₁ của số Graham đã là một tháp luỹ thừa cao hơn bảy nghìn tỷ tầng được lặp lại thêm nữa.
Chữ số cuối của số Graham là gì?
Chữ số cuối là 7, và mười chữ số tận cùng là 2464195387. Người ta tính được nhờ chữ số tận cùng của luỹ thừa của 3 lặp theo chu kỳ, và các tháp số 3 đủ cao có phần đuôi không đổi.
Số Graham có phải là số lớn nhất không?
Không có số lớn nhất, vì luôn cộng thêm 1 được. Số Graham từng được Guinness ghi là số lớn nhất dùng trong một chứng minh toán học, nhưng sau đó đã có những số lớn hơn rất nhiều xuất hiện trong toán học, như TREE(3).
Ký hiệu mũi tên Knuth là gì?
Đó là cách viết do Donald Knuth đưa ra năm 1976: một mũi tên là luỹ thừa, hai mũi tên là luỹ thừa lặp (tháp luỹ thừa), ba mũi tên là tháp lặp lại, và cứ thế. Ví dụ 3↑↑3 = 3²⁷ = 7.625.597.484.987.
