« Gruppteoretisk lösning av M12 puzzle i GAP | Main | Bloggträff i Malmö nu på lördag 5 juli (2008) »

juni 30, 2008

Gruppteoretisk lösning av M12 puzzle i GAP - take 2

I går skrev jag Gruppteoretisk lösning av M12 puzzle i GAP och publicerade ett GAP-program för att lösa M12 puzzle (för övriga länkar, se gårdagens skrift).

Efter lite mer funderande har jag nu kommit på en mer elegant lösning där man inte behöver göra inverse (^-1) på själva pusslet, och att man inte behöver arbeta baklänges. Den förra lösningen var inte felaktig, endast bökig.


Det som ändrades var helt enkelt hur man definierar merge-operatorn. Den är nu

merge:=PermList([1,3,5,7,9,11,12,10,8,6,4,2]);


Här är den nya GAP-koden och med ett nytt pyssel.


#
# GAP program for solving the M12 puzzle.
#

#
# The two operations M (Merge) and I (Reverse, Inverse)
#
merge:=PermList([1,3,5,7,9,11,12,10,8,6,4,2]);
reverse := PermList([12,11,10,9,8,7,6,5,4,3,2,1]);
g:=Group([reverse2, merge2]);

puzzle := [5,4,10,8,11,12,6,2,3,9,1,7];

#
# Solve the puzzle:
# x1 = I (inverse)
# x2 = M (merge)
#
# Notation: x2^-3 = x^(11-3) = x^8 = M8
#
Factorization(g, PermList(puzzle));

#
# End of GAP code
#

Notera att man inte behöver göra inverse på PermList(puzzle);

Lösningen på detta är

x1*x2*x1*x2^2*x1*x2*x1*x2^-5*x1

Denna lösning kan man alltså följa från början, och motsvarar följande operationer i M12-pusslet. Notera att x2^-5 är - som tidigare - samma som x^(11-5) = x^6 = M6.


I M I M2 I M I M6 I

Som jämförelse använder vi även den andra metoden som inte garanterar någon kort faktorisering:


#
# A variant
# R: = I
# M = M
#
hom:=EpimorphismFromFreeGroup(g:names:=["R","M"]);
PreImagesRepresentative(hom,PermList(puzzle));

Lösningen är

M*R*M^-2*R*M^-4*R*M^-1*R*M*R*M^3*R^-1*M^-1*R^-1*M^-4*R^-1*M*R^-1*M^-1*R*M^-1

Vilket alltså motsvarar M12-operationerna:

M I M9 I M7 I M10 I M I M3 I M10 I M7 I M I M10 I M10

Denna lösningen är också betydligt längre.


Jaha, så kan det gå när man vill publicera något innan EM finalen i fotboll...

Posted by hakank at juni 30, 2008 07:22 EM Posted to