ordine gruppo cubo di rubik

Analisi, algebra lineare, topologia, gruppi, anelli, campi, ...
Avatar utente
ficus2002
Messaggi: 60
Iscritto il: 10 feb 2006, 00:06

ordine gruppo cubo di rubik

Messaggio da ficus2002 »

Consideriamo il cubo di Rubik; qual'è l'ordine del gruppo generato dalle rotazioni delle sei facce?
MindFlyer

Messaggio da MindFlyer »

Ho trovato questa simpatica introduzione alla teoria dei gruppi che usa come strumento didattico il cubo di rubik:
http://www.geometer.org/rubik/group.pdf.

Non so se risponda alla tua domanda (l'ho guardato velocemente), ma sicuramente tocca argomenti molto vicini.
Avatar utente
ficus2002
Messaggi: 60
Iscritto il: 10 feb 2006, 00:06

Messaggio da ficus2002 »

grazie mille, molto interessante, ho trovato anche la risposta alla mia domanda :wink:
MindFlyer

Messaggio da MindFlyer »

Il capitolo 8 è dedicato all'ordine del gruppo delle posizioni raggiungibili del cubo di Rubik. In pratica vengono dimostrati 3 invarianti sulla parità delle permutazioni, sull'orientamento degli spigoli e sulla rotazione dei vertici, e da questo si ricava facilmente che l'ordine è un divisore di $ 8! \cdot 12! \cdot 2^{10} \cdot 3^7 $. Ma non viene dimostrato, a quanto abbia visto, che tutte quelle configurazioni sono davvero raggiungibili (e in più non dimostra che i 3 invarianti sono indipendenti, ma vabbé). Comunque avevo già sentito altrove che le permutazioni raggiungibili sono la dodicesima parte di quelle totali, quindi direi che il risultato è giusto, anche se nel capitolo 8 non è completamente dimostrato. Non escludo però che più avanti nell'articolo vengano presentate costruttivamente delle operazioni che generino tutto quanto.
Avatar utente
ficus2002
Messaggi: 60
Iscritto il: 10 feb 2006, 00:06

Messaggio da ficus2002 »

Si, concordo con te, nel capitolo 8 non viene data una dimostrazione completa del fatto.
Volevo sapere se esiste qualche teoria al riguardo di questo argomento, ovvero : è dato un gruppo e un'azione del gruppo su un insieme; aggiungiamo pure l'ipoesi di conoscere la rappresentazione del gruppo in generatori e relazioni. E' possibile determinare ll'ordine del gruppo? esistono edgli strumenti specifici?
MindFlyer

Messaggio da MindFlyer »

Dunque, ci ho pensato un momento e non la vedo così difficile da completare, quella dimostrazione. Sostanzialmente abbiamo 3 invarianti, ed occorre dimostrare che sono indipendenti, e che le posizioni generate da essi sono tutte raggiungibili.

La prima parte è facile se si modifica un po' la nozione di permutazione del cubo di Rubik data dall'articolo. Diciamo che una permutazione del cubo è una permutazione dei suoi 20 cubetti (12 spigoli e 8 vertici), in modo che gli spigoli vadano in spigoli ed i vertici vadano in vertici, a prescindere dal loro orientamento. Ovvero, un cubetto spigolo ha 2 orientamenti possibili che consideriamo equivalenti, ed un cubetto vertice ne ha 3 che consideriamo equivalenti. Vediamo che una mossa del cubo non è altro che un passo di un 4-ciclo sui vertici di una faccia, più un 4-ciclo sugli spigoli della stessa faccia. Ognuno dei 4-cicli è la composizione di 3 scambi di cubetti, quindi in totale vi sono 6 scambi, e la permutazione è quindi pari.
Ora, questo invariante è ovviamente indipendente dagli altri due (l'abbiamo definito tale!), ed inoltre l'invariante sugli spigoli è indipendente da quello sui vertici, perché gli spigoli non diventano mai vertici, e viceversa.

Detto questo, occorre dimostrare la seconda parte. Io direi che il metodo migliore è dimostrare che ogni permutazione pari dei cubetti è raggiungibile, a prescindere dal loro orientamento. Dopodiché, far vedere che è possibile ruotare "sul posto" i singoli cubetti in modo da orientarli nel modo giusto, e rispettando gli altri 2 invarianti.
Quest'ultima cosa è facile, perché nell'appendice B dell'articolo vengono descritte delle combinazioni di mosse per
A) ruotare sul posto 2 spigoli adiacenti,
B) ruotare sul posto 2 vertici adiacenti, uno in un senso, uno nell'altro.
La mossa A può essere usata ripetutamente per ruotare simultaneamente 2 spigoli qualunque del cubo. Infatti basta trovare un "cammino" di spigoli adiacenti che colleghi i due, ed applicare la mossa A su tutto il percorso. Nello stesso modo, si può usare ripetutamente la B per ruotare in sensi opposti 2 vertici qualunque. In più, si può ruotare nello stesso senso una terna di vertici qualunque (a,b,c), scegliendo un vertice a caso (d) diverso dai 3 dati, e ruotando a-d, b-d, c-d. Siccome d ruota 3 volte nello stesso senso, torna nello stato iniziale, mentre a, b, c sono ruotati una volta, e tutti nello stesso senso.
Ora, supponiamo che i cubetti siano già al loro posto (in una permutazione pari). Possiamo generare tutti i possibili orientamenti "pari" degli spigoli, perché possiamo ruotarli a coppie qualunque. Fatto questo, possiamo generare anche tutte le rotazioni dei vertici "a somma 0". Infatti, basta accoppiare i vertici da girare in un senso con i vertici da girare nell'altro senso, e girarli a coppie. Resteranno dei vertici da girare in uno stesso senso, che per l'invariante saranno un multiplo di 3. Ma allora basterà usare la mossa che ruota terne di vertici qualunque.

