2010 年度数学教育学会 夏季研究会(関東エリア)発表論文 グラフによるチャイニーズリングの視覚的構造解析 早稲田大学院教育学研究科 吉井 貴寿 [email protected] 早稲田大学 渡邊 公夫 [email protected] 概要：知恵の輪のルーツとして知られるチャイニーズリング，その構造は古くから研究されてお り，現在ではその文化的性質や二進法との関連から教材化提案もなされている．本研究はこの知 恵の輪をより優れた教材にすることを目指して始められたものであり，グラフを利用することで チャイニーズリングの構造をより明確にしたものである．また，リングの状態を全て記述し，誤 ルートやその上の頂点に着目することで新たな関係も明らかにしている． 検索語：チャイニーズリング，九連環，離散グラフ 1 はじめに 現在，チャイニーズリングの構造解析の一般 的な手法はその移動規則に着目した理論的な ものであり，漸化式あるいは二進法(またはグ レイコード)との関係から最短手数等を求める ものである．しかし、チャイニーズリングを教 材として導入した際，生徒自身がそういった関 係を見出し数学的に考察するということは難 しい．そこで，チャイニーズリングをより優れ た教材とするためにも，より段階的でわかりや すくその構造に迫るような手法が必要である と考え，グラフを用いたチャイニーズリングの 構造解析を試みた．本論文はその結果をまとめ たものであり，新たにわかった関係やより明確 化された構造について言及したものである． 2 チャイニーズリングとその先行研究 2.1 チャイニーズリングとは(添付資料 1) チャイニーズリングは図 2-1 のように，細長 い板 B に柄のついた環 C が 4~9 個はめこまれ たものであり，環の部分にはサオ A が通って いる． 問題はこの A をとりはずすことである． また，環の個数によって四連環~九連環のよう に呼ばれることもある． (図 2-1：チャイニーズリング) 2.2 チャイニーズリングの先行研究 世界的に広く知られ各国で様々な呼び名を 持つチャニーズリングであるが，その歴史は非 常に古く，発祥や作製者など不確かな点も多い． しかし，数学的にチャイニーズリングの解析を 試 み た の は イ タ リ ア の Cardano の 研 究 “De Subtilitate”(1550)が最初のようである．その後 イ ギ リ ス の J.Wallis の 研 究 “De Complicatis Annulis”(1698)があり，この段階で“解くこと が何手でできる”ということが示されていた． そして，フランスの L.Gros の研究“Théorie du baguenaudier”(1872)によって二進法応用のエレ ガントな方法が考案され，Cardano,Wallis の解 の手数が最短手数であることの証明や取りは ずしの手順までを的確にわかりやすく示すこ とが可能となった． 2.3 チャイニーズリングの仕組み まず，チャイニーズリングの環の移動規則に ついて説明する．各環(図 2-1 における Cn )は以 下の 2 つの条件を満たす場合にのみ，そのつけ はずしが可能となる． (1) Cn-2 までの全ての環がはずれている (2) Cn-1 がはまっている (＊ C1 は常につけはずしが可能) また，上記の移動規則から，以下の漸化式が成 立する．(CRn は n 連環の最短手数) CRn+2＝CRn＋1＋CRn＋CRn+1＝CRn+1＋2CRn＋1 これを解くことで CRn は次のように求まる． 2n＋1－2 n≡0 (mod 2) のとき，CRn ＝ ― 3 n＋1 2 －1 n≡1 (mod 2) のとき，CRn ＝ ― 3 また，環の状態を二進数で表現したり，グレイ コードを用いて考察したりすることで最短手 数を求めることができ，次の関係もわかる． n mod 2 ＝ 0：CRn ＝21＋23＋25＋…＋2n-1 n mod 2 ＝ 1：CRn ＝20＋22＋24＋…＋2n-1 以上が，既にわかっている主な関係である． このように，単純なグラフ化の作業をするだけ でも次のようなことがわかる．(以下，n は環の 数を表すものとする) (1) 頂点数:2n，辺数:2n－1 ⇒ いかなる状態から環をはずし始めても最 短手順ではずせば 2n－1 手を超えることは ない．(グラフの直径:2n－1) (2) n の偶･奇により，第 1 手で操作する環が異 なる． ⇒ この操作を誤ると最奥がはずせずに残る (3) n 連環を解く経路には，n－1 連環と同一の 状態が現れる．(上図 3-2 では破線枠の下部) ⇒ 帰納的に n 連環を解く経路には i 連環と同 一の状態が現れる．(1≦i≦n－1) をし，グラフの破線枠部分の位置を見ると，次 のような法則性があるように予想される． ○ n が偶数の場合： n－1 連環と同一状態が出現するのは，誤ル ートの端点と同一の深さのときである． ○ n が奇数の場合： n－1 連環と同一状態が出現するのは，誤ル ートの端点の深さ＋1 のときである． この法則性に関しては，環の移動規則と状態を 合わせて考えることで，数式で表現することが 可能となる．(以下，n 連環の最短手数を CRn とする) ○ n が偶数の場合：CRn-1 ＝ 2CRn-2＋1 ○ n が奇数の場合：CRn-1 ＝ 2CRn-2 また，これらの式は最短手数及び移動規則に関 する既存の関係式からも導出可能である． さらに，上述の関係を利用することで，以下 の(1)~(3)が言える． (1) n 連環の最短手数 CRn に関して CRn ＝ 2n－1－CRn-1 が成り立つ (2) n 連環の最短手数 CRn に関して次が成立 n が偶数：CRn ＝ 2n－1－(2CRn-2＋1) n が奇数：CRn ＝ 2n－1－2CRn-2 (3) n 連環の最短手数 CRn に関して次が成立 2n－1－CRn-1 n が偶数：CRn ＝ 2n－1－― 2 n 2 －1－(CRn-1＋1) n が奇数：CRn ＝ 2n－1－ 2 これらの 3 つは，いずれもグラフの辺の総数(2n －1)から誤ルートの辺数を除くことにより最 短手数を求めるものであり，各式の違いは誤ル ートの辺数の求め方の違いにより生じたもの である．故に，いずれの式からも正しい最短手 数を求めることができる．補足として，以下に 誤ルートの導出に関する略説をつけておく． (1)：誤ルートは 3.1 での考察(2)より，最奥の環 を残す．故にその辺数は CRn-1 で表される． (2)：上述した CRn-1 と CRn-2 の関係式を(1)に代 入することで得られる． (3)：分数で表されている部分は，全体(2n－1) から破線枠部分以降(CRn-1 または CRn-1－ 1)を除き，それを半分にしたものである． つまり，グラフを半分に折り返した際に重 なる部分の辺数を考えることで誤ルート の辺数を導出している． 3.2 誤ルートへの着目 前節(2)の観点から，n の偶・奇による場合分 4 超立方体グラフによる考察 4.1 n 次元超立方体グラフ 3 チャイニーズリングのグラフ化 3.1 グラフ化 本章では，グラフを用いてチャイニーズリン グの構造を探る．そのために，まずリングの各 状態を二進表示に対応させて簡易的に記述す る．今回，はずれている環を 0，はずれていな い環を 1 と表し，チャイニーズリングの先端は 常に右にあるものとする．つまり，1 番目の環 は二進表示の 1 桁目に対応する． (図 3-1：リングの状態と二進数の対応) 四連環の横図 簡便図 二進表示 ここで、これらの二進表示されたリングの各 状態を頂点とし，1 手(1 つの環の移動)で変換 可能な頂点のみを辺で結んだグラフを作成す る．これにより，チャイニーズリングの構造が グラフ化されることとなる．(添付資料 2) (図 3-2：四連環の状態のグラフ) 1010 1110 ― 1001 1011 1000 1111 1100 1101 0101 0100 0110 0111 0000 0011 0010 0001 前章でのグラフ作成方法及び作成されたグ ラフの性質から，さらなる解析手法として n 次元超立方体グラフ Qn の使用が考えられる． n 次元超立方体グラフ Qn とは n 桁の 2 進数を 頂点とし，1 つの桁を除けば全ての桁の数が等 しい頂点間に辺を与えたものである．これによ り定義される Q3 は以下のようになる． 000 001 101 100 010 011 110 111 これが，立方体グラフの名前の所以であり，こ れを n 次元に拡張したものが超立方体グラフ である．今後は，その拡張のしやすさから以下 のような同型なグラフをベースに考えていく． 000 110 010 001 011 100 101 111 また，その定義から n 連環のグラフが n 次元超 立方体グラフ Qn の全域部分グラフとなること がわかる．これは，チャイニーズリングの構造 がグレイコードにより説明可能であること．ま た，超立方体グラフの構造がグレイコードの構 造を内包していることからも明らかである． 今回、初期状態から環を全てはずすまでの最 短ルートを二重線と白抜き頂点で示し，誤ルー トを黒の実線と黒色頂点で示した．また，それ 以外の Qn の辺は，黒の破線で表している．(添 付資料 3) (図 4-1：四次元超立方体グラフ) グラフの黒色頂点に着目する．すると，ある 種の規則性を持って集合しているように見て 取れる．そもそも，黒色頂点は誤ルート上の点 であり，誤ルートは初手の分岐に依存した 1 本の道しか持っていないためこのような状態 になっているといえる．そこで，黒色頂点の配 置にどのような法則性があるのかを環の移動 規則ではなく，超立方体グラフの構造面から考 えてみる．ここでいう超立方体グラフの構造と は Qn のグラフに 2 つの Qn-1 のグラフが部分グ ラフとして含まれているということである．こ の構造が帰納的に働くため，n 次元超立方体グ ラフは適当に半分に分割していくことで，n－1 次元以下の超立方体グラフの集合として考え ることができる．したがって，この構造に着目 し，グラフを分割していくことで黒色頂点の配 置規則を探ることにした．そこで見えてきたの が以下の関係である．(以下，n 連環の誤ルート 上の頂点(黒色頂点)を BVn と表す．また，CRn はひきつづき n 連環における最短手順として 扱う) n が偶数：BVn＝20＋22＋24＋･･･＋2n-2 n が奇数：BVn＝21＋23＋25＋･･･＋2n-2 ここで，BVn は誤ルート上の頂点数であるから， その数は誤ルートの辺数に等しい．また，前述 したように誤ルートの辺数は CRn-1 に等しい． 故に，BVn ＝ CRn-1 が成り立つので n が偶数：CRn-1＝20＋22＋24＋･･･＋2n-2 n が奇数：CRn-1＝21＋23＋25＋･･･＋2n-2 と変形でき，この式は既知の関係式と等しい． また，この結果を利用すれば，最短手数 CRn を次のように表すことも可能となる． n が偶数：CRn＝2n－(20＋22＋24＋･･･＋2n-2)－1 n が奇数：CRn＝2n－(21＋23＋25＋･･･＋2n-2)－1 5 ここで，二重線の最短手順のみをみればその中 に，CRn+2 ＝ CRn+1＋2CRn＋1 などの既知の関 係を見て取ることもできる(CRn は n 連環にお ける最短手数)． 4.2 頂点への着目 おわりに 本研究ではグラフを使用しリングの移動を 全て記述したことで，チャイニーズリングの構 造の全体像が明らかとなった．また，今まで着 目されてこなかった誤ルートをも考察したこ とにより新たな関係も明らかとなった． 今後は，これらの研究結果もふまえた上で， チャイニーズリングの教材としての可能性を 考えていく予定である． 6 参考文献(一部) 松田 道雄 『パズルと数学』 明治図書 1958 一森 哲男 『グラフ理論』 共立出版 2002 グラフによるチャイニーズリングの視覚的構造解析(資料) ～ 資料 1 ～ ～ 資料 3 ～ ① 0 連環 ② 1 連環 ③ 2 連環 ～ 資料 2 ～ ① 0 連環 φ 0 連環はリングが無い状態であるから明らか に 1 つの孤立点からなるゼログラフである。 (ここでは、1 連環と区別するためにリングの 状態をφで表記している) ④ 3 連環 ② 1 連環 1 0 ③ 2 連環 ⑤ 4 連環 10 11 01 00 ④ 3 連環 110 010 011 001 000 111 101 100 ⑤ 4 連環 ⑥ 5 連環 1010 1001 1110 1011 1000 1111 1100 0101 1101 0110 0100 0111 0000 0011 0010 0001 ⑥ 5 連環 11110 11010 11001 11011 01000 11000 01011 01001 01110 01010 01101 01111 11111 11100 11101 10101 10100 10110 10111 10011 10010 10000 10001 00100 01100 00111 00101 00010 00110 00001 00011 00000
© Copyright 2024 ExpyDoc
