Kostka rubika - łamigłówka :)

[zażółcony]

Dla tych, co kostkę układali, takie ciekawe zadanko:

1. Bierzemy kostkę Rubika
2. Rozkręcamy ją (rozpada się na
pojedyncze klocki - 8 narożników, 12 klocków krawędziowych + trwały
szkielecik klocków środkowych)
3. Wszystko dokładnie mieszamy
4. Składamy kostkę z powrotem 'z zawiązanymi oczami', czyli nie zwracamy
uwagi na kolory.
5. Powstałą kostkę w stanie 'pomieszania' staramy się ułożyć dowolną znaną
nam techniką (byleby skuteczną i 'legalną', nie wymagającą rozkładania
kostki ;)

Jakie jest prawdopodobieństwo, że kostkę w ogóle da się ułożyć ?

Mi wychodzi z obliczeń, że prawdopodobieństwo wynosi 1/12.
czyli tylko jedna z 12 kostek będzie tradycyjną kostką robija, a 11
będzie w jakiś sposób 'uszkodzona' i niemożliwa do ułożenia.

[Maciek]

Post by zażółcony
1. Bierzemy kostkę Rubika
2. Rozkręcamy ją (.....)
4. Składamy kostkę z powrotem 'z zawiązanymi oczami', (....)
Jakie jest prawdopodobieństwo, że kostkę w ogóle da się ułożyć ?
Mi wychodzi z obliczeń, że prawdopodobieństwo wynosi 1/12.
czyli tylko jedna z 12 kostek będzie tradycyjną kostką robija, a 11
będzie w jakiś sposób 'uszkodzona' i niemożliwa do ułożenia.

Zgadza się.

Maciek

[zażółcony]

Post by Maciek

Post by zażółcony
1. Bierzemy kostkę Rubika
2. Rozkręcamy ją (.....)
4. Składamy kostkę z powrotem 'z zawiązanymi oczami', (....)
Jakie jest prawdopodobieństwo, że kostkę w ogóle da się ułożyć ?
Mi wychodzi z obliczeń, że prawdopodobieństwo wynosi 1/12.
czyli tylko jedna z 12 kostek będzie tradycyjną kostką robija, a 11
będzie w jakiś sposób 'uszkodzona' i niemożliwa do ułożenia.

Zgadza się.

Sprawdzone empirycznie ? :)))

Ja to liczyłem tak: błędy, jakie mogą powstać w kostce, których
nie da się już poprawić, są następujące:
1. Przekręcenie jednego z narożników - prawdopodobieństwo ułożenia
poprawnego wynosi 1/3
2. Odwrócenie jednego z klocków krawędziowych - prawdopodobieństwo 1/2
3. Zamiana dwóch narożników lub dwóch klocków krawędziowych miejscami,
przy czym jest to ten sam błąd - można jeden z nich zamieniać na drugi
odpowiednimi sekwencjami
ruchów - prawdopodobieństwo znów 1/2

Razem 1/3 * 1/2 * 1/2 = 1/12. Zrozumienie tego wymaga trochę obeznania
z samym układaniem.
Może jest jakiś inny dowód, mniej 'umoczony' w empiryczne eksperymenty ?

[Maciek]

Post by zażółcony

Post by Maciek

Post by zażółcony
1. Bierzemy kostkę Rubika
2. Rozkręcamy ją (.....)
4. Składamy kostkę z powrotem 'z zawiązanymi oczami', (....)
Jakie jest prawdopodobieństwo, że kostkę w ogóle da się ułożyć ?
Mi wychodzi z obliczeń, że prawdopodobieństwo wynosi 1/12.
czyli tylko jedna z 12 kostek będzie tradycyjną kostką robija, a 11
będzie w jakiś sposób 'uszkodzona' i niemożliwa do ułożenia.

Zgadza się.

Sprawdzone empirycznie ? :)))

Nie, rachunkowo.

Post by zażółcony
Ja to liczyłem tak: błędy, jakie mogą powstać w kostce, których
1. Przekręcenie jednego z narożników - prawdopodobieństwo ułożenia
poprawnego wynosi 1/3
2. Odwrócenie jednego z klocków krawędziowych - prawdopodobieństwo 1/2
3. Zamiana dwóch narożników lub dwóch klocków krawędziowych miejscami,
przy czym jest to ten sam błąd - można jeden z nich zamieniać na drugi
odpowiednimi sekwencjami ruchów - prawdopodobieństwo znów 1/2
Razem 1/3 * 1/2 * 1/2 = 1/12. Zrozumienie tego wymaga trochę obeznania
z samym układaniem.
Może jest jakiś inny dowód, mniej 'umoczony' w empiryczne eksperymenty ?

