ライツアウトパズルの解析：有限体上の線型代数の応用として

全文

(1) ライツアウトパズルの解析一有限体上の線形代数の応用として教科・領域教育学専攻. 自然系コース M 1 0 1 7 7 B 中原諒大. 1 研究の目的. 2 研究の内容. 本論文では数学分野の基礎である線形代数の応用，特. 本論文ではライツアウトパズルの解析をテーマとし. に行列を利用した研究について記している．. ている．ライツアウトパズルとそれに類似したパズルは. 線形代数は数学に関わる様々な分野の基礎であり，数. いくつかあるが，その中でも有名なものは5×5の格子. 学分野だけでなく，理学・工学を問わず多くの場面で応. 状に並んだライトが，ランダムに点灯または消灯してお. 用されている．つまり線形代数は数学を学ぶ上でも，活. り，そのライトに触れると，そのライトとそのライトの. 用する上でも必要不可欠なものといえる．しかし昨今，. 上下左右についているライトの点灯・消灯が切り替わる. 高校での行列の扱いは極端に縮小されている．学習指導. というルールの下，いくつかのライトに触れて全て消灯. 要領改訂により，2012年度から行列は教科「数学活用」. させることを目的としたパズルである．日本では1995. でのみ取り扱うこととなっている．しかし，r数学活用」. 年に株式会社ダカラから発売された．今では，インター. は多くの高校で開講されていなかったり，履修者がほと. ネット上に様々な類似ゲームが存在している．. んどいないことから，事実上取り扱われていないに近い．. このライツアウトパズルの構造は，初等的な線形代数. 確かに行列は線形代数の基礎であるがゆえに，高校数. の概念に置き換えることができ，ベクトル空間や行列の. 学の範囲ではどうしても計算方法に重きをおかれてし. 概念を用いて解析を行うことができる．また，本来ライ. まう．行列の計算はそれまでに習っていた計算方法と大. ツアウトパズルは長方形のグリッド状になっているも. きく違い，分かりにくい上に，その学習に面白さと意味. の（ただし，製品化されているもののほとノ）どは正方形. を見出しにくいことも否めない．それが現在のように行. のグリッド状）であるが，長方形のグリッド状に限らず，. 列の扱いが縮小されたことの理由の一端であろう．. 一般的なグラフ上でのライツアウトパズルを考察する. 筆者自身も高校で行列は学習したものの，知識として. こともできる．このライツアウトパズルを本論文上では. は計算方法を知っている程度のものであったし，大学で. σゲームという．. も線形代数を詳しく学んでこなかった．しかしながらこ. 長方形のグリッドもしくは一般的なグラフ上のσゲー. の研究を通して，線形代数・行列がどのように応用され. ムにおいて，任意の状態に対して，ある操作を加えて全. るのか，どのように便利なのか，どのような意味を持つ. て消灯した状態にすることができるとき，このグリッド・. のかなどを，身近で理解しやすい応用例を用いて，初め. グラフをσ可移であるということにする．特に長方形の. て学ぶことができた．. グリッドに関しては，そのグリッドがσ可移かどうかを. このように身近で親しみやすい題材を通した線形代. 決定するのが1つの主要なテーマである．. 数の応用として，ライツアウトパズルの解析の紹介を行. 長方形のグリッド・一般的なグラフともに各頂点に. うのが本論文の目的である．. ボタンとライトがついているものとし，ボタンには「押す」及び「押さない」という「操作」があり，ライトに. はr点灯」及び「消灯」というr状態」がある．この操作と状態をZ／2Z（＝F2）の元O，1を用いて，ボタンを押. す操作を1，押さない操作をO，ライトがついている状態.

