以前の「ひとこと」 ： 2016年2月前半
2月1日(月) ４パーツの十字型組木パズル
アーテックブロックを使ってこんなパズルを作ってみました。（情報源は明日のひとことでご紹介します。）
 |
| 図 1 |
分解したところです。（実は青のパーツで１つ、単位立方体を付け忘れています。）
 |
| 図 2 |
これ、頭の中だけで図1のようにどうやって組んだらいいか、わかる方は少数派だと思います。（私には絶対無理です。）
姿勢を変えて、分解手順がわかる写真を撮ってみました(図3,図4)。
 |
 |
| 図 3 | 図 4 |
１パーツだけの平行移動、それも単位立方体の座標系に平行な方向への移動だけで、組み立て、分解ができます。
面白くて何度も何度も組み立てたり分解したりしています。
先週、こんな問題について書きました。
| 【問題1】伸び縮みしないひも（ワイヤー）が１本あります。これを２つに切って、片方のひもでは円を、もう片方のひもでは正方形を作ります。このとき、円と正方形の面積の和を最も小さくするためには、ひもをどのように切ればよいでしょうか？ また、そのときの円の半径と正方形の１辺の長さの関係はどうなるでしょうか？ |
そうしたら、広島県の大村さん、兵庫県の濱中さん（濱中先生）から、なぜこのような答になるのか、さらにその一般化について詳しくメールでご説明いただきました。とても嬉しく拝見しました。これについてはぜひ解説を書こうと思います。ありがとうございました。
＜おまけのひとこと＞
月曜日の朝は、新聞の「歌壇」を読むのを楽しみにしています。
2月2日(火) Interlocked
昨日のパズルは、実はInterlockedというブラウザで遊べるゲームの問題を見て作ったものでした。このゲームは、仮想空間の中に組み立てられた組木パズルが配置されていて、それを分解することが目的のパズルです。視点を変えるモードとパーツを動かすモードがあって、視野の外まで移動したパーツは消えます。パーツを次々と消していって、全部のパーツが消えれば成功、というパズルです。
 |
 |
| 図 1 | 図 2 |
図1は３つのパーツが組み合わさった状態です。左下の円の中に目のようなイラストが描かれていますが、これが「視点変更モード」であることを表しています。この状態で画面をドラッグすると、対称の組木がくるくると回転します。目のアイコンをクリックすると、図2のように手のアイコンに変わります。この状態でマウスボタンを押し込むと、図2のようにxyz軸方向のガイドが現れます。そのガイドの方向にマウスを動かすと、パーツが動きます。（他のパーツに干渉している場合は動きません。）
昨日、アーテックブロックで作ったパズルは、このInterlockedというブラウザゲームの11番の問題のものでした(図3)。
 |
| 図 3 |
ブラウザゲームは本当によくできていると思うのですが、でも実物を作っていじってみるのはとても楽しいです。
＜おまけのひとこと＞
2月から、社内のとあるプロジェクトというか検討会に参加することになりました。メンバーは、20年前くらいに同じ職場だった方、10年くらい前に同じ職場だった方、3年前まで同じ部門だった方など、古い知り合いばかりだということがわかりました。
2月3日(水) Interlocked(その2)
Interlockedというブラウザゲームの立体パズル、もう１つアーテックブロックで作ってみました。問題の10番です。
 |
| 図 1 |
ローマ数字の２“II”のかたちのパーツが３方向に組み合わさっています。図2の青と白のパーツは、ほぼその形（II)をしています。赤と黄色のパーツが組み合わさって“II”のかたちになります。
 |
