Galois si diverte col cubo di Rubik

GALOIS SI
DI VERTE
COL CUBO
DI RUB IK
Indice Area di Progetto “Galois si diverte col cubo di Rubik”
PREREQUISITI
1.1 Definizione di insieme……………………………………………………….. pagina 1
1.2 Operazioni con gli insiemi…………………………………………………… pagina 2
1.3 Funzione biunivoca e funzione univoca, suriettiva e iniettiva…………………. pagina 3
I GRUPPI: DA COSA SCATURISCONO?
2.1 Cenni storici ………………………………………………………………….. pagina 4
2.2 Galois. Chi è? Biografia breve………………………………………………… pagina 5
STRUTTURE ALGEBRICHE E GRUPPI
3.1 Strutture algebriche…………………………………………………………… pagina 6
3.2 Definizione e caratteristiche di un gruppo…………………………………….. pagina 7
ESEMPI DI GRUPPI
4.1 Un po’ d’esempi……………………………………………………………… pagine 8-9
4.2 Gruppo ciclico………………………………………………………………... pagina 10
4.3 Gruppo delle classi resto modulo n…………………………………………… pagina 11
4.4 Gruppo delle matrici quadrate di ordine n…………………………………….. pagina 12
PERMUTAZIONI
5.1 Un particolare gruppo: le permutazioni……………………………………….. pagine 13-14
5.2 Una particolare permutazione: l’Identità………………………………………. pagina 15
5.3 Permutazione Simmetrica……………………………………………………... pagina 16
5.4 L’ordine di una permutazione………………………………………………… pagina 17
5.5 Scomposizione in trasposizioni………………………………………………... pagina 18
5.6 Un sottogruppo nelle permutazioni…………………………………………… pagina 19
5.7 Permutazioni classi pari e dispari……………………………………………… pagina 20
GIOCHI APPLICATI ALLA TEORIA DEI GRUPPI
6.1 Il gioco del 15………………………………………………………………… pagine 21-22
6.2 Il cubo di Rubik……………………………………………………………...... pagina 23
RINGRAZIAMENTI FINALI…………………………………………………………… pagina 24
1.0 - Prerequisiti
1.1 - DEFINIZIONE DI INSIEME
Il concetto di insieme costituisce l'elemento fondante di gran parte delle esposizioni della
matematica moderna: i principali testi introduttivi a buona parte delle aree della matematica
iniziano con nozioni di teoria degli insiemi. con il termine insieme si indica una collezione di oggetti
chiamati elementi dell'insieme. Ciò che caratterizza il concetto di insieme è:
un elemento può appartenere o non appartenere a un determinato insieme, non ci sono vie di
mezzo (come accade invece per gli insiemi sfocati);
un elemento non può comparire più di una volta in un insieme (mentre può comparire più volte in
un multi insieme)
gli elementi di un insieme non hanno un ordine di comparizione (come invece accade ai
componenti di un vettore o di un insieme totalmente ordinato)
gli elementi di un insieme lo caratterizzano univocamente: due insiemi coincidono se e solo se
hanno gli stessi elementi.
In molte esposizioni il concetto di insieme è considerato primitivo ed intuitivo.
"primitivo" perché viene introdotto come nozione non derivabile da concetti più elementari,
"intuitivo" perché viene introdotto come generalizzazione della nozione di insieme finito, concetto
a sua volta introdotto con metafore come quella dell'elenco di identificatori di oggetti o di scatola
contenente oggetti materiali (tendenzialmente omogenei); questa impostazione fa talora
riferimento al convincimento che l'idea di insieme nasca spontaneamente nella nostra mente ed ivi
ne sia sepolta.
1.2 – OPERAZIONI CON GLI INSIEMI
La somma sui numeri naturali N è un’operazione binaria su N. Infatti ad ogni coppia di numeri
naturali (es. 5 e 8) associa un altro numero naturale (es. 13 = 5+8) che è il risultato della somma.
Definizione
Un’operazione binaria su un insieme A è un’applicazione da A * A in A. Ovvero
un’applicazione che ad ogni coppia di elementi a,b Î A associa uno ed un solo elemento di
A.
1.3 - FUNZIONE BIUNIVOCA E FUNZIONE UNIVOCA, SURIETTIVA E INIETTIVA
E’ possibile ora introdurre nuovi concetti sulla base di quanto appena esposto.
Una corrispondenza tra insiemi A e B si dice univoca se associa a ogni elemento di A uno ed un
solo elemento di B, ma non viceversa.
Si dice Biunivoca se associa ad ogni elemento di A uno ed un solo elemento di B e viceversa.
Quindi una corrispondenza biunivoca tra due insiemi X e Y è una relazione binaria tra X e Y, tale
che ad ogni elemento di X corrisponda uno ed un solo elemento di Y, e viceversa ad ogni
elemento di Y corrisponda uno ed un solo elemento di X.
Lo stesso concetto può anche essere espresso usando le funzioni: una funzione
Una funzione è biunivoca se e solo se è contemporaneamente iniettiva e suriettiva:
Una funzione si dice iniettiva se elementi distinti del dominio hanno immagini distinte, o
equivalentemente se ad ogni elemento del codominio corrisponde al più un elemento distinto del
dominio; formalmente:
è iniettiva se
o equivalentemente:
è iniettiva se
Una funzione si dice suriettiva quando l'immagine coincide con il codominio, ovvero quando ogni
elemento y del codominio è immagine di almeno un elemento x del dominio.
Formalmente, una funzione
è suriettiva se
.
2.0 - I GRUPPI: DA COSA SCATURISCONO?
2.1 - CENNI STORICI
LA TEORIA DEI GRUPPI HA TRE RADICI STORICHE: LA TEORIA DELLE EQUAZIONI ALGEBRICHE , LA
TEORIA DEI NUMERI E LA GEOMETRIA.
EULERO, GAUSS, L AGRANGE, ABEL E GALOIS SONO STATI I PRIMI AD INDAGARE NELL ' AREA DELLE
TEORIA DEI GRUPPI . G ALOIS HA IL MERITO DI ESSERE STATI IL PRIMO MATEMATICO A STABILIRE UN
COLLEGAMENTO FRA TEORIA DEI GRUPPI E TEORIA DEI CAMPI CON QUELLA CHE ORA VIENE
CHIAMATA TEORIA DI
GALOIS.
LA MODERNA DEFINIZIONE DI GRUPPO È STATA DATA DA W ALTHER VON DYCK NEL 1882.
NELLA SECONDA METÀ DEL XX SECOLO SI È AVUTO LO SVILUPPO SISTEMATICO DELLA TEORIA DEI
GRUPPI FINITI CHE HA CONSENTITO DI OTTENERE UNA CLASSIFICAZIONE DEI GRUPPI FINITI SEMPLICI
1982. FIGURE CHIAVE DI QUESTA IMPRESA CHE HA COINVOLTO MOLTE
DECINE DI RICERCATORI SONO D ANIEL G ORENSTEIN , JOHN G RIGGS THOMPSON E M ICHAEL
ASCHBACHER. A QUESTO E A SIMILI SVILUPPI HANNO DATO UN NOTEVOLE CONTRIBUTO LE INDAGINI
QUASI COMPLETA NEL
SPERIMENTALI EFFETTUATE CON COMPUTER DI ELEVATA POTENZA E SISTEMI SOFTWARE MOLTO
(CAS) SUI GRUPPI FINITI E SULLE ALTRE STRUTTURE ALGEBRICHE E COMBINATORIE
COLLEGATE CON TALI GRUPPI .
ARTICOLATI
Ad ogni modo il concetto di gruppo nacque sostanzialmente dagli studi sulle equazioni polinomiali,
iniziati da Évariste Galois negli anni 1830. In seguito a contributi provenienti da altri settori della
matematica come la teoria dei numeri e la geometria, la nozione di gruppo fu generalizzata e
definita stabilmente attorno al 1870. La moderna teoria dei gruppi si occupa dello studio astratto
dei gruppi.
I matematici hanno sviluppato varie nozioni per spezzare i gruppi in parti più piccole e più facili da
studiare, come i sottogruppi ed i quozienti. Oltre alle loro proprietà astratte, i teorici dei gruppi si
occupano anche dei differenti modi in cui un gruppo può essere espresso concretamente, da un
punto di vista sia teorico, sia computazionale. Una teoria particolarmente ricca è stata sviluppata
per i gruppi finiti, culminata con la classificazione dei gruppi semplici finiti, completata nel 1983.
2.2 - GALOIS. CHI È? – BIOGRAFIA BREVE
Ragazzo prodigio, poco più che adolescente riuscì a determinare un metodo generale per scoprire
se una equazione è risolvibile o meno con operazioni quali somma, sottrazione, moltiplicazione,
divisione, elevazione di potenza ed estrazione di radice, risolvendo così un problema della
matematica vecchio di millenni.
Il suo lavoro ha posto le basi per la teoria che porta il suo nome, la Teoria di Galois appunto,
un'importante branca dell'algebra astratta. È stato anche il primo ad utilizzare il termine gruppo in
matematica per definire un insieme di possibili permutazioni di elementi, ed ha definito i gruppi che
portano il suo nome: i gruppi di Galois.
Galois era un fervente repubblicano, ed è famoso un suo brindisi al Re con in mano un coltello.
Questo brindisi lo portò in prigione e solo grazie a degli amici che testimoniarono a suo favore
riuscì ad essere scarcerato.
Morì per una ferita allo stomaco riportata in un duello, a soli vent'anni di età.
Ritratto di Evariste Galois
3.0 - STRUTTURE ALGEBRICHE E GRUPPI
3.1 – Strutture algebriche
“Una struttura algebrica è costituita da un insieme e da un operazione, detta legge di composizione
interna.
Quest’operazione composta con un qualsiasi elemento dell’insieme della struttura algebrica deve
identificare sempre un elemento dello stesso insieme.”
3.2 - DEFINIZIONE E CARATTERISTICHE DI UN GRUPPO
Possiamo ora passare alla definizione di gruppo: “esso è costituito insieme con un’operazione
binaria sui suoi elementi che soddisfa le seguenti quattro condizioni”:
1. L’operazione * è chiusa. Cioè se a, b  A  a  b  A
2. L’operazione * è associativa. Cioè se a, b, c  A  a  b  c   a  b  c
3. Esiste un elemento neutro. Cioè e  A tale che a  e  e  a  a a  A
4. Esiste l’inverso rispetto a * di ogni elemento a  A . Cioè a  A a' A tale che
a  a'  a'a  e
Un gruppo si dice abeliano (o commutativo) se per ogni a, b  A si ha a  b  b  a .
4.0 – Esempi di gruppi
4.1 – Un po’ d’esempi
Esempio n.1
1. Sia A l’insieme costituito dai numeri 1 e -1 e come operazione consideriamo il
prodotto. E’ facile verificare che si tratta di un gruppo, cioè che soddisfa i punti 1, 2,
3 e 4 della definizione. Questo è un gruppo finito con 2 elementi.
2. L’insieme delle simmetrie di un triangolo equilatero con la composizione
forma un gruppo. Gli elementi sono 6: l’identità, la rotazione di 120°,
la rotazione di 240° e le riflessioni attorno alle tre altezze.
Esempio n.2
Prendiamo un quadrato e consideriamo l’insieme costituito dalle sue rotazioni di 90°, 180° e 270°,
la simmetria delle diagonali e la rotazione banale che lascia il quadrato così com’è. Come
operazione prendiamo la composizione di rotazioni ovvero facciamo una rotazione seguita da
un’altra rotazione.
Questo è un gruppo finito.
Esempio n.3
Anche le simmetrie di un poliedro formano un gruppo finito. Di particolare importanza sono i gruppi
di simmetria dei solidi platonici. Le simmetrie di un tetraedro sono 24: oltre all'identità, ci sono 11
rotazioni intorno ad un asse, 6 riflessioni rispetto ad un piano e altre 6 operazioni ottenute
componendo rotazioni e riflessioni.
4.1 – Gruppo ciclico
Un gruppo G è ciclico se esiste un elemento g del gruppo (detto generatore) tale cheG è l'insieme
delle potenze di g ad esponente intero, in simboli .
Ad esempio, se G = { e, g1, g2, g3, g4, g5 } allora G è ciclico.
In altre parole, G coincide con il sottogruppo <g> generato da g. Si usa quindi scrivere G = <g>.
Esempi di un gruppo ciclico: CLASSI DI RESTO
L'esempio seguente, fornito dalla aritmetica modulare, è fondamentale.
Poiché Zn è un sottogruppo normale di Z di indice n, il gruppo quoziente Z/Zn è un gruppo
commutativo finito con n elementi, che possiamo scrivere { 0, 1, 2, ..., n-1 }.
La somma fra due elementi a e b è il resto della divisione di a + b per n. Poiché ogni elemento si
scrive come n = 1 + ... + 1 (sommato n volte), il numero 1 è generatore del gruppo. Quindi Z/Zn è
un gruppo ciclico.
4.2 – Gruppo delle classi resto modulo n
E’ l’insieme di quei numeri interi che danno lo stesso resto se divisi per uno stesso intero.
{..., -7, -5, -3, 1, 3, 5, 7,...} formano una classe di resto [1] perchè divisi per 2 danno lo stesso resto
1.
L’argomento è intrigante: utilizzare classi di resto anziché numeri nelle operazioni.
Le applicazioni pratiche sono di grande interesse: basti pensare che attualmente (e almeno fin
quando i computer quantistici non saranno realtà), l’esistenza delle transazioni commerciali e
bancarie via Internet è resa possibile grazie alle cifrature basate sull’algebra delle classi di resto.
Dato l’insieme N diremo che a è congruo a b modulo n
(e scriveremo a ≡ b mod n) se accade che dividendo sia a sia b per il numero n, si ottiene lo stesso
resto.
Perciò se, ad esempio, consideriamo un sottoinsieme proprio di A in N, costituito dai numeri
naturali {0; 1; 2; …; 39; 40; 41}, diremo che sono congrui fra loro modulo 7, rispettivamente i gruppi
di numeri:
0;
7;
14;
21;
28; 35
1;
8;
15;
22;
29; 36
2;
9;
16;
23;
30; 37
3;
10; 17;
24;
31; 38
4;
11; 18;
25;
32; 39
5;
12; 19;
26;
33; 40
6;
13; 20;
27;
34; 41
In base a questa relazione è possibile suddividere l’insieme dei numeri naturali in classi di
equivalenza, dove nella stessa classe metteremo tutti quei numeri che, divisi per un numero
prefissato n (nell’esempio precedente 7) danno lo stesso resto (nell’esempio 0,1,2,…,5,6).
È evidente che ciascuna delle classi di equivalenza può essere rappresentata da ognuno dei suoi
elementi, ma solitamente si prende come rappresentante il più piccolo fra loro e cioè proprio il
resto. Questo il motivo per cui tali classi di equivalenza si chiamano classi di resti modulo n. A tal
proposito in matematica è consuetudine parlare di aritmetica dell’orologio quando si parla si classi
di resti mod12 e, per analogia, di aritmetica delle stagioni quando si parla di classi di resti mod 4 e
di aritmetica della settimana quando si parla di classi di resto modulo 7.
4.3 – Gruppo delle matrici quadrate di ordine n
In algebra una matrice quadrata è una matrice con un numero uguale di righe e colonne, detto
ordine della matrice. Viene altrimenti detta "matrice
".
Un esempio del suo utilizzo lo abbiamo trovato nel metodo di Cramer per la risoluzione di sistemi
di equazioni.
L'operazione di somma tra matrici è chiusa . Infatti la somma di due matrici è ancora una matrice.
Rispetto all'operazione di somma tra matrici
l' elemento neutro : la matrice nulla,una matrici i
cui elementi sono tutti nulli, nel caso dell’addizione, quindi, uguali a 0.
L'operazione di somma tra matrici è associativa.
Rispetto all'operazione di somma tra matrici
l' elemento inverso : matrice inversa.
Inversa di una matrice quadrata
è un'altra matrice quadrata, indicata con
e
dove
è la matrice identità.
, tale che
5.0 – LE PERMUTAZIONI
5.1 - UN PARTICOLARE GRUPPO: LE PERMUTAZIONI
Un modo semplice di pensare ad una permutazione di n oggetti è quello di immaginare un insieme
di scatole numerate da 1 a n e un insieme di palline, anch’esse numerate da 1 a n, dove ciascuna
scatola contiene una sola pallina. Una permutazione consiste nel togliere tutte le palline dalle
scatole e successivamente riporle (nelle stesse o in differenti scatole) in modo tale che alla fine in
ogni scatola ci sia esattamente una pallina.
Esempio
Consideriamo l’insieme costituito da 4 palline numerate, sia quindi A  1,2,3,4.
Una permutazione potrebbe essere quella che sposta
la pallina 1 nella scatola 3
la pallina 2 nella scatola 2
la pallina 3 nella scatola 4
la pallina 4 nella scatola 1
Ciò che abbiamo appena enunciato possiamo rappresentarlo secondo una notazione molto più
diretta oltre che semplice. Disporremo dunque su di una riga i numeri da 1 a 4 (le palline) e
sull’altra riga i numeri delle rispettive scatole in cui le palline si vengono a trovare dopo la
permutazione.
1 2 3 4


