HẰNG SỐ 10⁴⁰ HẠ XUỐNG CÒN 30,5 CHO NHỮNG KHỐI RUBIK KHỔNG LỒ
Khối Rubik, vừa tròn 50 tuổi, có lẽ là trò chơi đố nổi tiếng nhất thế giới, và một trong những câu hỏi trọng tâm của nó rất dễ phát biểu: trong trường hợp xấu nhất, cần bao nhiêu nước đi để giải? Với khối 3×3×3 cổ điển, câu trả lời được biết chính xác: 20 nước đi, một kết quả được công bố năm 2014 bởi một nhóm có Tomas Rokicki, một trong các tác giả của bài báo mới này.
Với những khối lớn hơn, có n lớp dọc theo mỗi cạnh, câu trả lời chính xác nằm ngoài tầm với — việc giải tối ưu một khối n×n×n cho trước thậm chí là bài toán NP-đầy đủ (NP-complete). Nhưng năm 2011, Erik Demaine và các đồng nghiệp đã chỉ ra trường hợp xấu nhất tăng như thế nào: tỉ lệ với n² / lg n, trong đó lg là logarit cơ số 2. Như vậy là tốt hơn một thừa số logarit so với các phương pháp tiêu chuẩn, vốn về cơ bản giải từng mảnh một.
Một chứng minh với hằng số phi lý
Có một điểm vướng. Kết quả năm 2011 bảo đảm tốc độ tăng, chứ không phải con số đứng trước nó. Khi lần theo thuật toán đó, các tác giả nhận thấy hằng số của nó vào khoảng 1,01 × 10⁴⁰, tức 10 mũ 40. Thủ phạm là một phép kiểm tra bằng máy tính đã chứng minh rằng một số nước đi nhất định có thể đạt tới mọi cách sắp xếp của một nhóm 24 mảnh, mà không cho biết nhanh đến mức nào. Cận an toàn duy nhất cho độ dài đó là kích thước của nhóm các cách sắp xếp đó, khoảng 3,1 × 10²³ bước, và rốt cuộc công thức dùng con số khổng lồ 24! (1 × 2 × … × 24, khoảng 6,2 × 10²³) ở hai chỗ. Ngược lại, cận dưới — số nước đi mà gần như mọi khối bị xáo trộn đều cần — có một hằng số khiêm tốn khoảng 12,88. Vì thế, nhiều người trong cộng đồng tin rằng một thuật toán như vậy không bao giờ có thể dùng được trong thực tế với các kích thước hợp lý.
Jeremy Mrzyglocki, Tomas Rokicki, Maxine Perroni-Scharf và Erik Demaine, đến từ MIT, TU Munich và Palo Alto, nay đã làm cho hằng số đó trở nên tường minh và nhỏ.
Mạng sắp xếp cho các mảnh của khối Rubik
Trên một khối lớn, các mảnh trung tâm chiếm ưu thế: số lượng của chúng tăng theo n², trong khi các mảnh góc và mảnh cạnh chỉ thêm vào những số hạng tỉ lệ với n. Các mảnh trung tâm chia thành những họ gồm 24 mảnh, chỉ có thể hoán đổi với nhau. Công cụ cơ bản là hoán tử (commutator), một chuỗi có dạng A B A′ B′ giữ nguyên gần như mọi thứ và chỉ hoán vị ba mảnh của một họ. Nhóm nghiên cứu đã tìm ra các chuỗi nước đi cho cả 4.000 phép hoán đổi ba mảnh dùng được, mỗi chuỗi dài tối đa 12 nước.
Hai ý tưởng giúp con số giảm xuống. Thứ nhất, cùng một hoán tử có thể được áp dụng cho nhiều họ cùng lúc, trên cả những nhóm hàng và cột. Thứ hai, thay vì giải riêng từng họ, mọi họ đều tuân theo một chuỗi phổ quát (universal sequence) cố định gồm các phép hoán đổi, chỉ đơn giản bỏ qua những phép mà nó không cần. Một bổ đề gắn kết tất cả lại: một chuỗi phổ quát gồm L giai đoạn cho một hằng số dẫn đầu bằng L/2.
Việc rút ngắn chuỗi đó mượn công cụ từ mạng sắp xếp (sorting networks) của khoa học máy tính, những mẫu so sánh cố định có thể sắp xếp bất kỳ đầu vào nào. Một mạng sắp xếp tối ưu sáu đầu vào cho 96 giai đoạn, do đó hằng số là 48. Những mạng chia 24 vị trí thành các nhóm 12, rồi 4, được tìm ra bằng tìm kiếm trên máy tính, đưa con số xuống 72 giai đoạn (36). Cuối cùng, việc cho phép những nước đi xáo trộn hơn ba mảnh cùng lúc và chia các vị trí theo cách khác đưa nó xuống 61 giai đoạn.
Ba mươi phẩy năm
Định lý: bất kỳ khối n×n×n nào cũng có thể giải được trong tối đa 30,5 n²/lg n nước đi, cộng thêm các số hạng trở nên không đáng kể khi n lớn. Hằng số được cải thiện hơn 3,30 × 10³⁸ lần, và chỉ cách cận dưới một hệ số 2,37 (30,5 / 12,88). Với phiên bản phẳng n×n×1, dùng làm bài khởi động, hằng số giảm từ 12 hoặc 18 xuống 1,5.

Tám khung hình cách đều nhau trong quá trình giải một khối có 256 lớp mỗi cạnh: các mặt bị xáo trộn chuyển thành những màu đồng nhất. — Hình 1.1, Mrzyglocki et al. (2026), arXiv:2611.11018.
Thuật toán chạy trong thời gian tỉ lệ với số mảnh, và các tác giả cung cấp một bộ giải mã nguồn mở, kèm các script kiểm tra vét cạn mọi mạng mà nó dựa vào. Theo phép so sánh của chính họ, nó vượt các bộ giải hiện có từ khoảng n = 840; họ đã dựng hình quá trình giải các khối có 256 và 65.536 lớp mỗi cạnh.
Con số 2,37 là một phát biểu tiệm cận: các số hạng nhỏ hơn của công thức chưa được xác định cụ thể, nên nó không cho số nước đi chính xác với một khối cụ thể. Các tác giả gợi ý rằng những cải thiện trong tương lai có thể đến từ những cách khác để nhóm các mảnh vào mạng sắp xếp và từ những phép hoán đổi ba mảnh tốt hơn — và cùng bộ công cụ đó có thể giải quyết các trò đố khổng lồ khác, hoặc các siêu lập phương bốn và năm chiều.