| 図 2 |
バーチャルで解けても、なんとなく「わかった」という気がしないのです。本物を手にとっていじってみるというのはやっぱり全然違います。コンピュータやゲームやバーチャルな世界は好きなのですが、それでも今のユーザインタフェースでは物足りないです。
＜おまけのひとこと＞
先週末の1/29(金)は、冬だというのに雪ではなくて雨が降りました。雨は積もらずに流れてくれるのでとても楽です。ただ、その後凍ったりするととても危険です。松本付近ではそのため木の枝に重たい着氷ができて、倒木がたくさんあって道路が通行止めになって孤立した集落がいくつもできて全国ニュースになりました。
2月4日(木) 「星が透けて見える大きな身体」
ちょっと違う話題をはさみます。
1月29日(金)は、職場の新年会でした。私を含めて11名が参加しました。私の課は、一時期は30人近いメンバーがいましたが、今は私を含めて13名です。(一人は1月2日から中国に出張に行っていただいていて、一度1月10日ころに予定通り帰国したのですが、すぐにまた現地に飛んでもらわざるを得なくなって、帰国は2月3日の予定です。)
いつもは金曜日の夜に自宅に戻るのですが、飲み会だったので1月30日(土)の朝に自宅に車で戻りました。朝8時5分から45分まで、NHKのラジオ第一放送で「ラジオ文芸館」という番組をやっていて、移動中に聞きました。この日の放送は池澤夏樹の「星が透けて見える大きな身体」でした。とても面白く聞かせていただきました。
調べてみると、「南の島のティオ」という、連作短編の中の１つの作品ということでした。2014年にも放送されている、再放送のようです。読んでみたいと思って近所の図書館の本の検索をしてみたのですが、近隣の６市町村の遠い２つの図書館にしかなくて、しかも閉架になっているようでした。依頼すれば近所の図書館に取り寄せてもらえるのですが、まあそこまでしなくてもいいかなと思っています。Netで検索してみると、中学校の国語の教科書でも掲載されているものがあるそうです。
いつか機会があったらちゃんと読んでみようと思います。
＜おまけのひとこと＞1月29日は今年初めての職場の飲み会でしたが、2月10日には定年退職される方の激励会があります。また、別な方とも「そろそろまた飲みに行こうか」という話も出ています。
2月5日(金) アーテックブロックによる組木パズル
これはまた別の組木です。Interlocked由来ではありません。
 |
| 図 1 |
4×4単位の正方形の板を３枚、組み合わせたかたちになります。
 |
| 図 2 |
パーツはこんな構成です。
頭の中で考えるには適度なレベルかなあと思います。（ちょっと難しいかもしれません。）
＜おまけのひとこと＞
この一週間分の更新(1/30〜2/5）、結局2月1日(月)の早朝にあわてて仕上げています。
2月6日(土) ハノイの塔を二人で(その1)
「ハノイの塔」という古典的なパズルがあります。1883年にE.Lucasによって考案されたと言われています。
 |
| 図 1 |
ゲーム盤は３本の柱で、１本目の柱にすべて大きさが異なる円盤が大きい順に刺さっています(図1)。これが「ハノイの塔」です。パズルの目的は、この「ハノイの塔」を別の柱にそっくり移動することです。移動するときには
というルールを守って動かさなければなりません。
 |
| 図 2 |
途中の状態を図示してみました(図2)。
本来は一人遊びである「ハノイの塔」を対戦型の二人ゲームとして遊ぶ、という論文がありました("Two-player tower of Hanoi" J. Chappelon,U.Larsson, A.Matsuura arXiv:1503.03345v2 27 Oct. 2015)。中身を見る前に、どんなルールならゲームとして成立するか、考えてみてください。
＜おまけのひとこと＞
2月7日(日)の朝に、2/7〜2/12の一週間分の更新をしています。
2/6は床屋さんに行きました。髪を短くしすぎて、ちょっと寒いです。
2月7日(日) 組み合わせゲーム(Combinatorial game)の impartial game と partizan game
組み合わせゲーム(combinatorial game)というのは、運の要素がなくて、情報完全公開型で、勝ち負けが決まっているゲームのことを言います。囲碁とか将棋とかがその代表例です。カードゲームや麻雀のようなゲームは相手の手が見えないので「情報完全公開型」ではありませんし、カードの山（パイル）からカードをひいてくるようなゲームは運の要素がありますから、組み合わせゲームにはなりません。
ゲーム理論の本や論文を読んでいると、“impartial”ゲームと“partizan”ゲーム、という概念が出てくることがあります。日本語としての定訳があるのかなあと思ってちょっと調べてみたのですがよくわかりません。検索してみると、ファーガソン博士によるゲーム理論テキストというpdf（原文はこちらGame Theoryです)を公開していただいているのを見つけました。辞書をひいてみると、
と書かれています。「ファーガソン博士によるゲーム理論テキスト」では、
| ２人のプレイヤーの、各状態からの動作の集合が同じなら偏りのないゲーム(impartial)、そうでなければゲリラ的（遊撃隊）ゲーム (partizan) であるという |
と書かれていますが、やっぱりよくわかりません（翻訳は正確です）。
impartial game というのは、簡単に言うと「相手の駒」「自分の駒」の区別がないゲームのことです。「情報完全公開型で、運の要素がないのに、自分と相手の駒の区別がないゲームがあるんだろうか？」と思われる方もいらっしゃるかもしれません。
例えばNim（３山くずし）に代表されるような「取りつくし型ゲーム(take-away game)」は、代表的なimpartial gameです。Nimというのは次のようなゲームです。
| コインで３つの山を作る。プレーヤーは自分の手番のときに、３つの山のうち１つを選び、その山から好きなだけコインを取り去る。１つでも全部でもよい。交互にコインを取り去り、最後の１つを取った人が勝ち。 |
ちなみに、最後の１個を取った人が「勝ち」になるルールでのプレイを normal game、逆に最後の１個を取ったら「負け」になるルールでプレイするのを misere gameといいます。
昨日の「ハノイの塔」二人ゲーム版も、impartial game になります。辞書をひくと「公平な」とか書いてあるので、二人のプレーヤーの勝算が等しいという意味なのかと思ってしまいますが、そうではありません。
＜おまけのひとこと＞
寒い日が続いています。自宅の暖房には温水ヒーターを使っているのですが、その灯油タンク(90リットル)が日曜日の朝に空になってしまいました。油断しました。緊急用の石油ストーブを使っています。
2月8日(月) ハノイの塔を二人で(その2)
「ハノイの塔」を対戦型の二人ゲームとして遊ぶ話の続きです。論文を見る前に私が考えたルールは以下のものでした。
初期状態から、ハノイの塔のルールに従って、交互に１枚ずつ円盤を移動してゆきます。この条件だけだと、同じ状態を繰り返して勝負がつかないということが容易に想像できます。そこで、いくつか移動条件に限定をかける必要があります。
１．直前の相手の動きの逆の動作は禁止。相手が柱Aから柱Bに移動したとすると、自分は柱Bから柱Aに戻してはいけません。ルール上可能ならばBからCへの移動はOKです。
２．ターゲットの柱以外の柱に「ハノイの塔」が完成してしまってはいけません。スタートの状態に戻すことも禁じ手です。
これでもまだ条件が緩いのですが、いったんこれで考えてみました。
ハノイの塔を分析するのに、ハノイグラフというのが有名です。ハノイの塔の状態を図1、図2のようなグラフとして表現するものです。
 |
