しいたけアラカルト

  1. トップ
  2. ゲーム
  3. カラムサイクルパズル
  4. カラムサイクルパズルが解けるかどうかの考察

カラムサイクルパズルが解けるかどうかの考察

まずはじめに注意事項として(*)がついている定理などは私が考察の途中に考えたものなので 証明どころかステートメントさえ間違っている可能性があります。ですのですぐに信用するのではなく注意深く読んでください。
以下やや横柄な文体になります。

まず説明するにあたって説明の便宜上いくつかの用語を定義する。
まず、x行y列の位置を\((x,y)\)と座標のように表す。次に元の位置が\((x,y)\)であるタイルを\( T(x,y) \)で表す。 さらにx行を右に1つずらす変換を\(R(x)\)、y行を下に1つずらす変換を\(C(y)\)で表すものとする。 また位数nの置換群を\(P_n\)、位数nの交代群を\(A_n\)で表すものとする。 数列\(x_1,x_2,x_3,\cdots,x_n\)に対し\(S(a,b)\)でa番目の数をa+1番目に、…b-1番目をb番目に、b番目の数をa番目に持ってくるような変換とする (つまりa番目からb番目までの数を右にずらし、最後の数を最初に持ってくるような変換である。)。 また\(< S(a,b),S(a,b)>\)で\( S(a,b),S(a,b)\)の変換とその逆変換たちを合成させてできる変換の集合とする。 さらに\(S(a,b)\)において\(b - a + 1\)を\(S(a,b)\)の長さと呼ぶことにする。

これから示そうとしているのは次のことである。

命題A\(^{(*)}\) カラムサイクルパズルはタイルの数が偶数個の場合は任意の置換、タイルの数が奇数の場合は任意の偶置換で元のタイルの配置を変えたもののみが解ける。

まずb行a列のカラムサイクルパズルにおいて下のような操作によりb行とa列以外はすべて元の配置にもどすことができる。そのような状態を配置Lと呼ぶことにする。

\(x = 1 , y < b\)であり \( T(1,1) \)から\( T(x - 1,y) \)まで元の位置に配置されている場合、 、\( T(x,y) \)を\(R(x)\)を繰り返し行うことでa列まで持ってくる。 次に\(C(y)\)を適当に行うことで\( T(x,y) \)をb行まで持っていく。 最後に\( T(x,y) \)を\(R(x)\)を繰り返し行うことでx列まで持っていくことで\( T(1,1) \)から\( T(x ,y) \)まで元の位置に配置されている状態になる。
次に、\(2\le x < a , y < b\) であり \( T(1,1) \)から\( T(x - 1,y) \)まで元の位置に配置されている場合、 \( T(x,y) \)を\(R(x)\)を繰り返し行うことでa列まで持ってくる。 次に\(C(y)\)を適当に行うことで\( T(x,y) \)をb-1行まで持ってくる。 \( T(x - 1,y) \)を\(R(x)\)を繰り返し行うことでa - 1列まで持ってくる。 \(C(y) ^{-1}\)を行うことで\( T(x,y) \)をb行に持ってくる。 \( T(x,y) \)を\(R(x)\)を繰り返し行うことでx列まで持っていく。 そうすることで\( T(1,1) \)から\( T(x ,y) \)まで元の位置に配置されている状態になる。 このような操作を\(T(b-1,a -1)\)の操作が完了するまで続けると配置Lとなる。 (操作の説明終わり)

配置Lにおいて\(C(a)\)と,\(R(b)\)の変換のみで元配置へ戻すことができれば命題Aは示されたことになる。 これはすなわち次の問題となる。

問題B\(^{(*)}\)  \(1,\cdots , a + b - 1 \)の置換群を\( P\)とする。また交代群を\( A\)とする。 群\( G = < S(1, a) , S(a , a + b - 1) > \)において、
\( a \cdot b \)が偶数のときは \( G = P\)、
\( a \cdot b \)が奇数のときは \( G = A\)となる。

