Luôn luôn có một cái gì đó mới khi tìm hiểu và khám phá về nó, càng nghiên cứu và điều tra sâu tất cả 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ẽ rằng, bí hiểm lớn nhất trong toàn bộ mọi bí hiểm 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ự kiến trước được sự sống sót của bức xạ, lần tiên phong nước Mỹ sử dụng mã vạch để bán hàng, thì quả đât còn tận mắt chứng kiến một sự kiện đặc biệt quan trọng khác : khối Rubik được sinh ra bởi nhà giáo sư kiến trúc người Hungary – ông Erno Rubik .
Món đồ chơi Rubik 3×3 gồm có 6 mặt như tất cả 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ú vị. 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ố ít người thường lầm tưởng rằng God’s Number là một công thức toàn năng hoàn toàn 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, tất cả chúng ta đang nói về SỐ BƯỚC vận động và di chuyển tối thiểu để giải ( Fewest Move ). Tôi đã có một mục dành riêng để bàn về yếu tố 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 số 43.252.003.274.489.856.000 trạng thái khác nhau. Và phải mất đến 36 năm điều tra và nghiên cứu, các nhà khoa học mới tìm ra được câu vấn đáp 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 hoàn toàn 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 tập sự .
Trạng thái Super-Flip
Có lẽ nổi tiếng nhất trong số các Scramble ( trộn lẫn ) khan hiếm cần đúng chuẩn 20 bước chuyển dời 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).
Xem thêm: Hướng dẫn cách giải Rubik 4×4 cơ bản
Bạn có nhận ra sự đặc biệt quan trọng của Scramble này không ? Trong khi mọi góc đều được giữ nguyên vị trí thì toàn bộ các cạnh đều bị lật ngược lại. Đây cũng là trạng thái tiên phong được chứng tỏ là chỉ cần mất 20 bước xoay, nâng số lượ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 khởi đầ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 This tlewaite chứng tỏ bằng các thuật toán phức tạp. Đầu tiên, anh đã chỉ ra rằng 52 bước là đủ để xử lý mọi trạng thái nào của khối Rubik. Và số lượng này giảm dần qua từng năm nhờ các chiêu thức mới hiệu suất cao hơn, tốt hơn .
Bảng này sẽ tóm tắt sự đổi khác của God’s Number qua từng thời kỳ, gồm có : số lượng giới hạn trên, số lượng 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 hoàn toàn có thể có trong mỗi trường hợp. “ Khoảng cách ” là số bước tiến tối thiểu để giải khối Rubik, số trạng thái là tổng số toàn bộ 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, số lượng đư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, tất cả chúng ta sẽ cùng bàn về công thức hoàn toàn có thể vận dụng được nhiều lần, hoàn toà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 để hoàn toàn 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.
Kết luận
Vậy là tất cả 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 tất cả 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 nụ cười riêng phải không ? Hàng ngày được quay Rubik tít mù là đã tốt lắm rồi .
Source: https://vietsofa.vn
Category : Góc học tập
+ There are no comments
Add yours