3
2
4
1


A questo punto potrebbe sorgere spontanea la domanda: “quante permutazioni possono essere
eseguite sugli elementi di un dato insieme?”. Per dare una risposta a tale quesito, possiamo
avvalerci dell’utilizzo del fattoriale. Di seguito la definizione di tale elemento incognito:
“In matematica, se n è un intero positivo, si definisce n fattoriale e si indica con n! il prodotto dei
primi n numeri interi positivi.”
Nel nostro caso dunque, con n = 4, le possibili combinazioni tra questi quattro elementi risultano
essere 4! Ovvero 4  3  2  1 cioè 24 combinazioni possibili con 4 oggetti.
Tenendo sempre presente l’esempio preso in considerazione, vediamo come è possibile
rappresentare le permutazioni in un modo ancora migliore: con la notazione in cicli.
La prima pallina, quella numero 1, è andata a finire nella scatola numero 3, la pallina numero 3
nella scatola 4 e la pallina numero 4 nella scatola 1 (siamo tornati al punto di partenza). Possiamo
riassumere tutto ciò nella seguente scrittura che prende il nome di ciclo: 1 3 4 .
Interpretiamo la notazione ciclica: l’insieme dei numeri tra parentesi forma un ciclo in cui ciascuna
pallina si muove nella scatola di quello che segue, fino ad arrivare all’ultimo che si muove nella
scatola del primo della lista.
I cicli possono avere lunghezze variabili da un minimo di 1 (nel caso in cui la pallina non viene
spostata) fino ad un massimo di n che il numero totale di palline.
In conclusione la permutazione d’esempio si può scrivere in notazione ciclica nel seguente modo:
1
3 42
Questi cicli si dicono disgiunti, infatti ogni numero appare in un solo ciclo.
Di solito i cicli di lunghezza 1 vengono omessi visto che in tal caso quella pallina viene lasciata
fissa.
Teorema
Ogni permutazione si può esprimere in modo unico come prodotto di cicli disgiunti
Dimostrazione
Se analizziamo con cura la descrizione del processo che porta alla decomposizione in cicli
disgiunti, ci accorgiamo che lo possiamo modificare solo ricorrendo a scelte diverse degli
elementi di partenza; ad esempio, potremmo partire da 4 invece che da 1 e, una volta chiuso un
ciclo, potremmo scegliere “a caso” un elemento escluso.
Nel nostro caso otterremo
4
1 32 cioè 4 1 3 che in pratica rappresenta lo stesso
ciclo di quello precedentemente trovato.
Come convenzione facciamo iniziare ciascun ciclo con il più piccolo tra i numeri presenti in esso.
5.2 – Una Particolare Permutazione: Identità
Osservazione
Esiste una particolare permutazione, quella che non sposta nulla. Questa viene chiamata
permutazione identica o identità e viene rappresentata dall’unico ciclo 1 .
Consideriamo ora due permutazioni P e Q sull’insieme A  1,2,3,4, cosa succede se applichiamo
prima P e successivamente Q?
1 2 3 4
1 2 3 4 
 e Q  
 le due permutazioni, scriviamo
