Không thể phủ nhận được rằng, khối lập phương Rubik luôn khiến các nhà toán học tò mò và say mê nghiên cứu. Họ ngạc nhiên khi một món đồ chơi tưởng chừng đơn giản như vậy, lại có thể chứa đựng nhiều bí mật bên trong.
Luôn luôn có một cái gì đó mới khi tìm hiểu về nó, càng nghiên cứu sâu chúng ta lại càng yêu khối lập phương đầy mê hoặc này. Nhưng có lẽ, bí mật lớn nhất trong tất cả mọi bí mật về khối Rubik, thứ khiến cho các nhà toán học phải mất hơn 30 năm để tìm ra chính là God’s Number – Con số của Chúa (hoặc Thần Số). Trong bài viết này ta sẽ chỉ dùng cái tên God’s Number.
God’s Number là gì?
Năm 1974, ngoài việc Stephen Hawking dự đoán trước được sự tồn tại của bức xạ, lần đầu tiên nước Mỹ sử dụng mã vạch để bán hàng, thì nhân loại còn chứng kiến một sự kiện đặc biệt khác: khối Rubik được ra đời bởi nhà giáo sư kiến trúc người Hungary – ông Erno Rubik.
Món đồ chơi Rubik 3×3 bao gồm 6 mặt như chúng ta đã biết, được ghép lại 27 khối lập phương nhỏ hơn. Mặc dù nó nhỏ bé, chỉ vỏn vọn trong lòng bàn tay nhưng sự biến hóa khôn lường qua mỗi lần giải khiến các nhà toán học thích thú. Và rồi câu hỏi triệu đô được đặt ra:” số bước xoay nhỏ nhất để giải MỌI CÁCH sắp xếp khối Rubik là bao nhiêu?” Con số toàn năng này được biết đến là God’s Number.
# Lưu ý: một số người thường lầm tưởng rằng God’s Number là một công thức toàn năng có thể giải được khối Rubik từ mọi vị trí, mọi trạng thái. Điều này là không đúng, chúng ta đang nói về SỐ BƯỚC di chuyển ít nhất để giải (Fewest Move). Tôi đã có một mục dành riêng để bàn về vấn đề này ở phía dưới.
Vậy God’s Number là bao nhiêu?
Như nhiều người đã biết, một khối Rubik 3×3 có tổng cộng 43.252.003.274.489.856.000 trạng thái khác nhau. Và phải mất đến 36 năm nghiên cứu, các nhà khoa học mới tìm ra được câu trả lời cho God’s Number: đó là 20 bước xoay thần thánh. Hiểu nôm na rằng, mọi trạng thái của khối Rubik đều có thể được giải trong 20 bước hoặc ít hơn. Phát hiện này được tìm ra vào tháng 7 năm 2010 bởi Tomas Rokicki cùng các cộng sự.
Trạng thái Super-Flip
Có lẽ nổi tiếng nhất trong số các Scramble (xáo trộn) hiếm hoi cần chính xác 20 bước di chuyển là trạng thái Super-Flip (siêu lật). Bạn có làm được bằng cách xoay theo công thức sau:
R L U2 F U’ D F2 R2 B2 L U2 F’ B’ U R2 D F2 U R2 U
(Có thể xoay bắt đầu từ hướng nào cũng được, chỉ cần bạn đã hoàn thiện 6 mặt của khối Rubik và áp dụng công thức trên).
Bạn có nhận ra sự đặc biệt của Scramble này không? Trong khi mọi góc đều được giữ nguyên vị trí thì tất cả các cạnh đều bị lật ngược lại. Đây cũng là trạng thái đầu tiên được chứng minh là chỉ cần mất 20 bước xoay, nâng giới hạn dưới của God’s Number lên 20 vào năm 1995.
Lịch sử God’s Number – Con số của chúa
Công việc này bắt đầu từ việc tìm kiếm God’s Number vào năm 1981, khi một người đàn ông tên Morwen Thistlewaite chứng minh bằng các thuật toán phức tạp. Đầu tiên, anh đã chỉ ra rằng 52 bước là đủ để giải quyết mọi trạng thái nào của khối Rubik. Và con số này giảm dần qua từng năm nhờ các phương pháp mới hiệu quả hơn, tốt hơn.
Bảng này sẽ tóm tắt sự thay đổi của God’s Number qua từng thời kỳ, bao gồm: giới hạn trên, giới hạn dưới và độ lệch của chúng.
Thời gian Giới hạn dưới Giới hạn trên Độ lệch Ghi chú Tháng 7/1981 18 52 34 Morwen Thistlethwaite chứng minh 52 bước là đủ. Tháng 12, 1990 18 42 24 Hans Kloosterman đã giảm xuống còn 42 bước. Tháng 5/ 1992 18 39 21 Michael Reid cho thấy 39 bước là đủ. Tháng 5/ 1992 18 37 19 Dik Winter đã hạ thấp xuống còn 37 bước chỉ đúng một ngày sau đó. Tháng 1/ 1995 18 29 11 Michael Reid giảm giới hạn trên xuống còn 29 bước bằng cách phân tích công thức hai pha của Kociemba. Tháng 1/ 1995 20 29 9 Michael Reid tìm ra Super-Flip. Tháng 12/ 2005 20 28 8 Silviu Radu cho thấy 28 bước là đủ. Tháng 4/ 2006 20 27 7 Silviu Radu thay đổi kết quả của mình xuống còn 27 bước. Tháng 5/ 2007 20 26 6 Dan Kunkle và Gene Cooperman chứng minh 26 bước là đủ. Tháng 3/ 2008 20 25 5 Tomas Rokicki hạ giới hạn trên thành 25 bước di chuyển. Tháng 4/ 2008 20 23 3 Tomas Rokicki and John Welborn giảm xuống còn 23 bước. Tháng 8/ 2008 20 22 2 Tomas Rokicki and John Welborn tiếp tục giảm còn 22 bước. Tháng 7/ 2010 20 20 0 Tomas Rokicki, Herbert Kociemba, Morley Davidson và John Dethridge cuối cùng đã chứng minh được God’s Number chính xác là 20 bước với độ lệch bằng 0.
(Nguồn: cube20.org)
Bảng tổng hợp số trạng thái Scramble
Bảng dưới đây tổng hợp lại “khoảng cách” và số trạng thái có thể có trong mỗi trường hợp. “Khoảng cách” là số bước đi tối thiểu để giải khối Rubik, số trạng thái là tổng cộng tất cả trường hợp Scramble ứng với mỗi “khoảng cách”.
Ví dụ với “khoảng cách” là 0, chỉ có một trạng thái duy nhất là khối Rubik đã full 6 mặt. Đối với “khoảng cách” từ 15 trở lên, con số đưa ra chỉ là ước tính.
Khoảng cách Số trạng thái 0 1 1 18 2 243 3 3,240 4 43,239 5 574,908 6 7,618,438 7 100,803,036 8 1,332,343,288 9 17,596,479,795 10 232,248,063,316 11 3,063,288,809,012 12 40,374,425,656,248 13 531,653,418,284,628 14 6,989,320,578,825,358 15 91,365,146,187,124,313 16 khoảng 1,100,000,000,000,000,000 17 khoảng 12,000,000,000,000,000,000 18 khoảng 29,000,000,000,000,000,000 19 khoảng 1,500,000,000,000,000,000 20 khoảng 490,000,000
(Nguồn: cube20.org)
The Devil’s Algorithm – Công thức của quỷ
Như đã nói ở trên, chúng ta sẽ cùng bàn về công thức có thể áp dụng được nhiều lần, có thể giải một khối Rubik ở bất kỳ trạng thái nào. Devil’s Algrithm là công thức ngắn nhất để có thể làm được điều này, còn Devil’s Number là số bước ngắn nhất cho công thức của quỷ.
Rõ ràng, có một công thức dùng chung cho tất cả 43 tỷ tỷ trạng thái có thể có của khối lập phương rubik. Các nhà khoa học đã chứng minh được điều này nhưng họ không thể tìm được và gán cho nó cái tên “Công thức của quỷ”. Có thì có nhưng vấn đề là nó sẽ rất dài. Tìm Devil’s Algorithm khó hơn nhiều so với tìm giải pháp tối ưu. Thực tế là chúng ta vẫn chưa biết được Công thức của quỷ cho khối 2x2x2, mặc dù nó có ít trạng thái nhất. Vì vậy, đừng mong đợi điều này sẽ sớm được tìm thấy cho khối Rubik’s Cube tiêu chuẩn.
Vậy là chúng ta đã hiểu thêm phần nào về God’s Number cũng như Devil’s Algorithm. Những thứ này đã khiến các nhà nghiên cứu mất hơn 3 thập kỷ, sử dụng cả toán học phức tạp lẫn siêu máy tính chỉ để tìm được lời giải về chiếc Rubik nhỏ bé. Có lẽ trong chúng ta, chẳng có Cuber nào tận tụy được như họ. Nhưng mỗi người lại có một thú vui riêng phải không? Hàng ngày được quay Rubik tít mù là đã tốt lắm rồi.
Tôi là Nguyễn Văn Sỹ có 15 năm kinh nghiệm trong lĩnh vực thiết kế, thi công đồ nội thất; với niềm đam mê và yêu nghề tôi đã tạo ra những thiết kếtuyệt vời trong phòng khách, phòng bếp, phòng ngủ, sân vườn… Ngoài ra với khả năng nghiên cứu, tìm tòi học hỏi các kiến thức đời sống xã hội và sự kiện, tôi đã đưa ra những kiến thức bổ ích tại website nhaxinhplaza.vn. Hy vọng những kiến thức mà tôi chia sẻ này sẽ giúp ích cho bạn!