Tak, to samo można pokazać algebraicznie na własnościach
permutacji kostki. Ale wymaga dużo (naprawdę DUŻO) więcej
pisania, i najlepiej jeszcze obrazków, których na pewno
nie zrobię w ASCII-art. :)


Maciek

[Aleksander Nabagło]

!

Post by zażółcony
1. Przekręcenie jednego z narożników - prawdopodobieństwo ułożenia
poprawnego wynosi 1/3
2. Odwrócenie jednego z klocków krawędziowych - prawdopodobieństwo 1/2
3. Zamiana dwóch narożników lub dwóch klocków krawędziowych miejscami,
przy czym jest to ten sam błąd - można jeden z nich zamieniać na drugi
odpowiednimi sekwencjami
ruchów - prawdopodobieństwo znów 1/2
Razem 1/3 * 1/2 * 1/2 = 1/12. Zrozumienie tego wymaga trochę obeznania
z samym układaniem.
Może jest jakiś inny dowód, mniej 'umoczony' w empiryczne eksperymenty ?

Przed laty byl na ten temat artykul w "Scientific American".
Narozniki zachowuja sie jak hadrony (trzy widoczne boki == trzy kwarki)
natomist krawedzie, jak mezony (dwa widoczne boki == dwa kwarki).

[J.F.]

Post by zażółcony
Ja to liczyłem tak: błędy, jakie mogą powstać w kostce, których
3. Zamiana dwóch narożników lub dwóch klocków krawędziowych miejscami,
przy czym jest to ten sam błąd - można jeden z nich zamieniać na drugi
odpowiednimi sekwencjami ruchów - prawdopodobieństwo znów 1/2

Hm, pobawilem sie kostka i cos mi sie nie zgadza. Tylko ostatnia
warstwa ruszana - tzn ruszane wszystkie, ale po kombinacji ruchow dwie
warstwy bez zmian.

zamiana dwoch sasiednich "krawedziakow" kombinacja ruchow powoduje tez
zamiane dwoch sasiednich naroznikow.
Dowolnie ktorej pary sasiednich naroznikow.

W tym stanie zamieniamy nastepne dwa sasiednie krawedziaki. Co moze
doprowadzic do przywrocenia porzadku w naroznikach.

Tymczasem co widze - zamienione dwa przeciwne krawedziaki .. i dwa
sasiednie narozniki.

Czyli porzadek wyglada powiedzmy:
ABC
HxD
GFE
a jest
AFC
HxD
EBG

niby nadal dwa krawedziaki zamienione, to i dwa narozniki zamienione -
ale troche mnie zastanawia - czemu mi sie nie udalo przywrocic
porzadku w naroznikach ? Czyzby cos jeszcze wiazalo te uklady ?
To moze jest wiecej klas ukladow "niemozliwych" niz tylko jedna ?
(i druga "mozliwa").

Czyli co - srubokret w dlon i metode MC ?

J.

[zażółcony]

Post by J.F.
zamiana dwoch sasiednich "krawedziakow" kombinacja ruchow powoduje tez
zamiane dwoch sasiednich naroznikow.
Dowolnie ktorej pary sasiednich naroznikow.

Tu jest coś nie tak. Nie ma 'dowolnie'. Wtedy miałbyś rzeczywiście
niezależność ruchów zamieniajacych 2 krawędziaki od ruchów zamieniajacych
2 narożniki. A takiej niezależności nie ma.

Post by J.F.
W tym stanie zamieniamy nastepne dwa sasiednie krawedziaki. Co moze
doprowadzic do przywrocenia porzadku w naroznikach.

No nie może, jak widać, tych samych przywrócić ;)

Post by J.F.
niby nadal dwa krawedziaki zamienione, to i dwa narozniki zamienione -
ale troche mnie zastanawia - czemu mi sie nie udalo przywrocic
porzadku w naroznikach ? Czyzby cos jeszcze wiazalo te uklady ?
To moze jest wiecej klas ukladow "niemozliwych" niz tylko jedna ?
(i druga "mozliwa").

Hmmm... Więc wychodzi na to, że skoro nie ma tu dowolności, to
moje rozumowanie było zbyt skrócone.

Czyli, że: w poprawnym układzie zamieniamy dwa krawędziaki,
potem dwa narożniki - i otrzymujemy układ niemożliwy do naprawienia ...
Hmmm ...
Musze pomyśleć nad tym fantem ...

Post by J.F.
Czyli co - srubokret w dlon i metode MC ?

Da radę bez ;) Mocno używana kostka już śrubokręta
nie potrzebuje ;)

[J.F.]

wiadomości

Post by J.F.
zamiana dwoch sasiednich "krawedziakow" kombinacja ruchow
powoduje tez
zamiane dwoch sasiednich naroznikow.
Dowolnie ktorej pary sasiednich naroznikow.