| 図 1 |
 |
| 図 2 |
上記の条件だと、円盤が１つのとき(図1)は先手必勝、円盤が２つのとき(図2)は後手必勝のようでした。
 |
 |
| 図 3 | 図 4 |
先手が青、後手が赤とします。まず先手はゴールの柱に円盤を移します（図3）。後手はその円盤をゴールとは違う柱に移します。先手は初期状態には戻せないので、仕方なく円盤２をゴールの柱に移します。次の一手で後手の勝ちです。
では、図4のように、先手がゴールとは違う柱に円盤を移すとします。後手は負けたくないので、その円盤をゴールの柱に持っていきます。ルール上相手の動きの逆はできないので、先手は円盤２を動かします。後手は禁じ手を避けて円盤１を動かします。先手はゴール直前の位置に移動するしかありません。後手の勝ちです。
＜おまけのひとこと＞
2/6(土)は、お昼はパスタとパンでした。ついワインを開けて飲み始めたら、昼間から１本飲んでしまいました。午後じゅう寝てしまいました。たまにはこんな休日もいいかなと思います。夜になって起きてきて、組み合わせゲームの文献を夜中までいろいろ読みました。今週の更新はそこで読んだものがベースになっています。
2月9日(火) ハノイの塔を二人で(その3)
昨日は簡単な円盤２枚の例をご紹介しました。なぜ「初期状態に戻す」のを禁じ手にしたかというと、それを許すと、図のように先手後手が入れ替わるループが可能になるのです。
 |
| 図 1 |
二人のプレーヤーが負けないために最善を尽くすと図1の無限ループになってしまいます。それを避けるために「初期状態に戻るのは禁じ手」にしました。
それでは円盤の数が３枚以上になったらどうでしょうか？ （WolframのMathworldのHanoi Graphのページから図を拝借しました。）
 |
| 図 2 |
この図を見ながら考えると、なんらかの制約がないとこのゲームは終わらないな、ということがわかります。そこで、「その時点で一番大きな円盤をゴールの柱に移動すると、その（最大の）円盤は取り除かれる」というルールを追加したらどうだろうか、と思いました。このルールを追加することで、ゲームの規模がだんだん小さくなってゆくはずです。ただ、円盤を取り除くことが得点になるような仕組みを導入しないと、積極的に円盤を取り除こうとするプレイにはならないかなあとも思いました。もうちょっと考えてみたいです。
＜おまけのひとこと＞
実はこの時点でまだ論文は詳しくは読んでいないのです。ちゃんと読まないと。
2月10日(水) ハノイの塔のバリエーション
柱が３本の「ハノイの塔」は、円盤の数がn個ならば最小手数は2^n-1です。それでは、柱が4本以上だとどうなるでしょうか？ 調べてみると、古くから検討されているようなのですが、最小手数は定式化されていないようです。
村田和也、松浦昭洋による計算実験によると、柱の数が４本、５本と増えたときの最短手数は図1の表のようになったそうです。
| ハノイの塔の最短手数 |
|---|
 |