3 1 2 4
1 3 2 4 
Siano P  
 1 2 3 4 1 2 3 4   1 2 3 4 

  

PQ  
 3 1 2 4 1 3 2 4   2 1 3 4 
Abbiamo trovato un’altra permutazione!
Infatti la P porta 1 in 3 e la Q porta 3 in 2 quindi possiamo dire che PQ porta 1 in 2 e così via…
Pertanto possiamo dire che la composizione di due permutazioni è ancora una permutazione.
5.3 – Permutazione Simmetrica
Dato un insieme A con n elementi indichiamo con S n l’insieme di tutte le permutazioni sugli
elementi di A; su questo insieme S n consideriamo l’operazione di composizione tra permutazioni
così come vista nell’esempio precedente. Quello che otteniamo è un gruppo con n! elementi.
Infatti come visto in precedenza l’operazione di composizione è chiusa.
Si verifica inoltre che tale operazione è associativa.
L’elemento neutro è chiaramente la permutazione identica (quella che non sposta nulla).
E’ facile infine dimostrare che è sempre possibile trovare l’inversa di una permutazione.
Infatti possiamo ottenere l'inversa di una permutazione scambiando la prima con la seconda riga
della permutazione stessa e poi riordinando gli elementi della prima riga.
Esempio (troviamo l’inversa di una permutazione)
 4 1 2 3
 1 2 3 4
 poi riordinando
 , scambiando le righe otteniamo 
