GAP による15ゲームの解法

目次へ

GAP による15ゲームの解法   TyK   平成21年9月9日 をグーグルで見つけた。この論文について GAP と Mathematica を使って読み解くことにする。

1. 問題設定

  • 関数findPermutationReplaceを使って配置p0からgameへの巡回置換cycleを求める。
  • 関数permutationSignatureを使って偶置換であることを調べる。
  • 求めた巡回置換を基本配置p0に作用させgameを求めて確認する。

 

2. IS の決定

30個の3項巡回置換のから生成した群は位数15の交代群A15になることを示している。何故このような 30個の3項巡回置換を選ぶのか分からない。今後の課題である。

gap> IS := Group((1,2,6),(6,5,1),(5,1,2),
> (2,3,7),(3,7,6),(7,6,2),(6,2,3),
> (3,4,8),(4,8,7),(7,3,4),
> (5,6,10),(6,10,9),(10,9,5),(9,5,6),
> (6,7,11),(7,11,10),(11,10,6),(10,6,7),
> (7,8,12),(8,12,11),(12,11,7),(11,7,8),
> (10,14,13),(14,13,9),(13,9,10),
> (10,11,15),(11,15,14),(15,14,10),(14,10,11),
> (11,12,15));
<permutation group="" with="" 30="" generators="">
gap> Size(IS);
653837184000
gap>  (1,3,7,11,9)*(2,4,8,14,13,5)*(10,15) in IS;

GAP で求めた生成群を Mathematica で確認している。

3. 15ゲームの解法の決定

gap> GetWordOfElements:=function(G,GenName,x)
>   local gen,F,hom;
>   gen:=GeneratorsOfGroup(G);
>   if Size(GenName)<>Size(gen) then
>     F:=FreeGroup(Size(gen));
>   else
>     F:=FreeGroup(GenName);
>   fi;
>   hom:=GroupHomomorphismByImagesNC(G,F,gen,GeneratorsOfGroup(F));
>   return Image(hom,x);
> end;
function( G, GenName, x ) ... end
gap> 
gap> p := GetWordOfElements(IS,
> ["(1,2,6)","(6,5,1)","(5,1,2)",
> "(2,3,7)","(3,7,6)","(7,6,2)","(6,2,3)",
> "(3,4,8)","(4,8,7)","(7,3,4)",
> "(5,6,10)","(6,10,9)","(10,9,5)","(9,5,6)",
> "(6,7,11)","(7,11,10)","(11,10,6)","(10,6,7)",
> "(7,8,12)","(8,12,11)","(12,11,7)","(11,7,8)",
> "(10,14,13)","(14,13,9)","(13,9,10)",
> "(10,11,15)","(11,15,14)","(15,14,10)","(14,10,11)",
> "(11,12,15)"],(1,3,7,11,9)*(2,4,8,14,13,5)*(10,15));
(5,1,2)^-1*(1,2,6)^-1*(7,6,2)^-1*(1,2,6)^-1*(5,6,10)^-1*(3,7,6)^-1*(7,11,10)*(\
3,4,8)*(3,7,6)^-1*(6,5,1)*(6,10,9)*(1,2,6)*(10,11,15)*(5,6,10)^-1*(10,14,13)*(\
5,6,10)

gap> p^-1;
(5,6,10)^-1*(10,14,13)^-1*(5,6,10)*(10,11,15)^-1*(1,2,6)^-1*(6,10,9)^-1*(6,5,1\
)^-1*(3,7,6)*(3,4,8)^-1*(7,11,10)^-1*(3,7,6)*(5,6,10)*(1,2,6)*(7,6,2)*(1,2,6)*\
(5,1,2)
gap> 

GAP で求めた手順を Mathematica で確認する。行列表現から完成に至る手順を読み取ることができる。

手順の逆の確認。

4. まとめ

  • GAP による解法を確認した。
  • GAP による解法をMathematica を使って確認した。

目次へ