『今週の問題』第130回　解答

【問題１】の正解は

14→11→12→8→7→6→10→12→8→7→
4→3→6→4→7→14→11→15→13→9→
12→8→4→10→8→4→14→11→15→13→
9→12→4→8→5→4→8→9→13→14→
10→6→2→1　の４４手でした。

◆京都府　としひで さんからの解答

『１５パズル』の問題

現在の配置をC、次の配置をC'とする。
初期配置から現在の配置への置換をσとおく。
配置のi行j列目の要素をA_i,jとおく。

駒を左へ移動：
s(C')=(-1)^(i+1)+jsgn(στ)=-s(C)sgn(τ)=s(C).
但しτ=(A_i,j,A_i+1,j)

駒を右へ移動：
s(C')=(-1)^(i-1)+jsgn(στ)=-s(C)sgn(τ)=s(C).
但しτ=(A_i,j,A_i-1,j)

駒を上へ移動：
s(C')=(-1)^i+j+1sgn(στ)=(-1)ⁿs(C)sgn(τ)=s(C).
但しτ=(A_i,j,A_i+1,j)(A_i+1,j,A_i+2,j)…(A_i-1,j+1,A_i,j+1)
τはn個の互換の積

駒を下へ移動：
s(C')=(-1)^i+j-1sgn(στ)=(-1)ⁿs(C)sgn(τ)=s(C).
但しτ=(A_i,j,A_i-1,j)(A_i-1,j,A_i-2,j)…(A_i+1,j-1,A_i,j-1)
τはn個の互換の積

従ってどのような移動に対してもs(C)=s(C')であることが言える。

完成図C₀に対して
s(C)=(-1)^n+msgn(π)=(-1)^n+m
但しπは恒等置換。

配置の任意の変形によってs(C)は不変であることから、可解であるための必要条件は
s(C)=C₀=(-1)^n+m。

　◆『今週の問題』第130回へ　『１５パズル』へ

　◆　今週の問題へ

数学の部屋へもどる