2 3
 1 2 3 4
 1 2 3 4
1
 . Verificare che    1   1    1
abbiamo   
2 3 4 1
In S 4 sia   
4 1
Osservazione
Il gruppo simmetrico S n (con n  2 ) non è commutativo.
Consideriamo infatti in S 3 le seguenti permutazioni   1 2 e   1 2 3 , si ha che
   1 3 mentre     2 3 quindi       .
5.4 - L’ordine di una permutazione
Analizziamo ora cosa s’intende per “ordine di una permutazione”. Partiamo dal considerare la
seguente permutazione Q  1 4 2 . Applicandola tre volte consecutivamente, otterremo
l’identità, ovvero tutti gli oggetti torneranno nella loro posizione iniziale. Ovvero
Q 3  1 4 21 4 21 4 2  1
3
6
9
12
15
Inoltre Q  Q  Q  Q  Q      1
Volendo generalizzare questo concetto, consideriamo una permutazione come di seguito
P  1 32 6 5 . Essa è evidentemente un 2-ciclo, ove il primo è composto da due oggetti, il
secondo da tre oggetti. Se teniamo conto solo del primo ciclo, applicando la permutazione per due
volte, otterremo l’identità. Analogamente, se consideriamo solo il secondo ciclo, e applichiamo la
permutazione tre volte, saremo in presenza dell’identità. In generale comunque, se p è la
lunghezza del primo ciclo (nel nostro caso 2) e q la lunghezza del secondo ciclo(nell’esempio 3),
avremo che il mcm sarà il numero di volte che le permutazioni dovranno essere applicate per
raggiungere l’identità. E il mcm è detto “ordine della permutazione”. Per concludere, nel nostro
esempio, mcm(2,3)=6 (ordine 6). Applicando dunque 6 volte la permutazione saremo in presenza
dell’identità.
5.5 - Scomposizione in trasposizioni
Sappiamo che una permutazione è rappresentabile attraverso varie metodologie, una di queste è
quella in forma ciclica. Prendiamo la permutazione 1 2 3 . Essa può essere riscritta come
prodotto di 2-cicli, cioè come prodotto di trasposizioni, come nel seguente modo: 1 21 3 . E’
bene notare che potevamo anche scrivere 3 13 2 , ma sottolineiamo il fatto che è pur sempre
scritta come prodotto di trasposizioni, dove per trasposizione s’intende un 2-ciclo, ovvero un ciclo
contenente due oggetti. Un teorema ci dice inoltre che la parità di una permutazione dipende dal
numero di trasposizioni necessarie per la decomposizione del ciclo. Possiamo quindi enunciare la
seguente:
Definizione
Una permutazione si dice pari se si può rappresentare come prodotto di un numero pari di
trasposizioni. Altrimenti si dice dispari.
5.6 - Un sottogruppo nelle permutazioni
Soffermiamoci sull’insieme di tutte le permutazioni Sn. Esso potrà essere suddiviso in due insiemi
più piccoli disgiunti: l’insieme delle permutazioni pari e l’insieme delle permutazioni dispari. Se
cerchiamo di trovare nell’insieme delle permutazioni pari le caratteristiche del gruppo, noteremo
che tutte sono verificate. Infatti:
 Chiusura dell’operazione: la composizione di due permutazioni pari è ancora una
