Khối Rubik 3×3 có đúng 43252003274489856000 trạng thái giải được, tức hơn 43 tỷ tỷ. Con số này tính được bằng tổ hợp đơn giản: đếm cách sắp xếp 8 khối góc và 12 khối cạnh, nhân với số cách xoay hướng của chúng, rồi chia cho 12 vì có ba ràng buộc cơ học. Năm 2010, một nhóm nghiên cứu dùng máy tính chứng minh mọi trạng thái trong số đó đều đưa về được trạng thái ban đầu trong tối đa 20 bước, nếu tính xoay nửa vòng là một bước.
Bài này đi từng bước phép tính, giải thích vì sao lại chia cho 12, và kể lại ngắn gọn hành trình đi đến con số 20. Bạn chỉ cần biết phép nhân và giai thừa. Phần cuối nói về vì sao những ý toán này có ích cho người luyện khối, kể cả khi không định học toán.
Tính số trạng thái từng bước
Ta đếm những gì có thể thay đổi. Sáu khối tâm cố định so với nhau nên không tính. Còn lại 8 góc và 12 cạnh.
- Vị trí khối góc: 8 khối góc xếp vào 8 chỗ, có 8! = 40320 cách.
- Hướng khối góc: mỗi góc có 3 màu nên xoay được 3 hướng. Nếu tự do thì là 3 mũ 8, nhưng hướng của góc cuối cùng bị các góc kia quyết định, nên chỉ còn 3 mũ 7 = 2187.
- Vị trí khối cạnh: 12 khối cạnh vào 12 chỗ, có 12! = 479001600 cách.
- Hướng khối cạnh: mỗi cạnh có 2 hướng; cạnh cuối bị quyết định bởi các cạnh kia, nên còn 2 mũ 11 = 2048.
- Ràng buộc chẵn lẻ: hoán vị của góc và hoán vị của cạnh luôn cùng tính chẵn lẻ, nên chỉ một nửa số cách ghép vị trí là đạt được; chia 2.
- Nhân lại: 8! × 3 mũ 7 × 12! × 2 mũ 11 ÷ 2 ra đúng con số hơn 43 tỷ tỷ ở trên.
Hai ràng buộc về hướng làm số trạng thái giảm 3 lần và 2 lần, ràng buộc chẵn lẻ giảm thêm 2 lần: tổng cộng 3 × 2 × 2 = 12. Đó là nguồn gốc của con số một phần mười hai mà bạn sẽ gặp ở phần sau.
Vì sao tháo ra lắp ngẫu nhiên chỉ một phần mười hai giải được
Nếu tháo khối ra rồi lắp các khối nhỏ vào tùy ý, bạn không bị ba ràng buộc kia ràng buộc nữa. Số cách lắp lúc đó lớn gấp 12 lần số trạng thái giải được. Nói cách khác, trạng thái lắp tùy ý chia thành 12 "thế giới" tách rời, mỗi thế giới có hơn 43 tỷ tỷ trạng thái, và chỉ thế giới chứa trạng thái ban đầu là giải được bằng cách xoay.
Ba triệu chứng điển hình của khối bị lắp sai: chỉ một khối góc bị xoay lệch hướng ở bước cuối, chỉ một khối cạnh bị lật ngược, hoặc chỉ hai khối cạnh đổi chỗ cho nhau mà mọi thứ khác đều đúng. Không chuỗi xoay nào sửa được những trạng thái này. Cách duy nhất là tháo đúng khối đó ra lắp lại cho đúng.
Điều này cũng giải thích một chuyện hay gặp với trẻ nhỏ: khối bị rơi bung một hai khối, trẻ lắp lại theo cảm tính, rồi luyện mãi không xong. Người lớn nên kiểm tra bằng cách giải đến gần cuối; nếu thấy một trong ba triệu chứng trên thì sửa lắp, đừng để trẻ nghĩ mình kém. Phần cách tháo lắp an toàn có trong bài về bảo dưỡng khối.
Con số lớn đến mức nào
Con số hơn 43 tỷ tỷ khó hình dung. Bảng dưới đặt nó cạnh vài đại lượng quen thuộc; các phép so sánh đều là ước lượng làm tròn.
| Phép so sánh | Ước lượng | Ý nghĩa |
|---|---|---|
| Xem mỗi trạng thái một giây, không nghỉ | Khoảng 1.370 tỷ năm | Gấp gần một trăm lần tuổi vũ trụ theo ước tính hiện nay |
| So với khối 2×2 | Khối 2×2 có 3.674.160 trạng thái | 3×3 nhiều hơn khoảng mười nghìn tỷ lần |
| Xáo ngẫu nhiên hai lần | Gần như không bao giờ trùng | Vì vậy chuỗi xáo thi đấu sinh bằng máy vẫn công bằng |
| Số bước tối đa cần | 20 bước | Khoảng cách xa nhất giữa hai trạng thái bất kỳ là rất ngắn so với số trạng thái |
Điểm đáng ngạc nhiên nằm ở dòng cuối: số trạng thái khổng lồ, nhưng mọi trạng thái lại ở rất gần nhau. Đó là vì mỗi bước xoay mở ra khoảng 18 lựa chọn, nên chỉ sau 20 bước số đường đi đã vượt xa số trạng thái.
Cũng vì vậy mà luật thi không dùng tay người để xáo: một người xáo bằng tay thường lặp lại thói quen, dễ tạo trạng thái dễ hơn trung bình. Chuỗi xáo do máy sinh ra từ một trạng thái chọn ngẫu nhiên trong toàn bộ hơn 43 tỷ tỷ trạng thái, rồi mới đổi thành chuỗi xoay cho người xáo làm theo, bảo đảm mọi người thi cùng lượt nhận cùng một độ khó.
Hành trình đến con số 20
Con số 20 thường được gọi vui là con số của Chúa, ý nói số bước tối thiểu mà một người biết mọi thứ cần để giải trạng thái khó nhất. Việc tìm ra nó đi theo hai hướng: hạ cận trên (chứng minh "không cần quá N bước") và nâng cận dưới (chỉ ra "có trạng thái cần ít nhất N bước").
- Đầu thập niên 1980: các thuật toán chia nhỏ khối thành nhiều nhóm con cho thấy mọi trạng thái giải được trong khoảng năm mươi bước; cận dưới khi ấy chỉ khoảng mười tám bước, suy từ phép đếm.
- Thập niên 1990: các thuật toán hai pha tìm được lời giải ngắn cho từng trạng thái cụ thể rất nhanh; cận trên giảm dần qua nhiều công trình.
- Giữa thập niên 1990: người ta chứng minh trạng thái lật ngược cả 12 cạnh mà mọi khối khác đúng chỗ cần đúng 20 bước. Cận dưới thành 20.
- 2010: một nhóm nghiên cứu chia toàn bộ trạng thái thành hàng tỷ nhóm, dùng thời gian máy tính rất lớn để giải hết, chứng minh không trạng thái nào cần quá 20 bước. Cận trên gặp cận dưới.
- Vài năm sau: con số tương ứng theo cách đếm phần tư vòng được chứng minh là 26.
Đa số trạng thái chỉ cần khoảng 17 đến 18 bước; trạng thái cần đúng 20 bước rất hiếm. Còn người giải nhanh thì dùng 50 đến 60 bước, vì họ chọn cách dễ nhận diện và dễ thực hiện bằng tay, không chọn cách ngắn nhất.
Giao hoán tử và liên hợp: hai ý toán dùng được ngay
Giao hoán tử là làm A, làm B, hoàn A, hoàn B. Nếu A và B chỉ "đụng nhau" ở vài khối, chuỗi A B A′ B′ sẽ chỉ thay đổi đúng vài khối đó, phần còn lại trở về như cũ. Đây là bí mật đằng sau phần lớn công thức: chúng đổi chỗ ba khối hoặc xoay hai khối mà không phá phần đã xong.
Liên hợp là chuẩn bị, làm, hoàn chuẩn bị. Nếu bạn có công thức đổi ba khối ở vị trí X, Y, Z mà khối cần đổi lại nằm ở chỗ khác, hãy làm một chuỗi đưa chúng về X, Y, Z, dùng công thức, rồi làm ngược chuỗi đưa về. Viết gọn là S A S′. Đây là kỹ thuật cốt lõi của giải bịt mắt.
Thứ tự của một chuỗi. Lặp một chuỗi xoay đủ số lần thì khối luôn quay về trạng thái ban đầu. Ví dụ quen thuộc: lặp cụm R U R′ U′ sáu lần là khối trở lại như cũ. Bạn có thể tự kiểm trên khối đã giải.
Áp dụng với khối lạ. Gặp một khối hoàn toàn mới, người hiểu giao hoán tử có thể tự giải mà không cần tra công thức: tìm hai chuỗi chỉ đụng nhau ở ít khối, ghép thành giao hoán tử, rồi dùng liên hợp đưa khối cần sửa vào đúng chỗ.
Toán học giúp gì cho người luyện khối
Bạn không cần lý thuyết nhóm để giải nhanh. Nhưng hiểu được vài ý trên mang lại ba lợi ích thực tế. Thứ nhất, biết nhận ra trạng thái không thể, để không mất hàng giờ tìm công thức cho một khối lắp sai. Thứ hai, hiểu công thức chứ không chỉ thuộc, nên khi quên một chuỗi bạn vẫn tự dựng lại được bằng giao hoán tử. Thứ ba, mở đường sang các nội dung đòi hỏi tư duy hơn tay nhanh, như giải bịt mắt hay tìm lời giải ít bước nhất bằng giấy bút.
Với giáo viên toán, khối xoay là đồ dùng trực quan rất tốt cho phần hoán vị, tổ hợp và tính chẵn lẻ ở bậc phổ thông. Một hoạt động lớp học gợi ý: cho học sinh tự đếm số trạng thái của khối 2×2 trước, so với con số chính thức, rồi thảo luận vì sao phải cố định một góc. Hoạt động này không cần học sinh giải được khối, và không cần chấm điểm ai giải nhanh hơn ai.
Vì sao góc và cạnh luôn cùng tính chẵn lẻ
Ràng buộc chia 2 là ràng buộc khó hình dung nhất, nhưng có thể giải thích bằng một quan sát. Mỗi lần xoay một mặt một phần tư vòng, bốn khối góc trên mặt đó đổi chỗ theo vòng tròn, và bốn khối cạnh cũng đổi chỗ theo vòng tròn. Một vòng đổi chỗ bốn phần tử tương đương ba lần đổi chỗ từng cặp, tức là một hoán vị lẻ. Vậy mỗi lần xoay, hoán vị của góc đổi tính chẵn lẻ, và hoán vị của cạnh cũng đổi tính chẵn lẻ, cùng lúc.
Bắt đầu từ trạng thái đã giải, cả hai hoán vị đều chẵn. Sau một lần xoay cả hai lẻ, sau hai lần cả hai chẵn, cứ thế mãi. Hai hoán vị không bao giờ lệch tính chẵn lẻ với nhau. Do đó trạng thái chỉ có đúng hai khối cạnh đổi chỗ (hoán vị lẻ của cạnh) mà góc đều đúng chỗ (hoán vị chẵn của góc) là không thể đạt được bằng cách xoay.
Lập luận tương tự giải thích hai ràng buộc về hướng: mỗi lần xoay giữ nguyên tổng số lần xoay hướng của các góc theo modulo 3, và tổng số lần lật cạnh theo modulo 2. Khối 4×4 không có ràng buộc chẵn lẻ giữa các cạnh như vậy vì cơ cấu khác, nên mới xuất hiện các trường hợp chẵn lẻ khiến người mới bối rối.
Câu hỏi thường gặp
Vì sao không tính sáu khối tâm khi đếm số trạng thái?
Vì sáu khối tâm gắn vào lõi và luôn giữ nguyên vị trí so với nhau. Xoay cả khối trong tay chỉ đổi mặt nào hướng về bạn, không tạo trạng thái mới, nên người ta quy ước cố định các tâm khi đếm.
Số trạng thái khối 2×2 tính thế nào?
Cố định một góc để loại bỏ việc xoay cả khối, còn 7 góc với 7! cách xếp và 3 mũ 6 cách xoay hướng (góc cuối bị quyết định). Nhân lại ra 3.674.160 trạng thái.
Có ai giải được trạng thái bất kỳ trong 20 bước bằng tay không?
Trong thi đấu tìm lời giải ít bước nhất bằng giấy bút, người giỏi thường tìm được lời giải khoảng hai mươi mấy bước trong thời gian giới hạn, nhưng tìm lời giải tối ưu bằng tay cho mọi trạng thái thì nằm ngoài khả năng thực tế.
Một khối cạnh lật ngược một mình có sửa bằng công thức được không?
Không. Trên khối 3×3 nguyên vẹn, số khối cạnh lật luôn là số chẵn. Nếu chỉ thấy một cạnh lật, khối đã bị tháo lắp hoặc bung ra lắp sai; bạn cần tháo khối cạnh đó ra lắp lại đúng hướng.
Vì sao gọi là con số của Chúa?
Đây là cách gọi vui trong cộng đồng, ý chỉ số bước mà một người biết hết mọi lời giải tối ưu cần cho trạng thái khó nhất. Tên gọi chỉ là cách nói hình ảnh, nhấn mạnh rằng con người bình thường không tính được tối ưu bằng đầu.
Học sinh phổ thông có hiểu được phép tính này không?
Có. Phép tính chỉ cần giai thừa và lũy thừa, học ở phần tổ hợp lớp 10 hoặc lớp 11. Ý về tính chẵn lẻ của hoán vị cần giải thích thêm, nhưng có thể minh hoạ trực tiếp bằng khối.