第3章 長方形グリッドのσゲーム 63
証明 mを固定してηに関する数学的帰納法で示す．η＝Oのとき，
P＿1（λ）＝0，片（λ）＝1より，
み（λ）＝1ん（λ）十〇み．1（λ）＝昂（λ）凡（λ）十P＿1（λ）み＿1（λ）
となり正しい．また，η＝1のとき，命題3．2．5より，
ん斗1（λ）＝λ凡（λ）十ユ凡一。（λ）＝P1（λ）み（λ）十片（λ）み一1（λ）
となり正しい．
次に，1以上のんにおいて，η≦んのとき正しいとして，η＝ん十1のと き正しいことを示す．命題3．2．5より，
片十1＋m（λ）＝λPk＋m（λ）十片＿1＋m（λ）
が成り立っているので，帰納法の仮定を用いて計算すると，
片十1＋m（λ）＝λ片十m（λ）十片＿1＋m（λ）
＝入（片（λ）み（入）十片＿1（λ）戸m＿1（λ））
十片一、（入）Pm（入）十Pト。（λ）Pm−1（入）
＝（λPk（λ）十片＿1（λ））月m（λ）
十（出一1（λ）十片一。（λ））み一1（λ）
＝片十1（λ）月m（λ）十片（入）β什1（λ）
となり，η＝ん十1のときも正しい． 口
定理3．3．2自然数んについて，
ん一。（λ）＝λ（P托．1（λ））2
が成り立つ．
証明 実際に計算して求める．定理3，3．1から，以下のように式変形がで
きる．
易κ一。（入）＝Pκ（λ）PH（入）十P先一ユ（入）Pお一。（入）
＝片＿1（λ）（片（λ）十Pk＿2（λ））
＝Pト1（λ）（λ片＿1（λ））
＝λ（片．1（λ））2
この計算の途中で，命題3．2．5を用いている、 口
第3章 長方形グリッドのσゲーム 64 定理3．3．3自然数ηについて，η＝2L1ならば，
＾（λ）＝λη が成り立つ．
証明 まず，ん＝1のとき，η＝21−1＝1で，実際にP1（λ）＝λ1であるの
で正しし、．
次にn＝2ん＿1のときのみ．1（入）＝人2L1が成り立つと仮定して，
η＝2外1＿1の場合を示す．定理3．3．2を利用して，次のように式変形で
きる．
P．1・L1（λ）＝P。．。L1（λ）
＝λ（み．。（λ））2 一λ（λ・k一・）2 ＝λ2癌十L1
となるので，η＝2k＋1＿1のときも正しい．
口 定理3．3．4自然数れについて，η＝3・2L1ならば，
＾（λ）＝λ2ム■ （λ十1）2川 が成り立つ、
証明 たに関する数学的帰納法で示す．
ん＝1のとき，η＝3・21＿1＝5であり，易（λ）＝λ易（λ）十P1（λ）＝λ3，
れ（λ）＝λ片（λ）十万（λ）＝λ4＋λ2＋！を用いると，
片（λ）＝出（λ）十易（λ）＝λ（λ4＋λ2＋1）十λ3＝λ5＋λ＝λ （λ十1）4 となり正しい．
ん≦1のとき正しいと仮定して，ん＝1＋1のとき正しいことを示す、
易．2 十1−1（λ）＝馬13．2L1（λ）であるので，定理3．3．2を用いて，次のように 式変形できる．
馬．。1＋・．、（λ）＝渇．。L1（λ）2
一λ／λ・L1（λ・！）・j＋ ／2 ＝λ・λ2 十」2（λ十1）2 十2 一λ2工十L （λ十1）2！十2
第3章長方形グリッドのσゲーム 65
となり，ん＝1＋1のときも正しい． □ 次に，λm，荷の正則性について調べる、
定理3．3．5行列λ帆は，㎜が偶数ならば正則であり，mが奇数ならば，非 正則である．
証明 λmの固有多項式戸m（λ）は
Pm（入）＝d・t（λm一畑m）
となるので，λ＝Oのときみ（O）＝det（λm）である．また，定理3．2．5よ り㌦（O）＝｛一2（O）が得られる、特に，Po（O）＝1≠0より，P2先（0）＝
片（0）≠0である．したがって，mが偶数のときλmは正則である．また，
み十1（O）＝P1（0）＝0より，mが奇数のときんは非正員1」である． 口 定理3．3．6行列一㍍は，m≡0，1（mod3）ならば正則であり，m…2（mod3）
ならば非正則である．
証明λよ＝λ、、十∬mより，λ＝1とすると，
ん（1）＝d・t（λパ五m）＝d・t（λ点）
となる。また，P、（入）＝λP、＿1（入）十P、＿2（λ）より，
片（1）＝片一i（1）十片一。（1）
を得る．これを用いて計算すると，
pκ。。（1）＝片十。（1）十片。。（1）
＝（片十1（1）十片（1））十片十1（1）
＝片（1）
となる．P1（！）＝1，P2（1）＝0なので，易（1）＝1である．したがって，
m≡0，1（mod3）のとき舳は正則であり，m…2（mod3）のときλ点
は正則でない． 口第3章 長方形グリッドのσゲーム 66
3・4 凡，、上のσゲームが解けるm，nの条件
3節で，Kerσは，Ker（片（坤））及びKer（凡（λ才））と同型であることが分 かった。また，み，、がσ可移であることの必要十分条件は，dimKerσ＝O であることもわかった．第4節では，m，ηの具体的な値によってみ，、がσ 可移かどうかを調べていく．
まず，ηを小さな値に固定して，mを変イビさせることを考える．
定理3．4．1長方形のグリッド｛，1は，m…O，1（mod3）のときσ可移で あり，m≡2（mod3）のときσ可移でない．
証明 P1（λ）＝λであるので，P1（λ点）＝λよより，P1（λ点）の正則条件は
＃の正則条件と同じである．したがって，定理3．3．6より，m…O，1（mod3）
のときσ可移であり，m≡2（mod3）のときσ可移でない． 口 定理3．4．2長方形のグリッドみ，2は，mが偶数ならばσ可移であり，㎜
が奇数ならばσ可移でない．
証明 易（λ）＝λP1（λ）十片（λ）＝λ2＋1であるので，
易（λよ）一（λよ2＋亙。）＝λ。2＋亙。十五。＝λ。2
より，片（柑）の正則条件はλm2の正則条件と同じである1したがって，定 理3．3．5よりmが偶数ならばσ可移であり，mが奇数ならばσ可移でない．
口
定理3．4．3長方形のグリッド㌦，3は，m…0，1（mod3）のときσ可移で あり，m≡2（mod3）のときσ可移でない．
証明 易（λ）＝λ片（λ）十P1（λ）＝λ3であるので，易（λ志）＝λよ3より，
乃（柑）の正則条件は狐の正則条件と同じである．したがって，定理3．3．6
より，m≡0，1（mod3）のときσ可移であり，m…2（mod3）のときσ 可移でない1 □
定理3．4．4長方形のグリッドPm，4は，m≠4（mod5）のときσ可移であり，m…4（mod5）のときσ可移でない。
第3章 長方形グリッドのσゲーム 67
証明 局（λ）＝λ4＋λ2＋1＝（λ十1）4＋（λ十1）2＋1より，んの固有多項 式とλ才の固有多項式は一致する．ここで，れ（＾）ではなくて，み（λ才）
を考える．Pm（λ才）は，m＝（m−4）十4と考えれば，定理3．3．1より，
み（λ才）＝㌦一。（λ才）れ（λ才）十孔一。（λ才）局（λ才）
となる。片（λ）はんの固有多項式であり，λ才の固有多項式でもあるから，
定理3，2，6より，月（λ才）＝0である．よって，
則州＝み一。（λ才）易（λ才）
＝み一。（λ才）・（λ才）3
となる．このことを使い，m＝5ん十5（O≦5≦4）とすると，
み（λ才）＝互（λ才）・（λ才）3κ
となる．4≡1（mod3）であるので，定理3．3．6より，（λ才）3κは正則であ る。したがって，凡（λ才）が正則であることと，P、（λ才）が正則であること は同値である．実際に計算すると，次のことが分かる．
●5＝0のとき，片（λ才）：亙4は正則である．
●5＝！のとき，P1（λ才）＝λ才は正則である．
．5＝2のとき，局（λ才）＝（λ才）2＋万4＝（λ4）2は正則である．
●3＝3のとき，易（λ才）＝（λ才）3は正則である．
●5＝4のとき，れ（λ才）＝0は非正則である．
よって，み（A才）が正則であるための必要十分条件は，m≠4（mod5）で あることである．また，m≡4（mod5）のとき，㌔（λ才）は非正則である．
口
定理3．4．5長方形のグリッド㌦，5は，mが自然数んを用いてm＝6んも しくは6ん十4と表されるときσ可移であり，そうでないときはσ可移で
なレ・．
証明 片（λ）＝λ5＋λであるので，
片（瑚＝λよ5＋λ志＝λよ（λよ4＋万。）＝側4＋亙。十五。）＝点4