| 図 1 |
googleでtower of hanoi 4 pegsで検索してみると、いろいろ情報があって面白いです。
4本以上のハノイの塔、研究してみると面白そうです。
＜おまけのひとこと＞
仕事でお世話になっている方（私よりひと回りくらい若い方）と、2月3日(水)に飲みに行きましょうという話をしていました。彼は峠を越えたところに住んでいて、その日はホテルを予約してくれていました。当日のお昼前になって、上司から「今日19時から会議」と言われて、キャンセルになってしまいました。申し訳ないことになってしまいました。
今日(2/10)は職場でお世話になっている方の退職激励会があります。（退職がちょっと羨ましいです）
2月11日(木) SOSゲーム
the 28th Annual USA Mathematical Olympiad, 1999より、「SOSゲーム」のご紹介です。impartial game（相手と自分の駒の区別がないゲーム）です。
| 横１列のNマスの空欄があります。二人のプレーヤーは交互に空欄に"S"か"O"の文字を記入してゆきます。最初に"SOS"の並びを作ったプレーヤーが勝ちです。最後のマスが埋まった後でも、どこにも連続する"SOS"ができていなければ引き分けです。 |
簡単な例を示します。例えばマスの数が４マスだったとします。先手が不用意に、左端のマスに"S"と書きました(図1)。この時点で後手に必勝手があります。わかりますか？
 |
| 図 1 |
上記のページでは、マスが2000のときは後手必勝であることを示せ、という問題になっています。（答も書いてあります。）その前に、まず7マスだったら先手後手どちらが勝つでしょうか？
＜おまけのひとこと＞図1の４マスの問題、後手は空欄の３つのマスのうち１つを選んで、そこに"S"か"O"を書きますから、選択できる手の数は6です。２マス目に"O"を書いたり、3マス目に"S"を書いたりすると、直ちに先手が勝てますから、その２手は少なくとも除外できます。
正しい選択をすると、残った２マスのうちのどちらに先手が"S"を書いても"O"を書いても後手が勝てます。
2月12日(金) コラッツの予想（3x+1問題)
組み合わせゲームをいろいろ調べているときに、Jeffrey C. Lagarias: 3x+1 problem and related problemsというページにたどり着きました。面白そうな論文がたくさんあって、読んでみたいです。
コラッツの予想というのは、「奇数なら3倍して1を足す、偶数なら2で割る」という操作を続けると、どんな数から始めても必ず1に戻るという予想です。
調べてみると「コラッツ予想を解決した」という主張がいろいろあるようです（例えばこちら)。「角の三等分家（定木とコンパスだけで与えられた任意の角を三等分することはできる、という誤った主張をする人々）」を思い出させます。 こちらなどを読むと、びっくりします。
Netの情報というのは、真偽については気を付けなければいけないなあと改めて思います。また、自分自身が嘘を広めないように、誤った情報源にならないように注意しないといけないと思いました。情報源がどこなのか、いつの時点での情報なのか、きちんとわかるようにしないといけないですね。
＜おまけのひとこと＞
2/1〜2/5の週は、仕事で驚くような(嬉しくない)ことが２つほどありましたが、おおむね過ごしやすい週でした。2/8〜2/12の週はどうなるかなあと思っています。2/15の週がちょっと（かなり）大変になりそうで、その準備がちゃんとできるかなあと思っています。
2月13日(土) 「グラフ理論の魅惑の世界」
「グラフ理論の魅惑の世界」(アーサー・ベンジャミン＋ゲアリー・チャートランド ＋ピン・チャン 著 松浦俊輔 訳 青土社)を買って読んでいます。誤植もありますが、魅力的な話題が豊富で面白い本です。
 |
| 図 1 |
この本の最初のほうの話題として、「どんなパーティでも、出席している知り合いの数が等しい人の対(組)がある」という定理が出ていました。これをグラフ理論の言葉で言い換えると、「頂点の次数がすべて異なるグラフは存在しない」となります。
これを説明するために、基本用語だけ簡単に解説しておきます。グラフ理論が対象とする「グラフ」とは、点(頂点)と線(辺)で表される図形です(図1)。図形としてのかたちは問題にならなくて、つながり具合だけを問題にします。例えば、図2のグラフを見てください。白マルが「頂点」、白マルを結ぶ線が「辺」です。このグラフには頂点が６つ、辺が６本あります。
 |
