PDA

View Full Version : Giải bài toán Rubik trong vài giây nhờ lý thuyết nhóm



thomasblack
12-07-2008, 09:32 PM
Khối màu Rubik hẳn đã trở lên quen thuộc với mọi người, một số cảm thấy hứng thú khi có thể sắp xếp được mặt màu mà mình muốn, số còn lại thì cảm thấy chán nản vì phải ngồi hàng giờ loay hoay mà vẫn không tạo ra mặt màu nào. Dường như không có cách nào có thể sắp màu xanh về một mặt mà lại không rải rác các màu đỏ và màu vàng ở khắp nơi, không theo trật tự nào cả.

Trên tuần báo " Nine o'clock" có đăng tin một cậu sinh viên có thể sắp xếp khối hình Rubik sau 20 giây, đúng là sinh viên thời nay sáng dạ hơn. Chúng ta chấp nhận kết quả này nhưng không mất sự tự tin. Chúng ta có thể trách họ vì sử dụng thời gian cho công việc vô bổ, thay vào đó có thể dùng cho các trò chơi giải trí khác. Nhưng có một suy nghĩa đâu đó trong đầu chúng ta : Họ làm thế nào vậy ? Và một cậu bé 3 tuổi người Hoa, vẫn còn ngồi trên ghế em bé, đã chỉ cho chúng tôi cách sắp xếp màu Rubik bằng những ngón tay nhỏ xíu và mềm mại, làm chúng ta càng phải suy nghĩ hơn: chắc phải có một hệ thống nào đó. Và...phương pháp giải chính là lý thuyết nhóm

http://images.smarter.com/blogs/rubiks-cube.jpg

Rubik chứa một con quay ở đó cho phép toàn bộ các khối màu nhỏ có thể di chuyển xung quanh các mặt ngoài. Giống như bao khối lập phương khác, Rubik có sáu mặt ngoài được tô các màu giống nhau trên một mặt và khác nhau giữa các mặt kề. Có tất cả http://www.diendantoanhoc.org/cgi-bin/mimetex.cgi?%5Clarge%20%203%20%5Ctimes%203%20%5Cti mes%203%20=%2027khối lập phương nhỏ, trong đó 7 khối thuộc phần cố định của con quay và 20 khối có thể di chuyển xung quanh. 20 khối di chuyển này được chia vào 8 khối góc và 12 khối cạnh. Mỗi khối góc có 3 mặt lộ, trong khi mỗi khối cạnh có hai mặt nhìn thấy. Khối hình có tính đối xứng khi chiếu các góc với các góc, các cạnh với cách cạnh. Có tất cả 8! chỉnh hợp góc và 12! chỉnh hợp cạnh. Mỗi góc lại có ba mặt, do đó tăng số lượng khả năng sắp xếp lên 28 lần, tương tự với 2 mặt khả năng của các cạnh. Do có dự lặp lại giữa các cấu hình, nên chúng ta cần phải chia cho 12, như vậy tất cả sẽ có http://www.diendantoanhoc.org/cgi-bin/mimetex.cgi?%5Clarge%20%5Cfrac%7B1%7D%7B12%7D%20%5 Ctimes%208%21%203%5E8%2012%21%202%5E%7B12%7D=%2043 %20%5C%20252%20%5C%20003%20%5C%20274%20%5C%20%2028 9%5C%20%20856%20%5C%20000 đối xứng hợp lệ cho khối Rubik. Những đối xứng này hình thành lên một nhóm gọi là nhóm Rubik. Dựa trên Phân loại hóa của các nhóm đơn giới hạn ( Classification of Finite Simple Groups), nhóm Rubik hoàn toàn không đơn giản, nhưng lại được tạo lên bởi các nhóm đơn http://www.diendantoanhoc.org/cgi-bin/mimetex.cgi?%5Clarge%20%20A_%7B12%7D, http://www.diendantoanhoc.org/cgi-bin/mimetex.cgi?%5Clarge%20A_8 , 7 phiên bản sao chép của http://www.diendantoanhoc.org/cgi-bin/mimetex.cgi?%5Clarge%20Z_3 và 12 phiên bản sao chép của http://www.diendantoanhoc.org/cgi-bin/mimetex.cgi?%5Clarge%20%20Z_2.