Resta da far vedere che ogni permutazione pari dei cubetti è raggiungibile, e questo è il punto più fastidioso, su cui devo ancora pensare un pochino. Si può di nuovo sfruttare qualche mossa dell'appendice B, ovvero:
C) ciclare 3 vertici della stessa faccia,
D) ciclare 3 spigoli della stessa faccia,
E) ciclare 3 spigoli paralleli,
F) scambiare simultaneamente 2 spigoli adiacenti ed i 2 vertici estremi di uno dei due spigoli.
La mossa F permette di mettere a posto prima tutti i vertici, oppure prima tutti gli spigoli (si fa vedere abbastanza facilmente, perché esiste una "serpentina" di vertici adiacenti che li tocca tutti e si chiude su sé stessa, ed esiste una successione di spigoli adiacenti che li tocca tutti). E da qui, con le mosse D ed E nel primo caso, o con la mossa C nel secondo caso, bisognerebbe mettere a posto il resto dei cubetti. Ma qui non mi è ancora chiaro un metodo, se qualcuno vuole andare avanti...
Avatar utente
Catraga
Messaggi: 302
Iscritto il: 01 gen 1970, 01:00
Località: Trieste (Univ)

Messaggio da Catraga »

DELETED: fraintendimento di domanda. :oops:
Ultima modifica di Catraga il 14 ago 2006, 16:05, modificato 1 volta in totale.
Avatar utente
ficus2002
Messaggi: 60
Iscritto il: 10 feb 2006, 00:06

Messaggio da ficus2002 »

MindFlyer ha scritto:Ma qui non mi è ancora chiaro un metodo, se qualcuno vuole andare avanti...
Ho notato che è sufficiente dimostrare che, tenendo fissi tutti gli angoli, si possono ottenere tutte le permutazioni pari degli spigoli e, tenendo fissi tutti gli spigoli, si possono ottenere tutte le permutazioni pari degli angoli.

Suppongo che questo sia vero e dimostro che è possibile ottenere ogni permutazione pari di angoli e spigoli.