| 図 2 |
図2では辺はまっすぐ描かれていますし、辺どうしは交差していませんが、場合によっては辺は曲がって描かれることもあれば、交差することもあります。
頂点からは通常何本かの辺が出ています。注目している頂点から出ている辺の数を、その頂点の「次数」と言います。図2のグラフの頂点に次数を書き入れてみました(図3)。
 |
| 図 3 |
図3のグラフを、6人のパーティだと思って下さい。知り合いどうしだったら、頂点間に線をひくことにします。(一方的に知っている場合は「知り合い」とは言いません。）図3の例だと、知り合いの数が二人、という人が２名いました。このグラフの辺を足したり引いたりして、すべての頂点の次数を異なる値にできるでしょうか？
…定理で「できない」と言っているので、もちろん不可能なのですが、それがなぜか、どうしたら不可能なことを示せるか、考えてみてください。
＜おまけのひとこと＞
2月13日(土)の夕方に、2/13〜2/19の一週間分の更新をしています。
この本では、頂点の次数がすべて異なるグラフのことを“非正則グラフ”と呼んでいますが、「正則でないグラフ」と「非正則グラフ」の違いがわかりにくいので、非正則グラフとは本文中では書かないことにしました。この言葉を使うと、最初の定理は「非正則グラフは存在しない」と言えて、さらにシンプルですが。
2月14日(日) 「頂点の次数がすべて異なるグラフは存在しない」話
昨日のひとことで、「どんなパーティでも、出席している知り合いの数が等しい人の対(組)がある」という問題が、グラフの「頂点の次数がすべて異なるグラフは存在しない」と言い換えられるという話をしました。これを背理法で示してみましょう。
仮に、頂点の次数がすべて異なるグラフが存在したとしましょう。例えば昨日の例ならば、頂点の数が6なので、次数(知り合いの数)は 0,1,2,3,4,5 の5種類になります。6人のパーティなので、自分自身を除いて、知り合いの数は最大5名ということになります。このとき、次数5の頂点の人は、全員と知り合いです。一方、頂点の次数がすべて異なるためには、一人だけ、次数がゼロ、すなわち知り合いが誰もいない人がいます。これは明らかに矛盾です。
ということは、頂点数が6のグラフにおいて、次数が0と次数が5の頂点は同時には存在しないことがわかります。なので、次数の種類しては最高でも{0,1,2,3,4}か{1,2,3,4,5}のどちらかの、５種類しか存在できません。頂点数が6で次数の種類が5つなので、どのように割り振っても少なくとも一組は同じ次数の頂点のペアができてしまいます(鳩ノ巣原理)。
これはたまたま頂点の数(人数)が6の場合を考えましたが、2以上の任意の頂点数のグラフで同じ論理が成り立ちます。というわけで「どんなパーティでも、出席している知り合いの数が等しい人の対(組)がある」のです。
とても面白いと思います。
＜おまけのひとこと＞
言葉だけで説明しているので、わかりにくいかなあと思いながら書いています。
2月15日(月) ピーターセングラフ
グラフ理論の本を見ると、ピーターセングラフというのがよく出てきます(図1)。
 |
| 図 1 |
これは図1のように表されることが多いのですが、図2や図3のように表されることもあります。
 |
 |
| 図 2 | 図 3 |
辺がゴムひものように自由に伸び縮みするものとして、図1、図2、図3をどのように変形すると同じかたちにできるか、考えてみると面白いです。
ちなみにピーターセン自身はこんな図を描いているそうです。
 |
| 図 4 |
このピーターセングラフ、いろいろと面白い性質があるのですが、背景を説明するのが大変なので、１つだけ紹介します。
ピーターセングラフはハミルトン閉路が存在しません。ハミルトン閉路というのは、すべての頂点を１度だけ巡って出発点に戻る経路のことです。
出発点に戻らなくてもいいのならば、すべての頂点を１度だけ巡ることはできます(ハミルトン路といいます)。図1〜図4の４つの表記のうち、ハミルトン路がわかりやすいのはどれでしょうか？
＜おまけのひとこと＞
私は図2がわかりやすいかなあと思いました。中心の頂点から出発して、外周を一周すればOKです。図4も意外とわかりやすいかもしれません。(片方の五角形を一周して、隣の五角形に移って、隣の五角形を一周する。)