Mất 36 năm mới tìm ra 20 bước giúp giải được bất kỳ khối rubik nào

52
5.229

Cha đẻ của khối rubik, ông Ernő Rubik phải mất một tháng để tự giải được thử thách mình tạo ra.

Năm 1974, ngoài việc Stephen Hawking dự đoán trước sự tồn tại của bức xạ Hawking, khoa học xác định được vị trí của hố đen siêu lớn Sagittarius A nằm giữa Dải Ngân hà, 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:

Giáo sư kiến trúc và thiết kế người Hungary, ông Ernő Rubik phát minh ra thứ đồ chơi đi trước thời đại, một khối rubik.

Ernő Rubik - người phát minh ra rubik.

Nó là một khối lập phương, ghép lại từ 27 khối lập phương nhỏ hơn, diện tích 3x3x3 với mặt khối lập phương nhỏ mang màu khác nhau. Bạn có thể xoay khối rubik thế nào tùy thích, để đưa các khối lập phương nhỏ tới bất kỳ mặt nào. Cách chơi cũng đơn giản thôi: đối diện với một khối rubik ở trong trạng thái scrambled (tạm dịch là đảo lộn) , mỗi mặt có đủ thứ màu, bạn phải xoay khối lập phương sao cho mỗi mặt 3x3 của nó có cùng màu.

Kể từ ngày đó, người chơi đã sinh ra rất nhiều cách giải và chiến thuật khác nhau để chơi thành công khối rubik. Những “cuber” (biệt danh của người chơi rubik) với những đầu ngón tay giải đố thành thạo có thể hoàn thành một khối rubik chỉ trong vài giây. Kỷ lục thế giới hiện tại là 3,47 giây.

Những cách đảo khối rubik mang bản chất biến hóa khôn lường, mỗi cách giải một khác đã làm các nhà toán học mê đắm. Khối rubik với mỗi lần xoay khác nhau lại ra những câu đố khác hợp với toán học vô cùng, như lá chanh với thịt gà vậy.

Rubik
Rubik là một khối lập phương, ghép lại từ 27 khối lập phương nhỏ hơn, diện tích 3x3x3 với mặt khối lập phương nhỏ mang màu khác nhau.

Một khối rubik bình thường sẽ có các mặt 3x3 hiển thị một màu duy nhất, câu đố bắt đầu khi ta trộn các mặt lại với nhau, để tạo ra một khối màu sặc sỡ. Có tổng cộng 18 nước đi cơ bản, xoay một mặt ra phía trước, về phía sau, sang trái, sang phải rồi thuận chiều kim đồng hồ, ngược chiều kim đồng hồ hay xoay 180 độ. Có thể thấy quá trình giải khối rubik, dù ở bất kỳ trạng thái nào, đều là 18 bước trên được sắp xếp theo thứ tự khác nhau.

Câu hỏi triệu đô đặt ra cho cộng đồng các cuber đây: số nước đi nhỏ nhất để hóa giải một khối rubik là gì? Và một câu hỏi xa hơn, số nước đi nhỏ nhất để hóa 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 vẫn được những người chơi rubik gọi là God’s Number - con số Thần thánh.

Như Ernő Rubik đã chỉ ra trong một bài phỏng vấn với Business Insider, câu hỏi lớn này “liên quan chặt chẽ tới những vấn đề toán học xoay quanh khối rubik”.

Cuối cùng toán học cũng tìm ra câu trả lời: đó là 20 nước đi. Nhưng phải mất 36 năm nghiên cứu, các nhà toán học và lập trình viên mới tìm ra được câu tra lời cuối cùng. Vào năm 2010, một nhóm các nhà toán học và nhà lập trình máy tính chứng minh rằng 20 chính là con số Thần thánh.

Tại sao mất nhiều năm thế? Bởi bản thân khối rubik quá phức tạp, phức tạp hơn bạn tưởng nhiều. Phân tích cho thấy số lượng câu đố ẩn trong khối lập phương sặc sỡ kia, số lượng cách sắp xếp trật tự của các mảng màu trên khối rubik, là 43.000.000.000.000.000.000 cách - 43 tỷ tỷ cách.