Sia data una permutazione P pari di angoli e spigoli. Le permutazioni indotte sull'insieme degli spigoli Ps e sull'insieme degli angoli Pa hanno la stessa parità.

Se sono entrambe pari abbiamo concluso: infatti, per l'ipotesi che ho fatto, esiste una permutazione che lascia fissi tutti gli angoli e sposta gli spigoli come PS ed esiste una permutazione che fissa tutti gli spigoli e muove gli angoli come Pa. La composizione di queste due permutazioni è P che quindi è realizzabile.

Supponiamo ora che Pa e Ps siano entrambe dispari: allora posso dire che
P=Q*Ha*Hb
dove
1) Q è una permutazione che scambia simultaneamente 2 spigoli adiacenti ed i 2 vertici estremi di uno dei due spigoli.
2) Hs è un'opportuna permutazione pari degli spigoli che fissa tutti gli angoli;
3) Ha è un'opportuna permutazione pari degli angoli che fissa tutti gli spigoli;
La permutazione Q è del tipo F) descritta da MindFlyer, mentre, Hs e Ha sono realizzabili per ipotesi. Quindi, P è realizzabile.

Utilizzando lo stesso usato da metodo di MindFlyer per provare l'orientabilità pari degli spigoli, penso si possa anche dimostrare che, tenendo fissi tutti gli angoli, si possono ottenere tutte le permutazioni pari degli spigoli.
Analogamente per gli angoli.
Avatar utente
ficus2002
Messaggi: 60
Iscritto il: 10 feb 2006, 00:06

Messaggio da ficus2002 »

Una curiosità: come si può formulare formalmente l'indipendenza di due invarianti?
MindFlyer

Messaggio da MindFlyer »

Formuliamola in modo che faccia esattamente quello che vogliamo!! :wink:

Allora, sia X un insieme finito. Un invariante su X è un qualunque sottoinsieme di X.
Due invarianti A e B su X si dicono indipendenti se e solo se $ \displaystyle \#A \cdot \#B=\#(A \cap B) \cdot \#X $.
MindFlyer

Messaggio da MindFlyer »

ficus2002 ha scritto:Supponiamo ora che Pa e Ps siano entrambe dispari: allora posso dire che P=Q*Ha*Hb
Perché?
Utilizzando lo stesso usato da metodo di MindFlyer per provare l'orientabilità pari degli spigoli, penso si possa anche dimostrare che, tenendo fissi tutti gli angoli, si possono ottenere tutte le permutazioni pari degli spigoli.
No, le trasformazioni sull'orientabilità non permutano i cubetti, quindi non servono a niente qui. Bisogna usare le trasformazioni che ciclano terne di vertici e di spigoli...
Magari ci penso ancora un po' e vedo di venirne a capo.
Avatar utente
ficus2002
Messaggi: 60
Iscritto il: 10 feb 2006, 00:06

Messaggio da ficus2002 »

MindFlyer ha scritto:
Utilizzando lo stesso usato da metodo di MindFlyer per provare l'orientabilità pari degli spigoli, penso si possa anche dimostrare che, tenendo fissi tutti gli angoli, si possono ottenere tutte le permutazioni pari degli spigoli.
No, le trasformazioni sull'orientabilità non permutano i cubetti, quindi non servono a niente qui. Bisogna usare le trasformazioni che ciclano terne di vertici e di spigoli...
Magari ci penso ancora un po' e vedo di venirne a capo.
Intendevo dire il metodo che hai usato tu per l'orientabilità, ovviamente utilizzando, stavolta, le trasformazioni che scambiano spigoli.
ficus2002 ha scritto: Supponiamo ora che Pa e Ps siano entrambe dispari: allora posso dire che P=Q*Ha*Hs
Perché?
Poichè Pa è dispari la posso scrivere come un opportuno elemento del gruppo alterno sugli spigoli composto con lo scambio di due scelti spigoli opposti.
Analogamente Pb è la composizione dello scambio di due angoli (estremi di uno dei due spigoli di prima) con un elemento del gruppo alterno sugli angoli.