(2) を1，づいていない状態を。と表す．lF2土の演算では，. 第2章では実際の例を提示しながら，一般的なグラフ. O＋0＝0，1＋O＝1，O＋1＝・1，1＋1＝0であり，ライ. 上のライツアウトパズルについて解析（σゲームの解析）. トが0の頂点のボタンを押すとライトが1の状態にな. を行った．各頂点に順番を付け，各頂点にボタンとライ. るといったように，これは頂点のボタンの操作とライト. トがついているものとし，ライトの状態とボタンの操作. の状態の関係性を表している．各頂点にOか1を対応さ. を1F2の元O，1と対応付けをした．さらに，それを縦に並. せる写像の全体を0Gとすると，0Gの元はグラフの状. べ，頂点の状態や操作をベクトルと同一視した．また，そ. 態を表し，同時に0Gの元はグラフのσゲームでの操作. れぞれの頂点がどの頂点とつながっているかを表す隣接. を表す．さらに0Gはベクトル空間になる．. 行列を用いて，一般的なグラフ上のσゲームを行列とベ. 今，0oの元Vを操作として，操作μを施すことを考. クトルの積に帰着させた．その結果，一般的なグラフ上. えると，〃を施す前の状態と，操作後の状態の差は砂だけ. のσゲームがどのようなときにσ可移であるかを，特性. で決まる。この状態の差をσ（μ）とすると，σ：0o→0G. 写像と呼ばれるある線型写像の全射性に帰着できるこ. が線型写像となっており，ここからσゲームの解析に線. とがわかった．さらに，いかなるグラフであっても，全て. 型写像が応用できることとなる．. のライトが点灯した状態からであれぱ，全てのライトを. 一般的なグラフ上のσゲームにおいては，主に内積や. 消灯させた状態にすることができるという定理を得た．. 直交補空間の概念を用いて，いかなるグラフにおいても，. 第3章では，本来のライツアウトパズルの形に戻って，. 適当な操作によって全ての頂点が1の状態を，全ての頂. m×ηの長方形グリッドPm，nにおけるライツアウト. 点がOの状態にすることができるという結論を得た．. パズルを考えた．この章では，長方形のグリッド上の頂. また，長方形のグリッド上のσゲームにおいては，固. 点の状態を行列と同一視して考える．ゲームのルールに. 有多項式・ケーリーハミルトンの定理・行列の正則一性な. 基づいて，各頂点の操作と状態を行列で表し，Pm，”がσ. どを用いて，このグラフがσ可移であるかどうかについ. 可移であるかどうかをmη次元のベクトル空問上の線. て考察した．. 型写像σと関係付けた．これを，ある行列の固有多項式. の計算と関係付けることにより，m次（またはη次）の. 3 論文の構成. ある行列の正則性に帰着できた．. 本稿にて得た定理の一例を挙げておく．グリッドPmη. 第1章では，体・ベクトル空間・線型写像・行列・行列. において・η：3・2比一1と表されるηに対し・Pm，、は，. 式・内積空間を定義している．本論文で扱う，ρ元体Fp. mが自然数！を用いてm＝61もしくは6正十4と表され. 係数のベクトル空間については，Fpがさまざまな点で. るときσ可移であり，そうでないときはσ可移ではない、. 実数と異なった性質を持っているので，その点に注意し. そのほか，本稿では，実際に1≦η≦11（η≠6，1O）の範. ながら定義を行った．例えば，F2土において，F2の元1. 囲で，具体的にmがどういった条件のときにPm，、がσ. は1＋1＝O及ぴ1＝一1という性質を持つ．そのため，. 可移となるのかを，行列式の計算によって求めている．. 実数係数の内積空間での正定値性のような概念はFp係. 尚，同様の研究結果として岩堀長慶氏は，Pm，。がσ可. 数のベクトル空間には存在せず，高校で学習する，2つ. 移であるかどうかを，ある種の多項式の最大公約数の計. のベクトルについて内積が0ならば，2つのベクトルは. 算に帰着している．しかしながら任意の自然数m，ηに. 直交するという概念はそのままでは意味を成さない．し. 対してPm，。がσ可移であるかどうかを，m，ηの値に. かし1F2土においても，F2nというベクトル空間内なら. よって簡単に決定する方法は，今のところみつかってい. 2つのベクトルの「直交」を形式的に定義することはで. ないようである．. きる一ただし実数係数のベクトル空間での場合のように，. 実際に90。で交わることを意味するわけではない．このように随所に実数の場合と違う点が存在しており，注. 主任指導教員濱中裕明. 意を要する．. 指導教員濱中裕明.

(3)

ライツアウトパズルの解析 ： 有限体上の線型代数の応用として

ライツアウトパズルの解析：有限体上の線型代数の応用として