Chìa khóa để tìm ra lời giải nhanh cho khối Rubik đó là hiểu biết về các nhóm con trong nhóm Rubik. Một bước quay thay đổi 20 trong số 48 trường có thể di chuyển và cố định 28 trường còn lại. Kết hợp nhiều bước quay theo một cách sáng suốt sẽ tăng số lượng của các trường cố định. Đó chính là kỹ năng của các nhà sếp hình Rubik. Họ biết và nhớ các chuỗi quay và cố định một lượng lớn các trường, và sử dụng các chuổi này để thay đổi nhiều, nhiều hơn các trường vào đúng vị trí, mà không ảnh hưởng đến các khối đã nằm đúng chỗ. Từ cái nhìn của lý thuyết nhóm, công việc trên không có gì là phức tạp, xong việc nhớ các chuỗi di chuyển và hoàn thành chúng lại là một chuyện khác. Khối Rubik không chỉ là một ví dụ điển hình của việc sử dụng lý thuyết nhóm, mà nó còn là một minh chứng cho sự thật, giải trên lý thuyết là một chuyện, nhưng áp dụng vào thực tiễn lại là một chuyện khác.

Nguồn: abelprisen.no

kieuphong
13-07-2008, 12:28 AM
Cái này hình như ngogiuoc cũng nói 1 lần rồi, đọc chả hiểu cái khỉ gì, mình vốn dốt toán, thi xác suất đc có 5 điểm, hix hix

ngogiuoc
16-07-2008, 06:47 PM
cái này là một cơ sở đề tính toán nhưng lại không hẳn liên quan đến phường pháp có thể giải nhanh thực sự, cái 20 trong 48 chỉ là cơ sở đề tính và đi tìm chu kỳ.
thực sự thì bài toán rubik là một bài toán rất khó, liên quan đến rất nhiều vấn đề toán học như tổ hợp, xáv xuất thống kê, chu kì v.v..., hiện giờ 3x3 người ta còn chưa kaa1m phá hết thì kô biết bào giờ mới tính được trường hợp nxn hay các loại cube khác

nanotek2711
10-12-2008, 09:33 PM
http://diendantoanhoc.net/home/index.php?option=com_content&view=article&catid=64:toan-hc-va-i-sng&id=55:gii-bai-toan-khi-rubik-trong-vai-giay-s-dng-ly-thuyt-nhom&Itemid=80 cái này mình đọc ở đây nè :D

pirates00
10-12-2008, 10:11 PM
Vấn đề đặt ra là nhận ra dạng của nó trong vòng 15s :P nhận ra được dạng của nó rất khó vì phải đặt nó trong 44 tỷ tỷ vị trí khác nhau.
Hồi đó em với ga_fi_tiu qua bên forum 5s để quảng cáo, gửi cho ông kia cái video kỉ lục thế giới 7s08, em nói là người này dùng cách của Fridrich và skip phần PLL, ổng coi xong 1 hồi ổng nói người này chắc chắn phải sử dụng cách nhớ nhiều trường hợp mới có thể làm nhanh thế được (tức là cách làm lý thuyết nhóm), sau đó giải thích nào là khi xong layer 1 thì tổng số trường hợp là bao nhiêu, xong layer 2 tổng số trường hợp là bao nhiêu, em bắt bẻ ngay 1 cái là trong vòng 15s có thể nhận ra được dạng của nó trong 44 tỷ tỷ vị trí hay không, hay làm xong 1 hay 2 layer mất thời gian là bao nhiêu, thời gian còn lại có đủ để nhận diện để làm hay không -> mất tích luôn từ đó :D

lacthan77
13-12-2008, 05:14 PM
Rối bời, càng đọc càng rối bời!
tại sao chúng ta không làm cho các cách đó đơn giản hơn mà mà càng ngày càng phức tạp thế:shy:

UMU
13-12-2008, 11:45 PM
xếp hình rubik thành dạng mà đề bài cho trước chứ không phải chỉ lắp thành 6 mặt đơn thuần thì mới cần đến lý thuyết ấy, chứ 6 mặt 20s chắc nhiều pro trên 4rum đạt dc rồi :rolleyes: