Giochi di... gruppi

Alessandro Logar

Dipartimento di Scienze Matematiche
Università degli studi di Trieste

Animazioni di: Alessandro Budai












Probabilmente a tutti è capitato di avere tra le mani quel gioco che porta il nome di "cubo di Rubik" o "cubo magico". Esso è costituito da un cubo di plastica le cui facce non sono fisse: un ingegnosissimo meccanismo permette loro di muoversi permutando in tal modo i cubetti colorati che compongono ciascuna faccia. Scopo del gioco è di essere in grado di ricomporre il cubo nella posizione originaria.
Si può dimostrare che il numero di configurazioni differenti che un cubo di Rubik può assumere è dato da:

227314537211=43252003274489856000,
cioè circa 0.4*1020. Tanto per avere un'idea della grandezza di questo numero si pensi che se si volessero mostrare tutte le configurazioni che può assumere un cubo di Rubik dedicando un solo secondo a ciascuna di esse, si impiegherebbero circa 1370 miliardi di anni (si stima che il Sole brillerà ancora circa 5 miliardi di anni...). Insomma, riuscire ad elencare tutte le configurazioni di un cubo di Rubik sembra un'impresa assolutamente impossibile. Questo fatto però non deve scoraggiarci: per trovare la soluzione al rompicapo infatti non è necessario conoscere tutte le possibili configurazioni, ma basta saper destreggiarsi tra un po' di esse con sufficiente abilità.
Scopo di queste animazioni è di introdurre il lettore interessato a scoprire la strategia da seguire per saper risolvere il rompicapo del cubo di Rubik, senza però dare esplicitamente la soluzione... Si introdurranno invece alcuni nuovi giochi simili al rompicapo di Rubik ma più semplici per mezzo dei quali si scopriranno alcune possibili strategie di soluzione. Prenderemo il problema un po' alla larga e coglieremo l'occasione per introdurre altri concetti matematici di per sè interessanti che rientrano nella teoria dei gruppi... Per risolvere i giochi qui presentati non è assolutamente richiesta alcuna nozione matematica ma può darsi che chi possiede alcune conoscenze di teoria dei gruppi apprezzi ritrovare quelle nozioni in una veste un po' diversa.

Nei primi giochi interattivi che introdurremo, lavoreremo con una sequenza di alcune caselle numerate, come ad esempio la seguente:

e con alcune regole del gioco che diranno come scambiare fra loro le caselle.
 

Parte A: primi passi

Gioco1:
Qui di seguito sono date 5 caselle. All'inizio sono disposte ordinate. Il tasto "disorder" le mette in disordine. I 4 tasti successivi danno le mosse consentite: il primo di essi esegue lo scambio 1->2->1, cioè manda la casella che occupa il posto 1 nella casella che occupa il posto 2 e viceversa, la casella che occupa il posto 2 nella casella che occupa il posto 1. Analogamente i successivi pulsanti.




Problema 1: Partendo da una configurazione qualunque dei 5 numeri, si riesce sempre a riordinare la fila di 5 caselle, in modo che quella con il numero 1 occupi il primo posto, quella con il numero 2 il secondo e cosi' via?

Naturalmente lo stesso problema può essere riaffrontato per un numero qualunque di caselle, ad esempio 7, come nel:

Gioco 2: Qui le regole sono le stesse delle precedenti, ma sono stati aggiunti ancora due tasti, per permettere lo scambio delle caselle ai posti [5,6] e ai posti [6,7].



Soluzione...

La risposta al problema 1 dunque è affermativa: bastano gli scambi di due caselle alla volta per permutare in tutti i modi possibili i numeri 1,2,3,4,5 (o 1,2,3,4,5,6,7 o, in generale, 1,2,...,n). Quanto ora scoperto è un noto teorema di matematica (più precisamente di teoria dei gruppi) che di solito si formula nel seguente modo:

Teorema. Il gruppo simmetrico Sè generato da 2-cicli.

(La totalità delle permutazioni dei numeri 1,2,...,n si chiama "gruppo simmetrico" e uno scambio di due caselle si chiama un "2-ciclo"; un modo alternativo per enunciare il precedente teorema è il seguente: ogni permutazione dei numeri 1,2,...,n è un prodotto di 2-cicli).
 

Continuiamo con un gioco successivo:

Gioco 3: Anche qui il tasto "disorder" ha lo scopo di mischiare le caselle in tutti i modi possibili; le mosse consentite ora sono solo due: il pulsante 1->2->1 effettua lo scambio delle caselle che occupano i primi due posti, il pulsante successivo effettua la "traslazione" che muta la prima casella al posto della seconda, la seconda al posto della terza, ecc, finchè l'ultima è mandata al posto della prima. E' stato inserito poi per comodità anche un ulteriore pulsante: esso fa il movimento inverso del precedente pulsante. E' superfluo perchè fornisce lo stesso movimento che si ottiene eseguendo per 4 volte consecutive il precedente  pulsante della traslazione.



Problema 2: Partendo da una qualunque configurazione delle 5 caselle, è sempre possibile riordinarle? E se le caselle sono più di 5 (o meno), vale lo stesso risultato?

Soluzione...

Anche qui dunque la risposta è affermativa e anche ora il risultato trovato è un ben noto teorema di teoria dei gruppi:

Teorema.  Il gruppo simmetrico Sè generato da un 2-ciclo e da un n-ciclo.

Infine, vediamo un ulteriore tipo di mosse:

Gioco 4: le mosse lecite sono ora:  1->2->3->4->5->1  e  1<->2 contemporaneamente a 4<->5. Con la configurazione di partenza: [3,5,4,2,1] (per ora si suggerisce di non usare il tasto "disorder" ma di tentare di risolvere il gioco cosi' come è dato).


Problema 3: Partendo dalla configurazione [3,5,4,2,1] si riescono a riordinare le caselle?

Soluzione...

Gioco 5: analogo al precedente, ma si parte dalla configurazione [3,5,2,4,1].


Problema 4: Stessa domanda del problema 3, ma partendo dalla configurazione [3,5,2,4,1].

Soluzione...

 Il primo dei due precedenti giochi si riesce a risolvere abbastanza facilmente. Però per quanto riguarda il secondo, per quanti tentativi uno faccia, non sembra possibile risolverlo... In effetti è proprio cosi': cerchiamo ora di dare una spiegazione del perchè.
 

Finora dunque abbiamo incontrato alcuni gruppi: i gruppi simmetrici Sn e i gruppi alternanti An
Per giocare con alcuni di essi (e con qualche altro gruppo) cliccare qui.
 
 

Parte B: verso il cubo di Rubik


Passiamo ora ad un'altra categoria di giochi. Non dimentichiamo che lo scopo finale è quello di saper maneggiare il cubo di Rubik.

Gioco 6: Anche qui si tratta di riordinare una configurazione di numeri. I movimenti consentiti sono essenzialmente due, corrispondenti ai primi due bottoni e li indichiamo per comodità con le lettere f e g. 




Qualche ulteriore spiegazione sui tasti: Per facilitare lo studio, sono stati inseriti altri bottoni: La completa utilizzazione dei tasti sarà probabilmente più chiara via via che si eseguono i giochi successivi.

Problema 5: Provare a mettere in disordine i 6 numeri azionando i pulsanti di f e g a caso e poi cercare di riordinarli (la posizione che ogni numero deve occupare è indicata dai numeri scritti sullo sfondo).

Soluzione...

Problema 6: Trovare sequenze di mosse che, partendo dalla configurazione iniziale, rimettano i 6 numeri nella loro giusta posizione (esempi: f^3f oppure f^2g^2g^2f^2 oppure f^2g^2f^2g^2f^2g^2...)

Problema 7: Azionare prima di tutto il tasto "reset". Poi definire (con "add") un nuovo tasto che contiene una sequenza di mosse a piacere (come ad esempio fg^-1f^3g^2) e, partendo dalla configurazione iniziale dei sei numeri, ripetere varie volte l'esecuzione del nuovo tasto. Succede sempre che dopo un numero sufficiente di ripetizioni i sei numeri si vengono a ritrovare nuovamente nella posizione giusta? Se h è una certa sequenza di mosse, con h-1 (o h^-1) indichiamo la sequenza di mosse inversa di h (e quindi eseguire prima h e subito dopo h-1 non sortisce alcun effetto). Se h è data da una sequenza di mosse come ad esempio fg oppure fgf^-1gf^2 , come si esprime h-1?

Soluzione...

Passiamo ora finalmente a parlare del cubo di Rubik. Per cominciare semplifichiamo più possibile il problema: per ora supponiamo di usare un cubo in cui possono muoversi solo due facce adiacenti. Inoltre concentriamo la nostra attenzione solo sui movimenti dei sei cubetti di vertice. Quello che quindi si ottiene da un cubo di Rubik così ridotto è molto simile a quanto descritto dal seguente:

Gioco 7: In questo gioco i tasti hanno lo stesso significato dei tasti del gioco 6.  Inizialmente abbiamo 6 cubetti sistemati in modo che a sinistra (per chi guarda) hanno tutti la faccia arancione, a destra la faccia bianca e sopra la faccia gialla (i 3 quadratini colorati in arancione, bianco e giallo rimangono fissi e stanno ad indicare le posizioni corrette dei colori delle facce) Provare a "disfare" il gioco e tentare di rimetterlo a posto...

Molto facilmente dopo breve tempo si raggiungerà una configurazione dalla quale non è più molto facile tornare in dietro... Però... cosa c'entra il gioco 7 con il gioco 6? La spiegazione sta nel:

Gioco 8: I pulsanti hanno, anche qui, lo stesso significato dei pulsanti dei giochi precedenti.

Come si vede, dunque, il gioco 6 era una semplificazione del gioco 7: simulava il movimento dei sei cubetti di vertice di due facce contigue di un cubo di Rubik.
Rimettiamo ora nuovamente in disordine il disegno considerato nel gioco 8 per poi tentare di ricomporlo. Nel tentare di risistemarlo, seguiamo però la seguente strategia: guardando solo la parte sinistra dell'animazione metiamo a posto i 6 numeri, come fatto nel gioco 6. Ciò significa necessariamente rimettere i 6 cubetti nelle loro posizioni originali. Quello che però subito si constata è il fatto seguente: non basta rimettere a posto la parte sinistra del gioco per risistemare tutto: infatti anche se i cubetti vengono ad occupare le posizioni corrette, non le occupano necessariamente con la giusta orientazione. Saper risolvere il gioco 6 non è quindi sufficiente a risolvere del tutto il gioco 7. Ciò nonostante, abbiamo comunque fatto un passo importante verso la soluzione del gioco 7.
Resta dunque ancora il problema delle orientazioni. A tal fine abbiamo il seguente:

Gioco 9: I tasti sono gli stessi dei giochi precedenti, in più abbiamo solo un ulteriore disegno...





Il gioco precedente dovrebbe evidenziare quanto manca per completare il gioco delle due facce del cubo. Il disegno di destra è "attivo" solo quando i sei cubi occupano le posizioni giuste, cioè solo quando il gioco di sinistra è risolto e, quando è attivo, indica l'orientazione dei sei cubetti. Ognuno dei sei triangoli può assumere le seguenti tre posizioni:

la prima indica che il cubetto corrispondente è nella posizione giusta, la seconda indica che è ruotato di 120 gradi in senso orario e la terza indica che è ruotato di 270 gradi in senso orario. Un po' di dimestichezza con il cubo di Rubik (o con il gioco 7) mostra che ogni vertice (cubetto) in effetti può occupare la posizione giusta in tre sole posizioni:

Dunque i triangoli servono semplicemente ad evidenziare le tre suddette possibili posizioni. Chiaramente il gioco 7 (o il gioco 8 o il gioco 9) è risolto quando sono a posto sia i sei numeri dell'animazione di sinistra, sia i sei triangoli dell'animazione di destra.

Problema 8: Trovare un po' di possibili orientazioni dei triangolini del gioco 9. In altre parole provare a "disfare" il gioco applicando un po' di volte i tasti f e g e poi rimettere a posto solo il gioco dei sei numeri (si faccia riferimento al problema 6). Sarà probabilmente utile utilizzare i vari tasti a disposizione, quali ad esempio "add" e "Store result".

D'ora in poi chiamiamo H l'insieme di tutte le possibili mosse che risolvono il problema 8. Tra tutti gli elementi di H che si possono scoprire, mettiamo in evidenza il seguente:

fg2f-1g-1fg-1f-1g2
(cioè, nella sintassi che deve essere usata nella finestrella: fg^2f^-1g^-1fg^-1f^-1g^2)

Esso sortisce il seguente effetto (come subito si constata testandolo): lascia i sei numeri nelle loro posizioni corrette (e ciò deve accadere, in quanto abbiamo detto che è un elemento di H) e ruota i tre cubetti 2, 3 e 6 (cioè il centrale alto e i due di destra) di 270 gradi in senso orario. Chiamiamo da adesso in poi h la sequenza di mosse sopra indicata.

Problema 9: Trovare un elemento di H che ruota in di 2/3 di giro in senso orario i cubetti 2,3,5. (Tra le varie soluzioni, vi è una particolarmente "poco faticosa"...)

Soluzione...

Problema 10: Trovare

a) un elemento di H che ruota i cubetti 2, 3 e 6 di 120 gradi in senso orario;
b) un elemento di H che ruota i cubetti 1, 4 e 5 di 270 gradi in senso orario;
c) un elemento di H che ruota i cubetti 2, 4 e 5 di 270 gradi in senso orario;
Soluzione...

Problema 11: Che effetto si ottiene se in h definito sopra si scambia f con f-1 e g con g-1 (ottenendo quindi i:=f-1g2fgf-1gfg2)?

Soluzione...

I precedenti problemi permettono in particolare di costruire nuovi elementi di H. Notiamo una proprietà di H che segue facilmente una volta che si è capito il tipo di soluzione dato nel problema 9 e nel punto c) del problema 10. Si tratta della seguente:

Proprietà di H: se k è un qualunque elemento di H e se v è una qualunque mossa, allora vkv-1 è ancora un elemento di H.

Nel corso dei precedenti problemi in particolare abbiamo costruito due elementi di H che ci possono tornare utili: l'elemento h (cioè fg^2f^-1g^-1fg^-1f^-1g^2) e l'elemento i (cioè f^-1g^2fgf^-1gfg^2). Si provi ad eseguire ancora la mossa hi (cioè fg^2f^-1g^-1fg^-1f^-1g^2f^-1g^2fgf^-1gfg^2). Essa è naturalmente un elemento di H. Il suo effetto (facilmente prevedibile, una volta noti gli effetti di h e di i) è quello di far ruotare il cubetto 2 di 270 gradi in senso orario e il cubetto 5 di 120 gradi in senso orario.

Problema 12: Trovare una sequenza di mosse per:

a) ruotare (esclusivamente) il cubetto 1 di 270 gradi in senso orario e il cubetto 2 di 120 gradi in senso orario;
b) ruotare (esclusivamente) il cubetto 1 di 270 gradi in senso orario e il cubetto 6 di 120 gradi in senso orario;
c) ruotare (esclusivamente) il cubetto 1 di 120 gradi in senso orario e il cubetto 6 di 270 gradi in senso orario.
Soluzione...

A questo punto si hanno sufficienti strumenti per risolvere il gioco 7. La tecnica è la seguente: dapprima si mettono i 6 cubi nella loro posizione corretta, senza prestare attenzione alla loro orientazione. Successivamente, usando ad esempio la mossa hi, con ragionamenti analoghi a quelli fatti per risolvere i punti a), b) e c) del problema 12, si cercano di ruotare, due alla volta, i singoli cubetti fino a sistemarli tutti.

Fin qui abbiamo dato una tecnica per risolvere un sotto-problema molto particolare del problema generale del cubo di Rubik. Le nozioni introdotte sono però quasi sufficienti per rimettere a posto l'intero cubo di Rubik. I motivi sono due: innanzitutto il tipo di ragionamento da seguire per risolvere il rompicapo è della stessa natura dei ragionamenti fatti precedentemente e in secondo luogo, le mosse che fin qui si sono introdotte sono già un ottimo strumento. Si aggiunga ad esse la mossa seguente:

hgig-1.
Se eseguita su un cubo di Rubik integro il suo effetto è molto ben visibile: fa ruotare solamente tre cubetti centrali lasciando tutto il resto del cubo fisso. Questa mossa permette quindi, se usata con sufficiente astuzia, di mettere a posto tutti i cubetti centali. Resta ancora un problema con i cubetti di vertice che non è risolvibile con le sole mosse combinate di due facce contigue. Come detto all'inizio, qui non si vuol dare la soluzione completa del rompicapo...

Chi è interessato ad alcuni aspetti teorici del gioco 9, clicchi qui.