1.ハノイの塔
これは昔からある有名なハノイの塔という数理ゲームで、商品として販売されているものも数多くあります。
パズルのルールは、3つの柱があり、1つの柱に円盤が何枚か刺さっています。これを他の柱に移動するのですが、小さい円盤の上には大きい円盤をのせてはならないという制約のもと、円盤を動かして、他の柱に全ての円盤を移動するというパズルです。数列の分野では漸化式の具体例として扱われることが多いです。
今回はこのパズルを、表計算ソフトExcelでゲームが楽しめるようにプログラミングし、それを用いてPC室で生徒全員がゲームを楽しみながら授業を行いました。初めは生徒は大変夢中になり、移動回数には関係なくとにかく移動できることを目標に取り組みました。次にすべての円盤を移し終わる最小手数をクラス全員で競いながら求めました。そして結果を観察し、最小手数の規則性について気がついたことを発表し、理由を考えたりすることができました。このソフトを開発する前までは教材の準備もままならないことが多く、ハノイの塔を十分に授業で扱う時間がありませんでしたが、今回Excelを用いて独自ソフトを作成したことにより、教材準備の時間が大幅に減少したことと、生徒がパズルを楽しみながら意欲的に授業に集中する姿が見られたのは大変良かったと感じました。意欲的な生徒は最小手数の円盤の動かし方に規則性があることを発見し、その規則性に従えば間違えずに最小の手数で移動できることを発見することもできました。これには私自身も驚きました。
2.数独(ナンバープレース)
「数独」は今や全世界的に知られているパズルです。「ナンバープレース」という言葉で覚えている人も多いことでしょう。パズルのルールは、1から9までの数字を縦、横、3×3の小正方形の中にそれぞれ1つしか入れることができないという条件で、1から9の数字を埋めていくゲームです。これは論理的な思考力を必要とするゲームということで授業で扱うことにしました。生徒の中にはゲームを知っているものが多数おり、授業においては大体が真剣に取り組むことができました。パズルを楽しむ上でPCの利用については絶対に必要というものではないが、苦手意識を持つ生徒のために、数字が入る場所を判定できるソフトをExcelで作成したので、このような生徒の負担を減らしながら授業を行うことができました。
3.魔方陣
これは昔からある有名なパズルで、縦横斜の数字の和が全て等しくなるように、正方形のマスに数字を入れるゲームです。和を計算するのがやや大変なためと、どの数字を使ったかが一目でわかるように、Excelでシートを作成しました。これについては数独と同様に論理的な思考力と計算力が必要となるゲームです。授業ではしばらくゲームに取り組みましたが、難しいところもあったため、論理的な計算で数字が決定する場所をヒントにして、論理的思考を重ねて解法を示しました。その後、昔から発見されている解法を説明しながら、先人の考えに思いを馳せました。初めてでありかつ難しかったので、自力で生徒にたどり着いた生徒は少なかったですが、このゲームに興味を持って取り組めたので、良かったと思いました。
4.石とりゲーム(一山崩し misere版)
さまざまな石とりゲームが知られているが、これは単純で簡単なルールのゲームです。これについては内容が単純なため、PCの利用は敢えてせず、紙で小石の代わりになるものを作成し行いました。
このゲームのルールは、小石の山から小石を順番に取り去っていくが、取り去ることのできる数は1個から3個であり、最後に石を取らなければならなくなった方の負けというものです。取る石の個数は変えることもできます。そのときの必勝形を考えるのも課題としては面白いと思います。
生徒は大変興味を持って取り組み、中には教師と勝負したいと言い出す生徒もいたことは、うれしかったです。ゲームの戦略を考えるというのはレベル的には大変難しい内容ですが、生徒は論理的かつ帰納的に考え、戦略の正しさを実感しながら、攻略法について数理的に学ぶことができました。
石とりゲーム(PDFファイル) 石とりゲーム(Excelマクロファイル)
5.二山崩し・三山崩し
これは石とりゲームの発展形で石の山が複数あるものになります。ただし一山の場合は最後に石をとったほうが「負け」でしたが、二山崩しや三山崩しは最後に石をとったほうが勝ちとなるところが違う点です。これについてはプログラミングを利用し、PCでできるようにしました。このゲームのルールは、1つの山からしか石を取ることはできないが、取る石の数は0個以外ならばいくつでもよいというものです。そして最後にすべての石を取り去ったほうの勝ちとなります。二山崩しであっても必勝法にたどり着くのは難しいと思います。三山崩しとなるとかなり時間をかけて解析しなければ必勝法にはたどり着けないのではないかと授業を通して感じました。
必勝形を考えるにあたり、ヒントになるものがないかと考え、生徒がPCと対戦できるソフトを作成しました。生徒はPCと対戦するときはかなり真剣になって取り組み負けると悔しがっていました。二山崩しの場合はPCと対戦しながら必勝法に気がつく生徒もいましたが、三山崩しはPCの繰り出してくる手を見てもなかなか必勝法にはたどり着くことは難しかったです。数理的なゲームを楽しむことと、その背後にある数理について考えることは、見かけよりもかなりのギャップがあり、数学的な考え方に興味をもっている生徒でないと、そこまで考えることは難しいと感じました。これについてはどのような導入をしたらよいか、どのような授業展開が望ましいか、現在思考中です。よいアイデアがありましたらご教示ください。
6.裏表パズルとLightsOut
裏表パズルには私が知る限りでは2種類のパターンが知られています。1つは回転を含まないものと、もう1つは回転を含むものです。今回は回転を含まないものを題材にしました。(回転を含むものは高木茂男氏の発案によるものであり、著作権がある)これもExcelでプログラミングし、生徒が簡単に楽しめるようにしました。 このパズルの解法については連立方程式により説明が可能です。授業においては、まず生徒は裏表パズルを楽しみ、いろいろな模様のものを1色にできるかどうか取り組みました。その後、1色にできるものとできないものの違いを式で説明するという課題に挑戦しました。
最後にこの応用として、昔から知られている「LightsOut」というゲームを紹介しました。このゲームを式で解くためには9個の連立方程式を解くことになるため、その詳細を授業では扱うことはできませんでしたが、裏表パズルの応用としてその仕組みに興味をもってパズルに挑戦してくれました。
裏表パズル2×2(Excelファイル) 裏表パズル3×3(Excelファイル) LightsOut(Excelファイル)
7.リュカの入れ替えパズル(アマガエルとヒキガエル)
このゲームについてはハノイの塔ほど知られていないかもしれません。これはハノイの塔のゲームを考案したリュカが初期に考えたパズルです。やってみるとハノイの塔よりも難しい気がします。その理由はカエルが逆に前方にしか進めないという設定があるからでしょう。しかし構造はよく似ています。このパズルを解くことが可能であることは数学的帰納法で示せます。何手で可能かということについては漸化式で求めることができます。
8.シルバーダラー(コイン移動ゲーム :The Silver Dollar Game)
これはいくつかのコインを無限に右に長い横のマス目におき、コインを2人で交互に左に動かしていき、動かせなくなったほうの負けというゲームです。ただし動かし方に条件があり、左にいくつ動かしてもよいが、他のコインを跳び越すことはできません。また1マスにはコインは1つしか置けません。考えてみるとわかるのですが、これには必勝形があり、さらに山崩しに同値なゲームとなっています。三山崩しも面白いですが、このように形を変えるとなかなか必勝法を見抜くのが難しいので、楽しめると思います。
9.Empty and Divide
このゲームは次のようなゲームです。2つの箱があり、それぞれの箱にはいくつかの石を入れておきます。ただし、ここで空の箱ではいけません。次に2人のプレーヤーが交代で「どちらか1つの箱を選び、その箱の中身を空にして、他の箱の石を2つの箱に分けている」という操作を行います。ただし、分けて入れる際にそれぞれの箱の中には少なくとも1つは入っているようにしなければなりません。したがって、最後に1個ずつの石が残っているようにできたほうの勝ちとなります。なぜなら1を1以上の2つの数に分割することはできないからです。このゲームには必勝法があります。ただし最初の形が悪いと勝てないときもあります。
10.フィボナッチニム
これは石とりゲーム(一山崩し)の変形バージョンで、石の取り方を次のように少し変えたものです。
(遊び方)いくつかの石がある。それらから先手と後手が交互に石をとっていくが、次のようなルールに従う。
(1)先手は初めに1つ以上の石をとるが、全部の石ではいけない。
(2)次からは前回、相手の人がとった数の2倍までとることができる。
これはその名の通り、フィボナッチ数に関係があり、すべての正の整数は隣り合わない異なったフィボナッチ数の和として表すことができ、その表し方はユニークであるというZeckendorf's Theoremを根拠にしています。この表示を見れば、次に取るべき手が示されます。また初めに与えられた石の数がフィボナッチ数ならば後手必勝、そうでないとき先手必勝となります。
フィボナッチニム(Excelファイル) フィボナッチニムの数理
11.Dynamic subtraction
これは石とりゲーム(一山崩し)の変形バージョンで、石の取り方を次のように少し変えたものです。
(遊び方)いくつかの石がある。それらから先手と後手が交互に石をとっていくが、次のようなルールに従う。
(1)先手は初めに1つ以上の石をとるが、全部の石ではいけない。
(2)次からは前回、相手の人がとった数より多く取ることはできない。
これは石の数の2進数表示を見れば、次に取るべき手が示されます。また石の数が2のべき乗の形のとき後手必勝、そうでないとき先手必勝となります。
Dynamic subtraction(Excelファイル) Dynamic subtractionの必勝法
12.Wythoffのゲーム
これは石とりゲーム(二山崩し)の変形バージョンで、石の取り方を次のように少し変えたものです。
(遊び方)2つの石の山がある。2人で交代に石を取っていくが、次の規則に従うとする。
(1)どちらか一方の山から任意の数の石を取ることができる。
または両方の山から石を取ることができるが、その場合は同数の石をとるものとする。
(2)最後にすべての石を取った方の勝ち。
必勝形はフィボナッチ数列に関係していることが知られています。また黄金比を用いた勝形の一般式も知られています。
これはチェスのクィーンの動きをするボードゲームとも同値なので、それで遊んでもよいでしょう。
どちらでも楽しめるようにゲームを作成しました。
Wythoff game(石取り.ver)(Excelファイル) Wythoff game(ボードゲーム.ver)(Excelファイル)
Wythoffの石取りゲーム必勝形について
13.15パズル
これは有名なパズル作家サム・ロイドが懸賞金をかけて出題したゲームです。おそらく一度はやったことがあると思います。これは群論の置換の考えを使えば、解決可能な数字の配置の判定ができますが、高校数学のレベルを超えるため、今回は授業では扱うことはしませんでした。今後は進んだ生徒の発展教材として用いることが可能である考えています。
14.Nimble
これはNim属するパズルです。見方を変えることで石取りゲームと同値なものになります。ルールは2人で交代で1回ずつコインを左へ移動していき、最後にすべてのコインを一番左の位置に重ねることのできた方の勝ちというものです。左への移動はいくつでもよく、飛び越しても構いません。またコインは各位置に何枚重ねておいてもOKです。下のアプリでは都合上、7枚までのコインを使用することができるようになっています。
どのような見方をすればNimになるか、また必勝形についても考えてみると面白いです。
15.Turning Turtle
これはコインを1列に並べ、2人で交代にコインをひっくり返して遊ぶゲームです。
(ルール)初めにランダムにコインの表と裏を配置します。(H:Heads 表, T:Tails 裏)
動かし方は2通りあり、それは
「1つのコインを選んで、それをひっくり返す」または
「1つのコインをひっくり返し、さらにそれより左に位置するコインを1つ選んでひっくり返す」です。
(動かし方の例1)No7のコインをひっくり返す。
(動かし方の例2)No.12のコインをひっくり返し、それより左の位置にあるNo.5のコインをひっくり返す。
最後に全部「T」にできた方の勝ちです。これもNim属するパズルです。
Turning Turtle(Excelファイル) Turning TurtleのNimとの同値性について
16.引き算ゲーム(Subtraction Game)
これは石取りゲームの変形版であり、取る石の数が集合で与えられている場合です。取る石の数は集合Sで与えられていますが、このとき、先手必勝、後手必勝はどのように見分ければよいか、またどのような戦術によれば勝つことができるかを考えたいと思います。少し遊んでみると、これは単純な石取りゲームのような規則性はないように思えてきます。そこでまず「しらみつぶしに」先手必勝か後手必勝かを調べ、規則性を調べました。この際利用したのが、ゲーム理論においてよく使われる「ポジション」です。簡単に言えば、先手が必勝の状況を「Nポジション」、後手が必勝の状況を「Pポジション」といいます。定義は次のようになります。
(定義)PポジションとNポジションは次の3つの条件で再帰的に定義される。
(1) 最後の状況(ゲームが終わるとき)は、Pポジションである。
(2) すべてのNポジションから、少なくとも1つのPポジションへの動きが存在する。
(3) すべてのPポジションからは必ずNポジションに移る。
上の定義から、PポジションとNポジションは共存しえないので、P,Nのどちらかであるかを定めればよいことになります。そして必勝法は、定義から必勝のパターンは自分の番にPポジションを作り、その状況を相手に渡しながらゲームを進めることであることがわかります。もし、先手の番で石の数がPポジションだったら・・・。相手がミスをして、Nポジションで自分に渡してくれるときがあれば勝つ可能性がありますが、そうでなければ勝つことはできません。このように単純な石取りゲームの取る石の数を少し変えただけで、問題が格段に難しくなってしまいます。大変興味深いですね。
通常版(すべて取り去った方が勝ちというルール)の他に、misere版(すべて取り去った方が負けというルール)についても楽しめるよう、Excelでゲームを作成しました。よろしければご利用ください。
引き算ゲーム(PDFファイル) 引き算ゲーム(Excelファイル)
17.Staircase Nim
階段の上にコインが何枚か置かれており、2人で交互にプレーして、置かれているコインを1つ下の段に移します。移動できる枚数はコインの一部あるいはすべてです。このようにしてコインをすべて高さ0の位置に移していきますが、最後にコインを動かした方の勝ちというゲームです。これはNimの一種であり、戦略も同じものを使うことができます。
Staircase Nim(Excelファイル) Staircase Nimのポジションについて(PDFファイル)
18.さいころゲーム
これは次のようなゲームです。1個のサイコロを連続して振り、出た目の数を足していき、「出た目の数の和×1点」がもらえるとする。ただし、目の和が10以上になったら点数はもらえず、0点となる。プレーヤーは中止を宣言することができ、その場合は中止した時の和を点数としてもらう。このゲームはある戦略にしたがうことで有利に進めることができます。どのような戦略に従えばよいでしょうか。
さいころゲーム(Excelファイル) さいころゲームについての解説(PDFファイル)
19.ルービックキューブ(3×3)
ルービックキューブは大変よく知られており、おもちゃ屋さんでパズルとして売っています。これにもいろいろ種類があり4×4や2×2などもあります。実は6面を揃えることは私にとっては大変難しく、実は揃え方のコツ通りにやらないとできません・・・。あるとき、群論ソフト「GAP」を用いれば6面を揃えることができることを知りました。数学の理論をここで詳しくは展開しませんが、数学がパズルの解法に役立つということを広く知ってもらうために、群論ソフト「GAP」を用いて復元を行う方法を紹介したいと思います。(数学的な理解は必ずしも必要ないので心配ありません)ここではルービックキューブは3×3を考えることにします。その中心の色は面の回転によって変化せず、面の中心の正方形の周りの8つの面×6面=48個の面の色が変化していくことになります。そこで初めの整った状態からどのように面が動いたかを見るため、各面に番号を振り、その変化を見ることにします。この変化は数学的には「置換」という概念で表すことができます。「GAP」では、その状態を表す置換を、さらに互いに素な巡回置換の積で表示してからそのデータ取り込みます。そしてその元を各面の置換で表現し、逆元を求めれば、元に戻す手順が得られるということになります。数学的な理論の詳細は適当な代数学の本を参照してください。また、参考文献としては庄司俊明先生の「GAPの遊び方」という文書がインターネットの検索で見つかると思うので参考にしてください。インターネットでは既にGAPを用いた解法について多くの解説記事がありますので、検索してみて下さい。
(参考文献)[1]「GAPの遊び方」 庄司俊明 [2]「ルービックキューブとGap」 藤本 光史
「数学の話題」へ(リンク) こちらもよろしければご覧ください。
更新履歴
- 2018年11月23日 新しくサイトを立ち上げました。
- 2019年1月20日 二山崩し・三山崩しにPC対戦を加筆しました。
- 2019年2月3日 リュカの入れ替えパズル(アマガエルとヒキガエル)を加筆しました。
- 2019年4月3日 シルバーダラーを加筆しました。
- 2019年4月12日 Empty and Divideを加筆しました。
- 2019年4月16日 スクリーンショットを一部付け加えました。
- 2019年4月29日 フィボナッチニムを加筆しました。
- 2019年5月1日 Dynamic subtractionを加筆しました。
- 2019年6月4日 Wythoffの石取りゲームを加筆しました。
- 2019年6月12日 Wythoffの石取りゲームの必勝形を訂正しました。
- 2019年6月13日 Dynamic subtractionの必勝法を加筆しました。
- 2019年6月21日 フィボナッチニムの数理を加筆しました。
- 2019年12月12日 一部文章を更新しました。
- 2020年7月21日 一部文章の手直しをしました。
- 2020年10月27日 「ハノイの塔」と「フィボナッチニムの数理」の説明文に加筆しました。
- 2020年12月4日 表題を変更しました。
- 2021年7月3日 リンクを編集しました。
- 2021年8月6日 クリエイティブ・コモンズライセンスを付けました。
- 2021年11月6日 ルービックキューブ(3×3)を加筆しました。
- 2021年11月19日 石取りゲームのExcel版と「引き算ゲーム」を付け加えました。
- 2021年12月1日 Wythoffのゲームにボードゲーム版を付け加えました。
- 2021年12月15日 Nimbleを付け加えました。
- 2021年12月20日 Turning Turtleを付け加えました。
- 2021年12月22日 Staircase Nimを付け加えました。
- 2022年11月22日 数学の広場の法の中心極限定理を修正しました。
- 2022年11月24日 さいころゲームを付け加えました。