Matematyka kostki Rubika

W 2010 roku międzynarodowy zespół badaczy udowodnił, że bez względu na to, jak pomieszana jest kostka Rubika, jej ułożenie wymaga nie więcej niż 20 ruchów. Ich dowód opierał się jednak na równowartości 35 lat obliczeń liczbowych na dobrym, nowoczesnym komputerze.

W przypadku kostek większych niż standardowa kostka Rubika, odpowiednie rozpoznanie pozycji startowych może znacznie wykraczać poza możliwości obliczeniowe wszystkich komputerów na świecie. Jednak we wrześniu Erik Demaine (po prawej), docent informatyki i inżynierii, kierował zespołem, w skład którego wchodził jego ojciec, profesor wizytujący CSAIL Martin Demaine (po lewej), który zademonstrował matematyczny związek między liczbą kwadratów w sześcianie a liczba ruchów w najkrótszym rozwiązaniu do najbardziej pomieszanego stanu.

Standardowym sposobem ułożenia kostki Rubika jest znalezienie kwadratu, który nie jest na swoim miejscu i przeniesienie go na miejsce, pozostawiając resztę kostki jak najmniej zmienioną, jak to możliwe. Daje to najgorsze rozwiązanie, którego liczba ruchów jest proporcjonalna do N2, gdzie N jest liczbą kwadratów w rzędzie. Zespół zauważył jednak, że w pewnych okolicznościach pojedyncza sekwencja zwrotów akcji może przenieść wiele kwadratów na miejsce.

Matematyczne opisanie tych okoliczności nie było łatwym zadaniem. W pierwszej godzinie zobaczyliśmy, że musi to być co najmniej N2/log N, mówi Erik Demaine. Ale potem minęło wiele miesięcy, zanim mogliśmy udowodnić, że N2/log N to wystarczająca liczba ruchów.

ukryć