On 12.02.2016 17:22, J.F. wrote:
> Użytkownik "platformowe głupki" napisał w wiadomości grup
> dyskusyjnych:n9ku3m$m9j$...@n...news.atman.pl...
>> niepojęte, dowolnie poskręcaną kostkę można ułożyć w 20(40) ruchów?
>> niepojęte...
>
> To dziala tak - liczymy ilosc mozliwych ułozen/stanow kostki.
> Wychodzi nam liczba dosc duza, ale przeciez skonczona, oznaczmy ja przez S.
>
> Teraz rozwazmy jeden ruch - cwierc obrotu jednej sciany.
> Mamy 12 do wyboru - 6 scian, dwie strony.
> Czyli w jednym ruchu mozemy zmienic stan na jeden z 12 innych.
>
> W dwoch ruchach mamy juz 12*12 = 144 mozliwosc.
> No - troche mniej, bo drugi ruch moze skasowac pierwszy i wrocimy do
> stanu wyjsciowego.
> Ale takimi drobiazgami sie na razie nie zajmujemy.
>
> Po n ruchach mamy wiec kostke w jednym zgrubsza liczacz z 12^n stanow.
>
> No i jesli mnie pamiec nie myli, to 12^21 > S.
> Moze myli, i wykladniku jest np 23, ale tego rzedu liczba to jest. Nawet
> nie 30.

>
> Dalsze mieszanie teoretycznie nic nie daje, bo nie mozemy osiagnac
> wiecej niz S stanow.
>
> Czy nalezy wiec przyjac, ze kazda kostke da sie ulozyc w co najwyzej 21
> ruchach ?
> No ... na pierwsza mysl to niekoniecznie - moga byc uklady, ktore
> wymagaja dluzszej sekwencji, kosztem tego, ze inne wymagaja krotszej,
> czy powtarzaja sie czesto w czasie roznych sekwencji.
>
> Na to sie bodajze pojawilo sporo publikacji matematykow, tym niemniej
> nawet bez ich czytania jakis szacunek mamy - kostke powinno dac sie
> ulozyc w okolo 21 czy tam z niewielkim zapasem 25 ruchow.


Jak sam zauważyłeś, nie jest to żaden szacunek, bo bez trudu można
skonstruować obiekt, który ma 2 możliwe ruchu, a odległość pomiędzy
punktami jest znacznie większa niż log2(ilość_stanów).

Algebraiczne podejśćie dawało znacznie szerszy zakres. 19-30 czy coś
takiego.
Ostateczny wynik zrobiono w połowe btruteforcem na serwrach googla;-)

How We Did It

How did we solve all 43,252,003,274,489,856,000 positions of the Cube?
We partitioned the positions into 2,217,093,120 sets of 19,508,428,800
positions each.
We reduced the count of sets we needed to solve to 55,882,296 using
symmetry and set covering.
We did not find optimal solutions to each position, but instead only
solutions of length 20 or less.
We wrote a program that solved a single set in about 20 seconds.
We used about 35 CPU years to find solutions to all of the positions in
each of the 55,882,296 sets

http://www.cube20.org/

pzdr
bartekltg