Le due permutazioni prese dai gruppi alterni sono Hs e Ha. Q è la permutazione che scambia simultaneamente di due spigolo e di due angoli scelti.
MindFlyer

Messaggio da MindFlyer »

Ecco, ho finito. Rimando a QUESTO THREAD per la dimostrazione di 2 semplici lemmi sulle permutazioni. Non li ho messi qui perché appesantirebbero il post, sebbene siano facili da dimostrare.

Riprendendo da dove avevo lasciato la dimostrazione, vogliamo raggiungere una qualunque permutazione pari di spigoli e vertici, senza preoccuparci del loro orientamento. Per fare questo, prima mettiamo a posto gli spigoli (incasinando anche i vertici, ma non importa), e poi sistemiamo i vertici lasciando fermi tutti gli spigoli.

Per fare queste 2 cose, facciamo vedere che spigoli e vertici si possono "linearizzare" in questo modo: numeriamo in senso orario i vertici di una faccia del cubo da 1 a 4, e quelli della faccia opposta da 5 a 8, in modo che i vertici 4 e 5 siano adiacenti. Seguendo i numeri da 1 a 8, si vede che coppie di vertici con numeri consecutivi sono adiacenti nel cubo, ed inoltre che terne di vertici con numeri consecutivi appartengono alla stessa faccia del cubo. Quindi è possibile ciclare 3 vertici consecutivi secondo questa numerazione, grazie all'operazione C descritta qualche post sopra.
Adesso, guardando il cubo ortogonalmente ad una faccia, numeriamo gli spigoli di quella faccia da 1 a 4 in senso orario, quelli della faccia opposta con 11, 9, 7, 6 in senso orario, ed i 4 rimanenti con 10, 8, 5, 12 in senso orario, in modo che lo spigolo 5 sia adiacente agli spigoli 3, 4, 6, 7. Ora, seguendo i numeri da 1 a 12, si vede che spigoli con numeri consecutivi sono adiacenti nel cubo. Quindi è possibile scambiare 2 spigoli consecutivi secondo questa numerazione, grazie all'operazione F.

Ok, usando il lemma 1 enunciato nell'altro thread, riusciamo quindi a sistemare gli spigoli in qualunque permutazione vogliamo, grazie alla mossa F. Fatto questo, la permutazione da operare ai vertici per concludere, sarà sicuramente pari. Infatti, la mossa F scambia 2 vertici e 2 spigoli, ed è quindi una permutazione pari. Allora, se la permutazione complessiva spigoli+vertici dev'essere pari, resterà pari anche dopo l'applicazione di un qualsiasi numeri di mosse F. Ma ogni permutazione pari dei vertici è raggiungibile lasciando fermi gli spigoli, grazie alla mossa C ed al lemma 2 dell'altro thread.

Riassumendo, tutte le permutazioni pari del cubo di Rubik che rispettano i 2 invarianti sull'orientamento di spigoli e vertici, sono raggiungibili.
Avatar utente
ficus2002
Messaggi: 60
Iscritto il: 10 feb 2006, 00:06

Messaggio da ficus2002 »

Ho soluzione alternativa nel caso che Pa e Ps siano entrambe dispari: sia Q una qualunque permutazione del tipo F) citato da Minflyer; allora PQ induce una permutazione pari degli spigoli e una permutazione pari degli angoli. Quindi ci siamo ricondotti al caso in cui Pa e Ps sono pari.
MindFlyer

Messaggio da MindFlyer »

ficus2002 ha scritto:Ho soluzione alternativa nel caso che Pa e Ps siano entrambe dispari: sia Q una qualunque permutazione del tipo F) citato da Minflyer; allora PQ induce una permutazione pari degli spigoli e una permutazione pari degli angoli. Quindi ci siamo ricondotti al caso in cui Pa e Ps sono pari.
E' sostanzialmente quello che dicevi sopra per motivare il fatto che P=Q*Ha*Hs, mi sembra.
Però a questo punto non è chiaro come risolvi la Ps senza toccare i vertici.
Rispondi