まず次の捕題を示そう。

補題1\(^{(*)}\) 長さが4以上の\(\rho = S(1 , n) , \sigma = S(n , m) \)で生成される群\( G = < (S(1 , n) , S(n , m)> \)において、 \( S(3, n) \in G \)となる。

(証明) \( S(3 , n) = \rho^2\sigma^{-1}\rho\sigma\rho^{-1}\sigma^{-1}\rho^{-1}\sigma\rho\sigma^{-1}\rho^{-1}\sigma \in G \)  //

この補題から次の命題が導かれる。

命題2\(^{(*)}\) 長さが4以上の\( \rho = S(1 , n) , \sigma = S(n , m) \)で生成される群\( G = < \rho , \sigma > \)において、
\( n\)が偶数ならば \( S(n - 1 , n)\in G \)
\( n\)が奇数ならば \( S(n - 2 , n) \in G \)

(証明)  補題1から\( S(3 , n) \in G \)。
そこで\( \rho_3 = S(3 , n) \)として 群\( G_3 = < \rho_3 , \sigma > \)を考える。
この\( G_3 \)に対して再び補題1を用いることで\( S(5 , n) \in G_3 \)となり、これにより\( S(5 , n) \in G \) である。 これを繰り返すことで上の命題は導かれる。//

さらに次の命題が成り立つ。

命題3\(^{(*)}\) \( \rho = S(1 , n) , \sigma = S(n , m) \)で生成される群\( G = < \rho , \sigma > \)において、 任意の\( a_1,a_2,\cdots,a_n \in \{1 , 2, \cdots,n\} \)に対して \( \tau(1) = a_1, \ \tau(2) = a_2, \cdots, \ \tau(n) = a_n\)
となる\( \tau\in G \)が存在する。

(証明)簡単なので省略。//

系4\(^{(*)}\) \( \rho = S(1 , n) , \sigma = S(n , m) \)で生成される群\( G = < \rho , \sigma > \)において、 \( \tau(1) = 1, \ \tau(2) = 2, \cdots, \ \tau(n) = n\)
となる\( \tau\in G \)が存在する。//

この命題2と系4から問題Bは次の3つのパターンに帰着される。
(1)偶数 * 偶数のカラムサイクルの場合は\(< S(1,2),S(2,3)>\)が置換群\(P_3\)と一致すれば問題Bが成り立つ。
(証明)\(< S(1,2),S(2,3)>\)が置換群\(P_3\)と一致するのは明らか。
(2)奇数 * 偶数のカラムサイクルの場合は\(< S(1,3),S(3,4)>\)が置換群\(P_4\)と一致すれば問題Bが成り立つ。
(証明)命題3により任意の\(a_1,a_2\)に対して\(\rho(1) = a_1 , \rho(2) = a_2\)となる\(\rho \in< S(1,3),S(3,4)>\)が存在する。 残りの2つの要素も互換で交換できるから\(< S(1,2),S(2,4)>\)に全ての置換が含まれている。
(3)奇数 * 奇数のカラムサイクルの場合は\(< S(1,3), S(3,5)>\)が交代群\(A_5\)と一致すれば問題Bが成り立つ。
(証明)上と同様に命題3により任意の\(a_1,a_2\)に対して\(\rho(1) = a_1 , \rho(2) = a_2\)となる\(\rho \in< S(1,3),S(3,4)>\)が存在する。 \(a_1,a_2\)の選び方は20通り。 上と同様、残りの3つの要素は巡回させることで3通りの並び方を作ることができる。 \(< S(1,3),S(3,5)>\)の位数は60以上であることが分かる。 しかし1,2,3,4,5の交代群\(A_5\)の位数は60であり\(< S(1,3),S(3,5)>\)は\(A_5\)の部分群であるから、 \(< S(1,3),S(3,5)>= A_5\)となる。

これにより命題Aは示された。

広告

戻る