1東北大学オープンキャンパス 2007 数学クイズ解答(kuroki@math.tohoku.ac.jp)

黒木玄＠東北大学大学院理学研究科数学専攻

1あみだくじ
12345123451234512345

図 1: あみだくじの例

図 2: あみだくじのたどり方

まずあみだくじ (阿弥陀籤) について復習しよう. たとえば図 1 のあみだくじで 2 番を選んだ人は図 2 のようにあみだくじをたどらなければいけない. 2 番を選んだ人は 5 番にたどり着くことになる. 他の番号を選んだ人は他の番号にたどり着く. 実際に図 1 のあみだくじをたどってみると, 1, 2, 3, 4, 5 番を選んだ人はそれぞれ 3, 5, 2, 1, 4 番にたどり着くことがわかる (実際にそうなることを確かめよ).
不思議なことにどのようなあみだくじであっても異なる番号を選んだ人は異なる番号にたどり着くことになる. たどり着く先に重複が生じることはない. (たとえば 3 番を選んだ人と 5 番を選んだ人が同じ場所にたどり着くことはない.)
問題 1 任意のあみだくじでたどり着く先に重複が生じない理由を説明せよ.
ヒント. 横線を複数本持つあみだくじは横線を一本しか持たないあみだくじの積み重ねでできている.
解答. 横線が一本しかない場合. i 番目と i + 1 番目の縦線のあいだに横線が一本だけしかないあみだくじは i 番目の縦線と i + 1 番目の縦線だけを交換する置換を与えることはすぐにわかる. (置換の定義ついては以下を見よ.)
横線が複数ある場合. 各々の横線はそれが繋いでいる隣り合った縦線を交換する置換を与えている. したがって複数の横線で構成されたあみだくじ全体は隣り合った縦線を次々に交換することによって作られた置換を与えていることがわかる. (図 3, 図 4 も参照せよ.)
一般に番号 1, 2, . . . , n のそれぞれを重複無しに番号 1, 2, . . . , n のどれかに対応させる
規則を n 次の置換 (permutation) と呼ぶ.
あみだくじではたどり着く先に重複が生じない. したがって n 本の縦線を持つ任意のあみだくじは n 次の置換を与えている.

2
たとえば図 1 のあみだくじは 1, 2, 3, 4, 5 をそれぞれ 3, 5, 2, 1, 4 に対応させる置換を与えている. このような置換を σ = ( 1234535214 ) と書く約束になっている. 一般に 1, 2, . . . , n··· nのそれぞれを i1 , i2 , . . . , in に対応させる置換は σ = ( i11 i22 ···in ) と表わされる.

¡¢n−2 n−1 n
問題 2 1, 2, . . . , n のうち 1 と n だけを交換する置換 σ = n1 22 33 ······ n−2 n−1 1 を与えるあみだくじで横線の本数が 2(n − 2) + 1 本 (よって特に奇数本) であるものを作れ.
ヒント. あみだくじの横線は隣り合った番号の交換を与えている. 隣り合った番号の交換の繰り返しで 1 と n だけを交換するにはどのようにすればよいか? 縦線の本数がn = 2, 3, 4, 5, 6 の場合について考えてみよ. 問題 3 のヒントも参照せよ.
解答. n = 6 の場合はたとえば図 3 のあみだくじが 1 と n だけを交換する置換を与えている. 他の n についても同様の形のあみだくじで 1 と n だけを交換するあみだくじを作れる. (正解はこれだけではない.)

123456123456123456123456図 3: 1 と 6 だけを交換する置換を与えるあみだくじ

問題 3 任意の置換に対してそれを与えるあみだくじを作れることを示せ.
ヒント. 置換をひもで表現し, あみだくじに変形する方法を考えよ.
解答. たとえば置換 σ = ( 123312 ) に対しては図 4 のようにしてあみだくじを作ればよい. 任
意の置換に対しても同様にしてそれを与えるあみだくじを作れる.

123123123123123123

図 4: 置換を与えるあみだくじの作り方

3問題 4 偶数本の横線を持つあみだくじが与える置換と奇数本の横線を持つあみだくじが与える置換は決して一致しないことを証明せよ.
ヒント. その辺にいる数学科の学生もしくは大学院生に質問してみよ.
解答. 大学に入学すれば 1 年生のときに線形代数の授業で教わることになる. 以下のキー
ワードをインターネットで検索してみよ:
置換群, 対称群, 偶置換, 奇置換, 符号, あみだくじ, あみだ籤, 阿弥陀籤.
線形代数の教科書としては個人的に [佐武] と [長谷川] がおすすめである. 他にも良書がたくさん存在する. 偶置換・奇置換および置換の符号に関する解説は [佐武] の p.44 付近と [長谷川] の付録 2 にある.

2十五パズル
あみだくじと置換の理論を十五パズルに応用することができる.

123412345678567891011129101112131415131514

図 5: 十五パズルの初期配置

