Rubik có bao nhiêu trạng thái? Đếm từng bước ra 43 tỷ tỷ

Trạng thái là gì?

Một trạng thái là một cách sắp xếp các màu trên khối mà bạn có thể đạt được chỉ bằng cách xoay các mặt. Khối đã giải là một trạng thái. Xoay một mặt là đã sang trạng thái khác. Chỉ ba nước F R U đã cho bạn một khối trông khá lộn xộn:

Hình bên trái là khối sau ba nước đó, bên phải là khối đã giải. Nếu bạn chưa quen các chữ cái R, U, F, xem bài Ký hiệu Rubik cho người mới.

Khi đếm, ta không tháo khối ra. Ta chỉ đếm những trạng thái mà tay xoay có thể tạo ra. Điều này quan trọng, vì nó làm con số nhỏ đi 12 lần, như bạn sẽ thấy ở cuối bài.

Sáu viên trung tâm đứng yên

Khối 3x3 có 26 viên nhìn thấy được: 6 viên trung tâm, 8 viên góc và 12 viên cạnh. Viên trung tâm chỉ xoay tại chỗ, không bao giờ đổi chỗ cho nhau: trắng luôn đối diện vàng, đỏ luôn đối diện cam. Vì vậy ta coi sáu viên trung tâm là "khung" cố định, và chỉ cần đếm cách sắp xếp góc và cạnh.

Bước 1: đặt 8 viên góc vào 8 chỗ

Có 8 chỗ cho viên góc. Viên đầu tiên có 8 chỗ để chọn, viên thứ hai còn 7, viên thứ ba còn 6, cứ thế đến viên cuối chỉ còn 1 chỗ:

8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 40.320 cách.

Trong toán học, tích này được viết gọn là 8! (đọc là "8 giai thừa").

Bước 2: xoay hướng 8 viên góc

Mỗi viên góc có ba ô màu, nên khi nằm trong một chỗ nó có thể quay theo 3 hướng. Nếu 8 viên góc được xoay tự do thì có 3 mũ 8 cách. Nhưng khối thật không cho phép điều đó: không thể xoay riêng một viên góc. Khi bảy viên góc đã có hướng, hướng của viên thứ tám bị ép theo.

Vì vậy chỉ có 3 mũ 7 = 2.187 cách xoay hướng các viên góc.

Bạn có thể tự thấy luật này. Cụm R' D' R D làm hai lần thì viên góc trước bên phải tầng trên xoay một chiều. Xoay U để đưa viên góc kế bên vào chỗ đó, làm cụm này bốn lần, rồi xoay U' trả lại. Kết quả: hai viên góc tầng trên bị xoay, ngược chiều nhau, mọi viên khác về như cũ.

Hai viên góc luôn "bù" cho nhau. Không có cách nào để chỉ một viên bị xoay.

Ghép bước 1 và bước 2, phần góc có 40.320 × 2.187 = 88.179.840 trạng thái.

Bước 3: đặt 12 viên cạnh vào 12 chỗ

Cách đếm giống bước 1: 12 × 11 × ... × 1 = 12! = 479.001.600 cách.

Nhưng lại có một luật: không thể đổi chỗ đúng hai viên mà giữ nguyên mọi viên khác. Mỗi nước xoay một mặt dời 4 viên góc và 4 viên cạnh cùng một lúc, nên các lần "đổi chỗ" của góc và của cạnh luôn đi đôi với nhau. Nếu hai viên cạnh đổi chỗ, thì hai viên góc cũng phải đổi chỗ.

T-perm là ví dụ rõ nhất. Nó đổi chỗ hai viên góc và hai viên cạnh cùng lúc:

R U R' U' R' F R2 U' R' U' R U R' F'

Luật này cắt đôi số cách, vì một nửa số cách xếp không bao giờ đạt được. Phần đặt chỗ cạnh còn 479.001.600 ÷ 2 = 239.500.800 cách.

Bước 4: lật hướng 12 viên cạnh

Mỗi viên cạnh có hai ô màu, nên có 2 hướng: đúng hoặc bị lật. Giống viên góc, không thể lật riêng một viên cạnh. Số viên cạnh bị lật luôn là số chẵn, nên khi 11 viên đã có hướng, viên thứ 12 bị ép theo.

Vì vậy có 2 mũ 11 = 2.048 cách lật cạnh.

Chuỗi sau lật đúng hai viên cạnh tầng trên (trước và trái) tại chỗ, mọi viên khác về như cũ:

F R B L U L' U B' R' F' L' U' L U'

Ghép bước 3 và bước 4, phần cạnh có 239.500.800 × 2.048 = 490.497.638.400 trạng thái.

Nhân tất cả lại

Góc và cạnh độc lập với nhau (trừ luật đổi chỗ đã tính ở bước 3), nên ta nhân hai phần:

Đây đúng là con số mà Wikipedia ghi trong mục Permutations của bài Rubik's Cube, với cùng công thức 8! × 3 mũ 7 × 12!/2 × 2 mũ 11 (Wikipedia). Trang cube20.org của nhóm Tomas Rokicki cũng dùng con số này (cube20.org).

43 tỷ tỷ lớn cỡ nào?

Một tỷ tỷ là một tỷ nhân một tỷ. Vài cách hình dung:

- Nếu mỗi giây bạn xem một trạng thái, không ngủ, không nghỉ, bạn cần khoảng 1.370 tỷ năm để xem hết. (Chúng tôi tự tính: 43 tỷ tỷ giây chia cho số giây trong một năm.) - Theo Wikipedia, nếu có một khối Rubik cỡ thường cho mỗi trạng thái, số khối đó đủ phủ kín bề mặt Trái Đất 275 lần, hoặc xếp thành một cột cao 261 năm ánh sáng (Wikipedia). ## Xoay mãi một cụm nước rồi cũng về