Những năm tiếp nối 1974, công nghệ chưa đủ hiện đại để tìm ra phương pháp giải cần ít nước đi nhất cho toàn bộ 43 tỷ tỷ câu đố. Chìa khóa quan trọng nhất trong chuyến hành trình đó là tìm ra được số nước nhỏ nhất để giải thành công một trạng thái đảo lộn bất kỳ. Có được con số đó, các nhà toán học sẽ lợi dụng được mối liên hệ giữa các trạng thái đảo lộn khác nhau.

Năm 1995, nhà toán học Michael Reid tìm ra được trạng thái đảo lộn có tên là “siêu lật - superflip”, ông chứng minh được rằng chỉ cần ít nhất 20 bước để giải được trạng thái superflip. Nhờ có ông Reid, ta đặt được giới hạn dưới cho con số Thần thánh. Câu hỏi còn lại là liệu có những trạng thái đảo lộn nào cần hơn 20 bước để giải không?

Quá trình giải khối rubik, dù ở bất kỳ trạng thái nào, đều là 18 bước trên được sắp xếp theo thứ tự khác nhau.

Trong những thập kỷ tiếp theo, liên tục xuất hiện những giới hạn trên của số bước cần có để giải một khối rubik. Một trong những phân tích toán học đầu tiên về khối rubik, được thực hiện bởi Morwen Thistlethwaite, chứng minh được rằng: giải bất kỳ khối rubik nào cũng chỉ cần tối đa 52 bước.

Lập trình viên Tomas Rokicki dựng nên một bản phân tích tìm ra những cách giải ngắn nhất cho một khối rubik, dựa trên một trong những nghiên cứu toán học đầu tiên liên quan tới khối lập phương sặc sỡ kia, nghiên cứu của Herbert Kociemba. Nhà toán học đã chia quá trình giải khối rubik ra làm hai phần, dựa trên tổ hợp 19,5 tỷ khối rubik đã được giải một phần. Tất cả các trạng thái đảo lộn trong tổ hợp 19,5 tỷ kia đều có số bước giải khá ít.

Bước một sẽ là đưa khối rubik về một trong 19,5 tỷ trạng thái kia. Bước thứ hai mới là áp dụng cách giải.

Những dự án giải rubik cũ đều cho thấy số bước thực hiện tối đa là 30, cho bất kỳ cách đảo lộn rubik nào. Trong số đó, việc giải chỉ cần tối đa 18 bước, việc đưa rubik vào trạng thái đặc biệt để giải thì mất 12 bước.

Anh Rokicki cải tiến phương pháp giải trên bằng cách gộp 19,5 tỷ tổ hợp kia thành một tổ hợp đặc biệt, rồi tìm cách giải một lúc toàn bộ 19,5 tỷ cách đảo lộn rubik đó. Vậy là tổng cộng, họ “chỉ” phải giải 2.217.093.120 tổ hợp mà mỗi tổ hợp, có “mỗi” 19.508.428.800 cách đảo khối rubik.

Thế nên chỉ cần giải 2,2 tỷ lần, chứ không cần thực hiện tất cả 43 tỷ tỷ cách đảo lộn. Phương pháp này vẫn cần một siêu máy tính cực mạnh, nhưng công nghệ cuối cùng cũng đã bắt kịp với nhu cầu giải toán của con người. Năm 2010, Rokicki và các đồng nghiệp đã sử dụng siêu máy tính của Google để tìm ra con số Thần thánh, ta có được kết quả 20.

Các nhà nghiên cứu mất hơn 3 thập kỷ, sử dụng cả toán học sâu xa lẫn siêu máy tính để giải được câu đố rubik; chẳng cuber “bình dân” nào tận tụy được như họ cả. Nhưng mỗi người lại có những điều kiện khác nhau để cho mình thú vui riêng mà. Có lẽ với “người thường” chúng ta, xoay tít mù khối rubik trên tay cũng đã là niềm vui rồi.

Cập nhật: 23/04/2019 Theo Trí Thức Trẻ