Tu jest coś nie tak. Nie ma 'dowolnie'. Wtedy miałbyś
rzeczywiście
niezależność ruchów zamieniajacych 2 krawędziaki od ruchów zamieniajacych
2 narożniki. A takiej niezależności nie ma.

Dowolnie. Tzn pozniejsza sekwencja "przestaw 3 narozniki"
doprowadza do zamienionych dowolnych dwoch naroznikow, nie
zmieniajac krawedziakow.

Post by J.F.
W tym stanie zamieniamy nastepne dwa sasiednie krawedziaki. Co moze
doprowadzic do przywrocenia porzadku w naroznikach.

No nie może, jak widać, tych samych przywrócić ;)

Bede to musial jeszcze na spokojnie przecwiczyc, ale to za pare dni
niestety :-(

J.

[zażółcony]

Dowolnie. Tzn pozniejsza sekwencja "przestaw 3 narozniki" doprowadza do
zamienionych dowolnych dwoch naroznikow, nie zmieniajac krawedziakow.

eee ... Coś tu chyba zamieszałeś :) Te narożniki po drodze muszą
się 'obkręcać', nie da się ich tak po prostu zamieniać.

[J.F.]

Post by zażółcony

Dowolnie. Tzn pozniejsza sekwencja "przestaw 3 narozniki" doprowadza do
zamienionych dowolnych dwoch naroznikow, nie zmieniajac krawedziakow.

eee ... Coś tu chyba zamieszałeś :) Te narożniki po drodze muszą
się 'obkręcać', nie da się ich tak po prostu zamieniać.

Same narozniki, uklad poczatkowy jest np taki:
AB
DC

zamieniamy dwa, razem z krawedziakami, wychodzi np
AB
CD

rotujemy trojke BDC, krawedziaki nie ruszone:
AC
DB

Czyli.. teraz zamienione sa CB w stosunku do oryginalu.
Rotujemy trojke ACB
BA
DC

kolejna rotacja:
DB
AC

A krawedziaki ciagle sa nieruszone - tzn jak zostaly zamienione w
pierwszym ruchu tak juz zostaly.

J.

[Mariusz Marszałkowski]

Post by J.F.
A krawedziaki ciagle sa nieruszone - tzn jak zostaly zamienione w
pierwszym ruchu tak juz zostaly.

Może zrobić eksperyment na kompie? przekręcić jeden narożnik o
120 stopni i przeszukać na 8-10 ruchów w głąb?
Pozdrawiam

[J.F.]

Post by Mariusz Marszałkowski

Post by J.F.
A krawedziaki ciagle sa nieruszone - tzn jak zostaly zamienione w
pierwszym ruchu tak juz zostaly.

Może zrobić eksperyment na kompie? przekręcić jeden narożnik o
120 stopni i przeszukać na 8-10 ruchów w głąb?

Przekrecic jeden naroznik to wiadomo co wyjdzie - nie da sie
naprostowac.
Podobnie jeden krawedziak.

Pytanie brzmi ile grup kombinacji ma ostatnia warstwa jesli chodzi
o rozmieszczenie klockow. A wrecz jeszcze licznosci tych grup -
bo od tego zalezy pr-stwo ulozenia po losowym zlozeniu.

J.

[J.F.]

Post by zażółcony

Dowolnie. Tzn pozniejsza sekwencja "przestaw 3 narozniki" doprowadza do
zamienionych dowolnych dwoch naroznikow, nie zmieniajac krawedziakow.

eee ... Coś tu chyba zamieszałeś :) Te narożniki po drodze muszą
się 'obkręcać', nie da się ich tak po prostu zamieniać.

No dobra, nakrecilem sie, nakrecilem i doszedlem do pewnych
wnioskow:-)

Sekwencja "przestaw 3" oznacza tez "zamien dwa".
Majac uklad np
AB
DC
po przestawieniu np BCD
AD
CB
cala czworke wystarczy obrocic
DB
AC
i mamy niby zamienione D z A

dotyczy zarowno krawedziakow, jak i naroznikow.

Istota zlego zlozenia jest wiec nie tyle zamiana dwoch elementow, co
przestawienie krawedziakow wzgledem naroznikow. Nie ma sekwencji
"przestaw 4 krawedziaki o 90 stopni nie ruszajac naroznikow".

Ale poniewaz mozna przestawic o 180 stopni, wiec takie przestawienie w
prawo jest rownowazne przestawieniu w lewo.

Czyli przychylam sie pierwotnego wniosku: 50% szans ze przy losowym
zlozeniu zamienimy dwa elementy. w calosci 1/12.

Teraz czas na potwierdzenie MC - kto chce partycypowac i rozlozy swoja
kostke kilka razy ? :-)

J.