Số trạng thái lớn nhưng có hạn. Hệ quả thú vị: lặp lại bất kỳ cụm nước nào đủ nhiều lần, khối luôn quay về trạng thái ban đầu.

Cụm "sexy move" R U R' U' làm 6 lần là khối về như cũ. Đây là hình sau một lần:

1. Bạn đang có (đầu vào)
3. Sau công thức

Cụm hai nước R U cần tới 105 lần mới về. Cả hai con số đều được đếm trên trình mô phỏng của EasyRubic. Bạn thử với khối thật: cụm R U R' U' sáu lần là bài tập tốt để làm quen ký hiệu.

Nếu tháo khối ra lắp lại thì sao?

Ba luật ở trên (không xoay riêng một góc, không lật riêng một cạnh, không đổi chỗ đúng hai viên) chỉ đúng khi bạn xoay mặt. Khi tháo khối ra và lắp lại tuỳ ý, cả ba luật không còn nữa:

• Hướng góc: 3 mũ 8 thay vì 3 mũ 7, gấp 3 lần.
• Hướng cạnh: 2 mũ 12 thay vì 2 mũ 11, gấp 2 lần.
• Đặt chỗ cạnh: 12! thay vì 12!/2, gấp 2 lần.

Tổng cộng gấp 3 × 2 × 2 = 12 lần, tức khoảng 519 tỷ tỷ cách lắp (đúng là 519.024.039.293.878.272.000). Wikipedia ghi rằng chỉ một phần mười hai số đó giải được (Wikipedia). Nói cách khác, lắp các viên vào ngẫu nhiên thì 11 trên 12 lần bạn sẽ có một khối không bao giờ giải được. Bài Rubik không giải được chỉ cách nhận ra và sửa.

Số của Chúa: mọi trạng thái giải được trong 20 nước

Với 43 tỷ tỷ trạng thái, câu hỏi tự nhiên là: trạng thái khó nhất cần bao nhiêu nước? Người chơi gọi con số này là Số của Chúa (God's Number), vì đó là số nước mà một người "biết tất cả" cần dùng trong trường hợp xấu nhất.

Câu trả lời là 20. Theo cube20.org, tháng 7 năm 2010, Tomas Rokicki, Herbert Kociemba, Morley Davidson và John Dethridge chứng minh điều này, dùng khoảng 35 năm CPU thời gian máy tính do Google tặng (cube20.org). Ở đây một "nước" là xoay một mặt 90 hoặc 180 độ, nên U2 tính là một nước. Nếu chỉ tính nước 90 độ (U2 là hai nước), Số của Chúa là 26, cũng theo cube20.org.

Trạng thái đầu tiên được chứng minh là cần đúng 20 nước là superflip: mọi viên đều đúng chỗ, nhưng cả 12 viên cạnh đều bị lật. Theo cube20.org, Michael Reid chứng minh điều này năm 1995. Đây là một chuỗi 20 nước tạo ra superflip, theo Wikipedia (Wikipedia):

U R2 F B R B2 R U2 L B2 R U' D' R2 F R' L B2 U2 F2

1. Bạn đang có (đầu vào)
3. Sau công thức

Bên trái là superflip: mọi viên góc và tâm đúng, cả 12 viên cạnh bị lật. Làm chuỗi này thêm một lần nữa, khối về như cũ.

Lưu ý: 20 nước là lời giải ngắn nhất, do máy tính tìm. Người giải bằng tay dùng nhiều nước hơn hẳn, vì họ đi theo một phương pháp dễ nhớ như CFOP chứ không tìm lời giải ngắn nhất.

Còn khối 2x2?

Khối 2x2 chỉ có 8 viên góc và không có viên trung tâm cố định. Theo Wikipedia, nó có 3.674.160 trạng thái, tính bằng 8! × 3 mũ 7 rồi chia cho 24, vì không có tâm nên phải bỏ đi 24 cách cầm khối khác nhau (Wikipedia). Mọi trạng thái 2x2 giải được trong 11 nước (hoặc 14 nếu chỉ tính nước 90 độ). Muốn tự giải, xem bài Cách giải Rubik 2x2 cho người mới.

Bảng tóm tắt các chuỗi nước trong bài

Mỗi chuỗi đi kèm hình của nó, cầm mặt trắng ở trên.

• Xoay hai viên góc: R' D' R D hai lần, U, bốn lần, U'

• T-perm, đổi chỗ hai góc và hai cạnh: R U R' U' R' F R2 U' R' U' R U R' F'

• Lật hai viên cạnh: F R B L U L' U B' R' F' L' U' L U'

• Sexy move, sáu lần là về: R U R' U'

1. Bạn đang có (đầu vào)
3. Sau công thức

• Superflip, 20 nước: U R2 F B R B2 R U2 L B2 R U' D' R2 F R' L B2 U2 F2

1. Bạn đang có (đầu vào)
3. Sau công thức

Luyện trên khối của chính bạn

Với ứng dụng EasyRubic, bạn có thể quét khối thật bằng camera và xem lời giải từng bước trên khối 3D. Tải EasyRubic và thử chọn một trong 43 tỷ tỷ trạng thái cho riêng mình.

Video tham khảo

Muốn xem bằng hình ảnh chuyển động? Video ngắn dưới đây của kênh CHIEN MATH trên YouTube minh hoạ thêm cho nội dung bài. Video thuộc về kênh đó và được nhúng trực tiếp từ YouTube.

Nguồn tham khảo

• Rubik's Cube – Wikipedia (Permutations, Optimal solutions)
• God's Number is 20 – cube20.org
• Superflip – Wikipedia
• Pocket Cube – Wikipedia