permutazione pari;
 Identità: è una permutazione pari, in quanto è rappresentata da zero (n. pari) trasposizioni;
 L’inversa è una permutazione ancora pari;
 L’associatività è la stessa del gruppo Sn.
Definizione
Se di (G ; *) esiste un sottoinsieme ( H ; * ) che con la stessa legge di composizione verifica le
operazioni di gruppo, esso è detto “sottogruppo”.
Il sottogruppo appena visto (permutazioni pari) si chiama gruppo alterno di grado n e si indica con
An
.
Altrettanto non può essere detto circa la composizione di due permutazioni dispari. Infatti la
composizione di una permutazione dispari con una permutazione dispari, non restituisce una
permutazione dispari. Di conseguenza, non risulta essere verificata una delle caratteristiche
necessarie affinché un gruppo sia definito tale.
5.7 Permutazioni: classe pari e dispari
Per definire la classe di una permutazione si lavora principalmente sugli oggetti della stessa.
Prendiamo ad esempio la seguente permutazione (in notazione ciclica):
(1 2 7)(3 4)(5 6)
Abbiamo che nel primo ciclo ci sono tre oggetti, nel secondo ciclo abbiamo due oggetti, e nel terzo
ed ultimo ciclo due oggetti. A questo punto dobbiamo considerare il numero di oggetti di ciascun
ciclo, quindi rispettivamente 3, 2, 2 sottraendo a ciascuno di essi l’unità 1, in modo da giungere alla
somma di 2+1+1=4.
Il risultato ottenuto, 4, risulta essere un numero positivo e di conseguenza la classe della
permutazione considerata è pari. Da sottolineare che, delle 7! Permutazioni possibili, la metà sarà
di classe pari, mentre la restante parte sarà di classe dispari.
6.0 GIOCHI APPLICATI ALLA TEORIA DEI GRUPPI
5.1 IL GIOCO DEL 15
Il gioco del quindici è un rompicapo classico inventato da Samuel Loyd nel 1878. Il gioco consiste
di una tabellina di forma quadrata divisa in quattro righe e quattro colonne (quindi 16 posizioni), su
cui sono posizionate 15 tessere quadrate, numerate progressivamente a partire da 1. Le tessere
possono scorrere in orizzontale o verticale, ma il loro spostamento è ovviamente limitato
dall'esistenza di un singolo spazio vuoto. Lo scopo del gioco è riordinare le tessere dopo averle
"mescolate" in modo casuale (la posizione da raggiungere è illustrata in bassa).
Loyd descrisse per la prima volta il suo fifteen puzzle ("rompicapo del quindici") nel volume Sam
Loyd's Cyclopaedia of 5000 Puzzles, Tricks and Conundrums, pubblicato nel 1914 dal figlio. Il
gioco ebbe sin da subito grande successo, contribuendo alla fama del suo inventore, già rinomato
enigmista e autore di altri giochi di successo. Loyd mise in palio la cifra di mille dollari come premio
per chi fosse riuscito a risolvere una versione del gioco partendo da una posizione identica a
quella finale, ma con i numeri 14 e 15 scambiati (così come si vede dall’immagine qui sotto). Un
premio che nessuno mai avrebbe potuto reclamare poiché, come l'autore sapeva benissimo, la
soluzione del gioco partendo da una tale configurazione è matematicamente impossibile.
Una generalizzazione naturale del gioco del quindici è un puzzle di
su una griglia
. Per determinare se a partire da una data configurazione C1 se ne possa raggiungere
un'altra C2 occorre calcolare le permutazioni dei numeri sulle caselle (nell'ordine di lettura): il
numero di inversioni (coppie non ordinate), deve essere pari.
GIOCO RISOLVIBILE
PARITA’ = PARI
GIOCO IRRISOLVIBILE
PARITA’ = DISPARI
5.2 - IL CUBO DI RUBIK
Si tratta di un cubo dove ciascuna faccia ha un colore diverso ed è suddivisa in 9 quadratini.
È possibile ruotare ciascuna faccia con il risultato che dopo un po’ di rotazioni le varie faccette
colorate si “disperdono” sulle varie facce del cubo. Lo scopo del gioco è quello di ripristinare
l’ordine iniziale. Basta fare poche “mosse” per trovarsi in una situazione apparentemente
irrisolvibile! Per fortuna esistono diverse tecniche per risolverlo.
È interessante anche osservare che sotto questo gioco ci sia una matematica alquanto complicata
che ha una nascita relativamente recente.
Come si fa per calcolare tutte le possibili combinazioni che il cubo può assumere?
Per calcolare le possibili combinazioni si potrebbe pensare di calcolare il fattoriale del totale delle
faccette che sono 54.
Esso è un numero enorme di 72 cifre:
54!=230843697339241380472092742683027581083278564571807941132288000000000000
Però questa stima non tiene conto dei vincoli che il cubo di rubik ha legate ai 6 cubetti centrali
che rimangono fissi dopo qualunque rotazione, ai 12 cubetti di spigolo (che hanno 2 faccette) e agli
8 di angolo (aventi 3 faccette).
Si giunge quindi a scoprire che il numero esatto di possibili configurazioni del cubo magico è :
43 252 003 274 489 856 000 (quarantatre miliardi di miliardi).
Però come abbiamo già visto per il gioco del quindici anche qui troviamo delle
configurazioni imposibili da risolvere.
Se si smonta il cubo e lo si rimonta a caso non è assolutamente certo che si ricade in una delle
posizioni possibili. Infatti esistono 12 “mondi paralleli” di configurazioni che non comunicano tra
loro, cioè se ci ritrova in uno di questi mondi non è più possibile raggiungere tramite rotazioni una
configurazione di un altro mondo. Quindi poiché la configurazione che vogliamo raggiungere è
unica (quella con tutte le facce del cubo dello stesso colore) la potremo raggiungere solo se ci
troviamo in una configurazione che appartiene al suo mondo.
Osservazione
Il gruppo di Rubik R è un sottogruppo di S 54 .
Infatti le rotazioni delle facce del cubo non sono altro che particolari permutazioni del gruppo
simmetrico su 54 elementi (quadratini colorati).
Area di progetto IIIA Informatica
A.S. 2009-2010
Studenti:
Catalano Biagio
Dargenio Ruggiero
Paciolla Andrea
Si ringraziano i docenti:
NICOLA CIRULLI che è stato il creatore di
quest’area di progetto e che ci ha seguiti
nell’ambito della matematica;
ANTONIO CRISTALLO che ha curato i
nostri lavori;
FILOMENA DI CAGNO che ha curato la
sezione “permutazioni”.
Si ringrazia:
Nicola Montrone che ha creato il gioco del
15 in VB 6.0 e il video del cubo di Rubik in
movimento.