図 6: 初期配置から 14 と 15 だけを交換した配置問題 5 十五パズルにおいて初期配置 (図 5) から 14 と 15 だけを交換した配置 (図 6) に持って行けないことを示せ. (あみだくじに関する問題の結果を認めて使ってよい.)
ヒント. 1. 空いているマス目に数 16 を対応させることにすれば, 十五パズルの配置と 16次の置換 σ が自然に一対一に対応する. 以下, 十五パズルの配置と 16 次の置換 σ を同一視する. (たとえば図 5 の初期配置と 1, 2, . . . , 16 のそれぞれをそれ自身に対応させる置換ε (単位置換と呼ばれる) が同一視され, 図 6 の配置と 1, 2, . . . , 14, 15, 16 の うち 14 と 15だけを交換する置換 τ が同一視される.)
2. 十五パズルにおいて許される操作は空いているマス目の上下左右のタイルをすべらせて空いているマス目に移動するという操作 (この操作を以下基本操作と呼ぶ) の繰り返しだけである.
3. 問題 3 の結果より, 任意の置換 σ に対してそれを与えるあみだくじが存在する. 問
題 4 の結果より, その横線の本数 k の偶奇は置換 σ だけで決まり, あみだくじの選び方によらない. よって (−1)k という数は置換 σ を与えるあみだくじの取り方によらずに定まる. そこで (−1)k を置換 σ の符号 (signature) と呼び, sgn(σ) と表わす. (たとえば図 6の配置に対応する置換 τ は 14 番目と 15 番目の縦線のあいだに横線が一本しかないあみだくじで表現できるので sgn(τ ) = −1 となる.)

4
4. 十五パズルの任意の配置 σ に基本操作を加えたものを σ 0 とすると sgn(σ 0 ) = − sgn(σ)となる. すなわち基本操作で sgn(σ) は −1 倍に変化する. (証明. 基本操作は空いているマス目に対応する番号 16 とその上下左右にあるタイルの番号 m だけを交換する置換 ρに対応している. 問題 2 の結果より置換 ρ は奇数本の横線を持つあみだくじで与えられることがわかる. 置換 σ 0 を与えるあみだくじは置換 σ を与えるあみだくじの下に置換 ρ を与えるあみだくじを連結することによって作れる. このことから置換 σ 0 を与えるあみだ
くじの横線の本数は置換 σ を与えるあみだくじの横線の本数に奇数を足したものになる.
このことから sgn(σ 0 ) = − sgn(σ) となることがわかる.)
5. 十五パズルの配置 σ において, 空いているマス目 (16 が対応) の位置が左上スミから数えて右に i 番目下に j 番目の位置にあるとき, p(σ) = (−1)i+j と置く. (たとえば初期配置 (図 5) における 7 の位置に対応する (i, j) は (3, 2) なので空いているマス目が初期配置の 7 の位置にあるとき p(σ) = (−1)3+2 = −1 となる.)
6. 基本操作で p(σ) はどのように変化するか?
7. f (σ) = sgn(σ)p(σ) と置く. たとえば図 5 の初期配置 ε に対して f (ε) = 1 となり, 図6 の配置 τ に対して f (τ ) = −1 となる. よって f (ε) 6= f (τ ).
8. 基本操作で f (σ) はどうなるか? 変化するか?
解答. 6. 基本操作で i と j の片方のみの偶奇が変化する. よって基本操作で p(σ) は −1倍に変化する.
8. 上の 4, 6 の結果から, 基本操作で f (σ) は変化しないことがわかる.
したがって 2 と 7 の結果より, 十五パズルで許された操作で図 5 の初期配置を図 6 の配置に持って行くことは不可能である.
問題 6 上の問題の続き. p(σ) の値が互いに等しい十五パズルの配置は十五パズルで許された操作で互いに移り合うことを証明せよ.
証明の方針. 次のような証明の方針が文献 [ITM] の第 3 章の終わりにある. 空いているマス目を初期配置と同じ場所に移動することによって 15 次の交代群 (符号が 1 であるような14 15置換全体のなす群) の問題に帰着される. 15 次の交代群は位数 15 の巡回置換 ( 12 23 ······ 15 1 )12 13 14 15と位数 3 の巡回置換 ( 11 ······ 12 14 15 13 ) から生成されることを示せる (少し面倒). よってこの 2 つの置換を十五パズルでも実現できることを示せばよい. (詳しい解答は略する.)
文献 [ITM] は現代数学入門としても優れた良書である. オープンキャンパスの帰りに見付けたら購入しておいても損がない.

参考文献[佐武] 佐武一郎: 線型代数学, 裳華房数学選書 1, 324 頁.
[長谷川] 長谷川浩司: 線型代数 Linear Algebra, 日本評論社, 390 頁.
[ITM] 今井淳, 寺尾宏明, 中村博昭: 不変量とはなにか―現代数学のこころ―, 講談社ブルーバックス B1393, 2002 年, 246 頁.