ベン図とグレイ符号
領域が4個のベン図を描きたい!
というのは誰もが一度は考えることだと思います(?)。しかし普通に描いてみると通りすべての組み合わせができなかったり、同じ組み合わせの場所が2つできてしまったりと、なかなかうまくいきません。
そこで今回は、領域がいくつのベン図であっても必ず機械的に書ける方法を紹介したいと思います!
使う数学的概念は「グレイ符号」というものです。
グレイ符号とは何か?
(※グレイ符号を知っている方はこの節は読み飛ばして構いません)
「符号」というのは数や文字列に対して別の数や文字列を対応させる規則のことです。ここではわかりやすく、2進列(0と1の並び)を別の2進列に変換する規則を考えます。
しかし、そもそもなぜ2進列を別の2進列に変換することなどを考えるのでしょうか。例えば実用的な話として、何かの棒の回転角度を検出するセンサーを作ることを考えてみましょう。基準となる位置から反時計回りに測った角度をとして、
というように2進表記のの順番で信号が出力されるようにするのが普通でしょう。しかし実はこのような決め方では不具合が生じる可能性が高いのです。
たとえば棒の角度がちょうど付近で動いている時、信号はとの間を行き来します。ここで各桁の信号が変化するタイミングが少しでもずれたら、その瞬間にやという全く別の信号が出力される可能性があるのです。これでは安定的な信号が得られません。
そこで同じく区切りに、次の順番で信号が出力されるようにしてみます。
こうすれば信号が乱れることはありません。なぜなら隣り合う2つの信号は1桁しか違わないからです。実はにそれぞれを割り当てるこの規則こそが、3桁のグレイ符号と呼ばれるものです。
具体的に作り方を定義しましょう。
・桁のグレイ符号は(何もしない)。
・桁のグレイ符号は、がに対応する桁のグレイ符号で、末尾はならば、そうでなければ。
具体的には次のようになります。
隣り合う自然数の2進表記に対応する符号は1桁しか違わないことが見て取れます。これは定義からただちに証明できます。実際が変化するのは(2進表記で自然数とみなす)が奇数から偶数になるときですが、末尾の2桁の差が変化するのはが偶数から奇数になるときで、これらは同時に変化することがないので帰納的に示せます。
領域が個のベン図の描きかた
グレイ符号がわかってしまえば、実はベン図を描くのはとても簡単です。領域1個から初めて、次のように帰納的に描いていきます。個まで描けたとして、個目の領域を描きましょう。まず今あるベン図の個の部屋に2進列を割り当てるのですが、上から桁目は「その部屋が番目に描いた領域の内部に入っているかどうか」を見て、入っていれば、入っていなければとします。たとえばなら次のようになります。
全ての領域に2進列を割り当てたら、自然数の2進表記に対応するグレイ符号の順番に線を結んで新しい領域を作ります。すると全ての部屋を1回ずつ通るので、全ての部屋が新しい領域で2分され、個の部屋からなる正しいベン図が書けるのです!グレイ符号を使ったのは、線を跨ぐごとに隣りあう部屋(=1桁のみ違う部屋)にしか行くことができないから、というわけです(領域を描いている途中で「飛び地」に行かなければいけない状況は、この作り方なら発生しません。気になった方は帰納法で示してみましょう)。
最後にこうして描ける領域6個(部屋は個)のベン図を鑑賞して終えることにしましょう。
楽しい!(*^^*)
不思議な確率論
※今回の内容は箱(@o_ccah)さんから教えていただきました。
問題です。
平面上に10個の点を書きます。このときどんな書き方をしても、交わらないいくつかの単位円板で全てを覆うことはできるでしょうか?
いくつか具体的にやってみると(コインなどを使ってみましょう)、どうやらできそうだという感覚が得られます。しかし厳密な証明はそう簡単には得られません。任意の書き方について示さなければならない、というのは無謀にも思えます。
しかし、実はこの問題は確率論的手法を使うと鮮やかに解くことができます。確率論的手法とは、ランダムな試行を考え、確率や期待値を計算することで何かの存在を導くという手法です。つまり確率的なのは手法だけで、得られる結果は常に成り立つのです。以下にその不思議な解法を紹介します。
10点を固定し、これらを必ず覆うことができることを示します。まず単位円板を平面全体に最密に充填した図形を考えます。これをとしましょう。
次にを平面上のランダムな場所に配置(平行移動)し、これをとします。平面全体の中からランダムに選ぶことは難しいですが、幸いは周期的になっているので、1周期ぶんの有界な領域から一点選ぶことと同一視できます。
ここで10点のうちに含まれる点の個数の期待値を計算します。これは1点ずつそれぞれがに含まれる確率を10倍すれば求まります。が平面全体に占める割合を計算するととなるので、期待値は個となります。
どんな配置をしても10点のうち9点以下しか含まないと仮定すると、期待値は当然9以下になるはずです。しかし結果は9より真に大きくなっています!よって10点を含むようなの配置があることが示されました。
騙されたような気がしてしまいますが、これはもちろん正当な数学的証明です。
ちなみに何点までなら必ず覆えるかは未解決問題だそうです。現在知られている最良の評価は(は覆えない配置が存在する最小の点の個数)です。
勝敗が周期34で変化するゲーム
先日、いつものように夜眠れずに布団の中で数学のことを考えていたところ、ふと面白いゲームを思いつきました。
ルールは簡単です。のマス目に2人で交互にのタイルを置いていきます。タイルは重なってはいけません。先に置けなくなったプレイヤーが負けです。
布団の中でしばらく考えたところ、まずが2以上の偶数の時は先手必勝であることがわかりました。必勝手順は次の通りです。
(1) 先手は最初に中央の2マスにタイルを置く。
(2) その後は後手が置いたタイルと左右対称な位置に置くことを繰り返す。
こうすれば先手が置いた後は常に盤面が左右対称になるため、先手が置けなくなることは決してありません。
次にが奇数の時を順番に考えていくと次のことがわかりました。
・は先手必勝。
・は後手必勝。
・は先手必勝。
・は後手必勝。
・は先手必勝。
・は先手必勝。
これらは単純に全ての手のパターンを考えることで得られます。
ここまでは特に規則性が無いように見えたので、何か手がかりになる情報がないかと思いネットで調べてみました。すると次のような記述が見つかりました(要約)。
さすがにこれには驚きました。周期34で繰り返すなんて誰が予想できるでしょうか!
そういうわけで今回はこの周期性(Guy-Smith periodicity)をDawson's Kaylesの場合に限って証明したいと思います。
Grundy値について
今回の証明の鍵となるのが、ゲームの局面について定まるGrundy値と言う概念です。
ここでは「有限の手数で勝敗が決することが保証され、確率的要因が絡まず、両者の打てる手が対等で、盤面の情報が全て共有されており、打てる手が無くなった人が負ける」というタイプのゲームのみを考えることにします。Dawson's Kaylesはこのようなゲームの一例です。あとで見ますが、この種のゲームの局面についての命題を示す時は「ゲームが終わるまでの最長手数」に関する帰納法を使うことができる、ということに注意しましょう。
ゲームの局面について、局面がから一手で得られることをと表記します。
このとき局面が後手必勝であることはと同値です。なぜなら(上に述べた帰納法で)が先手必勝となるのはで後手必勝のものが存在することと同値で、これは帰納法の仮定からなるが存在すること、すなわちそのがにならないことと同値だからです。
Grundy値はただの数字の割り当てではなく、際立った性質を持っています。それは「局面の直和」に対してうまく振る舞うということです。2つの局面の直和とは「2つの局面を並べた*1ゲームの局面」のことです。例えばのDawson's Kaylesの初期局面をとすると、の中央にタイルを置いた局面はと書くことができます。
証明. 帰納法で示す。はまたはと書くことができる。よって帰納法の仮定より
と定めた時
に注意すれば、示すべきことはと言い換えることができる。以下これを示す。
の2進表記の桁数をとする。自然数の2進表記の下から桁目をと書くことにすると
なので, , としてよい。するとなので、の定義を考えればあるがあってとなる。移項してなのでがわかった。
周期性の証明
さて、Dawson's Kaylesに話を戻しましょう。と書くことにします。定義よりです。
これから示すGuy-Smith periodicityというのは大雑把に言うと「Grundy値がある範囲で周期的になっていればそこから先ずっと周期的になる」という定理です。これにより、数の小さい範囲で具体的に勝敗を計算して周期34の部分を見つけるだけで、その先の周期性まで示すことができるというわけです。
証明. についてであることを帰納法により示す。から一手だけ打った後の局面は、を満たすある非負整数に対する直和である。よってGrundy値の定義とSprague-Grundyの定理より
ここでよりの少なくとも片方は以上なので、としてよい。すると帰納法の仮定よりなので、とおけば
より、という分解においてと仮定しても一般性を失っていない。よって上式は
に等しい。
具体的な計算
それではDawson's KaylesのGrundy値が本当に周期34を持つのか確かめてみましょう。愚直に計算すると(コンピュータに計算させると)以下の結果が得られます。字が細いので別タブなどで拡大して見てください。
であるものは桃色で示されています。青で示したの部分はを満たしています。ゆえに先ほど示した定理により、この後もずっと周期34で繰り返すことがわかりました!
感想
ところで上の表を見ていると、私にはこの周期性が「数列の途中で偶然生じたものがGuy-Smith periodicityによって繰り返されてしまった」というものには思えず、最初から何か別の理由で周期性が生じているのではないか、という感覚が拭きれません(数学的ではありませんが)。青で塗られた周期的な列は、偶然できたにしては長すぎるように感じます。
今のところGrundy値の周期の長さを計算する方法は、上のように愚直に計算していって周期らしきものを見つける以外ありません。しかし私はいつか必ず34という数の本当の理由が明かされる日が来ると信じています。
*1:一度にどちらか一方だけに打てる。
ζ(2,1)=ζ(3)の2通りの証明
今回の登場人物は次の2つの実数です。
,
.
は有名なAperyの定数という無理数です。一方での方は初めて見た方も多いかもしれません。これは多重ゼータ値と呼ばれる実数の族のうち最も単純なものです。
さて、冒頭に「2つの実数」と書きましたがこれは厳密には嘘です。というのも、これらは実は同じ値だからです!今回はその証明を2通り紹介したいと思います。
証明1. 2つの級数を足すと
ここで
と変形できるので
さらに和の中身は
となるから
移項すればを得る。
証明2. まずの展開
の両辺をで割って積分すると
さらに両辺をで割って積分すると
一方最初の式をで割って積分すると
さらに両辺をで割って積分すると
よって示すべき式は
これはという変数変換により得られるのでよい。
如何でしたでしょうか。この等式には上にあげた以外にも様々な証明が知られていて、以下の文献にはなんと32通りもの証明が載っています。気になった方はぜひ読んで見てください。
Gilbreath予想
たまには合コン受けする(?)タイプの小ネタを紹介したいと思います。
数学の未解決問題は山ほどありますが、中でも「マジかよ」感が高いものとしてGilbreath予想というのがあります。
予想の内容は小学生でも思いつきそうなほど簡単です。まず素数を小さい順に並べます。
そして隣り合う2数の差の絶対値を下に書くことを繰り返します。
するとなんと、左端に1が並びます!これが何段繰り返しても成立するというのがGilbreath予想です。
この予想は1958年に提出され、2017現在も未解決ですが、段目までは正しいことが計算で確かめられています。かの有名な数学者Erdősは「この予想は恐らく正しいが、証明されるのは200年以上後のことだろう」と述べたそうです。
ちなみに何回か繰り返すとわかるように、1の後には0と2ばかりが並ぶ長い列ができます。これを確かめることで、何段も先まで愚直に計算しなくてもある程度先まで予想が正しいことが検証できます。完全な余談ですが、0と2のみからなる数列に新しい段を作る操作を2回繰り返すと、ちょうどルール90のセルオートマトンと同じ動きをします。
HEXは先手必勝である
HEXは以下の記事で紹介したボードゲームです。
fibonacci-freak.hatenablog.com
実はHEXは先手必勝であることが知られています。このこともまた、ゲームの考案者の1人であるNashが証明しました。
しかもその証明法はあまりにも意外です。ふつう先手必勝といえば「各ターンでこういう手を打てば勝てる」という必勝法を見つけようと考えるでしょう。しかしなんとHEXにおいては具体的な必勝法はわからないのです。
今回はその不思議で圧倒的な証明を紹介したいと思います。
注意: ドロップダウンの中に証明があります。自分で考えてみたい方は見てしまわないようにご注意ください。
このような議論はstrategy stealing argumentと言われていて、他にも様々なゲームに応用できます。しかしこんな証明は人間には思いつかないように思われます。Nashは宇宙人だったのでしょう。
HEXの定理(2)
この記事は以下の記事の続きです:
fibonacci-freak.hatenablog.com
さて、前回はHEXの定理とBrouwerの不動点定理が実は同値であるということを紹介しました。今回はその証明を書こうと思います。それぞれのステートメントを確認しておきましょう。
証明のための第一歩はHEXの定理の次のような言い換えです。
(1)上下の辺を結ぶ道で赤い頂点からなるもの。
(2)左右の辺を結ぶ道で青い頂点からなるもの。
HEXの盤面をそのままグラフに直せば、これがHEXの定理と同値であることがわかります。
それでは不動点定理との同値性を証明しましょう。
HEXの定理不動点定理.
に不動点が存在しないと仮定する。は上で最小値を持つのでそれをとする。また上図のグラフを、上下左右の辺がの上下左右の辺上に来るように内に配置する。このときグラフ上の任意の点についてによる座標, 座標の変化のいずれかは以上なので、前者なら赤に、後者なら青に塗る。両方を満たす場合はどちらに塗ってもよい。上の命題より上下の辺を結ぶ赤い頂点からなる道があるとしても一般性を失わない。
さらにこの道上の頂点を、により座標が以上減少するならば白、増加するならば黒で塗り分ける。道の上端の点は白、下端の点は黒なので、道中の連続する2点で色が異なるものが存在する。を十分大きくとればは任意に小さくでき、かつとできる。これはの一様連続性に反する。
不動点定理HEXの定理.
上と同様ににを埋め込む。命題の(1)(2)いずれも成立しない塗り分けがあったとすると、頂点集合には以下の4つの交わらない部分集合が存在する。
上の辺からの赤い道がある赤い頂点
に属さない赤い頂点
左の辺からの青い道がある青い頂点
に属さない青い頂点
そして十分小さいをとり、(はの頂点集合を表す)を以下のように定める。
ただし仮定からの像はに入ることに注意する。
を小三角形ごとに線形に補間することで連続写像が得られる。不動点定理よりの不動点が存在する。を内部に含むの小三角形の頂点を取ると、の凸包は原点を含むので、これらの頂点はのうち相異なる3つに属する。がそれぞれに属するとしても一般性を失わない。しかしは辺で結ばれているからは上の辺からの赤い道があることになりに矛盾する。
組み合わせ論と位相幾何の間のアナロジーは多々ありますが、このように綺麗に同値になる例は少ないように思います。