Side 2 - Endelig gruppe

Ja, selvom det ikke umiddelbart virker sådan, se er grafen todelt. Lad os til eksempel nummerere de 16 felter i puslespillet som på nedenstående figur

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Punkterne forbindes med kanter, således at ethvert punkt er forbundet med en kant til ethvert punkt over, under, til højre og til venstre for sig selv (hvis de findes). Jeg har med vilje ikke tegnet disse kanter, da det kommer til at se noller ud. Kanterne repræsenterer bevægelsesmulighederne for det tomme felt.

Denne graf er todelt, fordi hvis punkterne inddeles i de to mængder

A = {1,3,6,8,9,11,14,16}

B = {2,4,5,7,10,12,13,15}

så forbinder enhver kant i grafen et punkt i A med et punkt i B og der er ingen kanter punkterne imellem indenfor hver af de to mængder.

Med hensyn til metoder, så kan i sagtens gribe sagen an som du foreslår. I kan så bare med en placering betegne en distribution (permutation) af de 15 brikker + det tomme felt på de 16 celler. Disse placeringer vil faktisk falde i ækvivalensklasser med 16 placeringer (permuteringer) i hver, thi indenfor hver permutering er det ligegyldigt hvor det tomme felt er - det er samme permutering. Med et punkt betegner i så blot en repræsentant fra hver af disse ækvivalensklasser - som vi passende kan kalde en konfiguration, og grafen fremkommer ved at forbinde alle de punkter, hvor man kan komme fra det ene punkt (konfiguration) til det andet ved hjælp af en legal flytning af det tomme felt.

Der gælder der helt generelle resultat, at enhver (ikke-separabel) todelt graf har netop to sammenhængende delgrafer. Den ene svare til lige, den anden til ulige permutationer. Det vil sige, starter man ud med en konfiguration i den ene delgraf, så kan man aldrig komme over i en konfiguration i den anden delgraf.

Som nævnt er puslespillets gruppe A_15. Det betyder, at givet to placeringer p1 og p2 hørende til konfigurationerne c1 respektive c2, så kan p2 fremkomme af p1 hviss c2 er en lige permutation af c1.

Så ja, det er kun halvdelen af konfigurationerne, der er løsbare. Faktisk tror jeg at spillet i sin oprindelig udformning var uløseligt. Jeg mener, jeg engang læste sjove historier om folk der var ved at blive sindssyge af forgæves at skubbe brikker rundt da spillet kom frem engang i ruder konges tid.

Ahh... Nu kan jeg se, hvordan din graf bliver todelt.

Tak, fordi du gider hjælpe! :) Det er virkelig rart at læse dine indlæg, da det giver en dybere forståelse for, hvad vi kommer til at arbejde med senere i projektet.

Tror egentlig du har ret i, at puslespillet var uløseligt i sin oprindelige form. Det var noget med, at 15 og 14 vist var byttet om, men ellers var alle brikkerne placeret, som du også skriver. På den måde kunne det aldrig lade sig gøre at få 15 og 14 byttet tilbage igen.


Jeg har faktisk et "lille" spørgsmål:

Permutationsgruppen for X, hvor X={1,...,n} betegnes S_n og kaldes den symmetriske gruppe af grad n.

Hvorfor er gruppen symmetrisk?
Hvad vil det sige, at en gruppe er symmetrisk?

#22:
At en gruppe af grad n er symmetrisk betyder blot, at der netop er tale om gruppen af _samtlige_ permutationer af de n symbolet; altså er det bare definition på en symmetrisk gruppe, jævnfør http://mathworld.wolfram.com/SymmetricGroup.html.

Som antydet i #23 er 'symmetrisk' ikke en egenskab ved en gruppe. Det er en samlebetegnelse for en bestemt type grupper.

Den symmetriske gruppe fremkommer på følgende maner: Lad X være en vilkårligt ikke-tom mængde. Betragt nu mængden S_X af alle bijektive afbildinger af X på sig selv og forsyn S_X med kompositionen 'funktionssammensætning'. Da bliver S_X en gruppe [hvilket jeg vil overspringe beviset for her], og man kalder den for en symmetrisk gruppe.

Den symmetriske gruppe af grad n er et specialtilfælde som fremkommer ved at lade mængden X være en endelig mængde X = {1,2,3,...,n} og S_X bliver da netop mængden af samtlige permutationer af tallene 1,..,n i X. Man betegner da S_X som S_n. Den kaldes den symmetriske gruppe af grad n.

En permutering (bijektiv afbilding, altså et element i S_X resp. S_n), som kun ombytter to elementer, kaldes en transposition. Enhver permutering kan skrives som et produkt (og produktet - kompositionsreglen - i gruppen er altså funktionssammensætning) af enten et lige eller et ulige antal transpositioner. Da gruppen således både indeholde lige og ulige permuteringer, kaldes den symmetrisk. Modsat den alternerende gruppe, der kun indeholder de lige permuteringer.

Mange tak for svarene til jer begge!

Det var egentlig ikke vanskeligt at forstå :)