フィボナッチ・フリーク

数学の小ネタ集。

Fibonacci Freak

勝敗が周期34で変化するゲーム

先日、いつものように夜眠れずに布団の中で数学のことを考えていたところ、ふと面白いゲームを思いつきました。

ルールは簡単です。1\times nのマス目に2人で交互に1\times 2のタイルを置いていきます。タイルは重なってはいけません。先に置けなくなったプレイヤーが負けです。

f:id:fibonacci_freak:20170902015458p:plain

布団の中でしばらく考えたところ、まずn2以上の偶数の時は先手必勝であることがわかりました。必勝手順は次の通りです。

(1) 先手は最初に中央の2マスにタイルを置く。

(2) その後は後手が置いたタイルと左右対称な位置に置くことを繰り返す。

こうすれば先手が置いた後は常に盤面が左右対称になるため、先手が置けなくなることは決してありません。

次にnが奇数の時を順番に考えていくと次のことがわかりました。

n=3は先手必勝。

n=5は後手必勝。

n=7は先手必勝。

n=9は後手必勝。

n=11は先手必勝。

n=13は先手必勝。

これらは単純に全ての手のパターンを考えることで得られます。

ここまでは特に規則性が無いように見えたので、何か手がかりになる情報がないかと思いネットで調べてみました。すると次のような記述が見つかりました(要約)。

このゲームはDawson's Kaylesと呼ばれ、octal gameという種類に属する。octal gameにはGuy-Smith periodicityという定理が知られており、それによればDawson's Kaylesの勝者はnについて有限個の例外を除き周期34で繰り返す。具体的には後手必勝となるのはn=0,1,15,35またはn\equiv 5,9,21,25,29~\mathrm{mod}~34の時に限る。

 

さすがにこれには驚きました。周期34で繰り返すなんて誰が予想できるでしょうか!

そういうわけで今回はこの周期性(Guy-Smith periodicity)をDawson's Kaylesの場合に限って証明したいと思います。

 

Grundy値について

今回の証明の鍵となるのが、ゲームの局面について定まるGrundy値と言う概念です。

ここでは「有限の手数で勝敗が決することが保証され、確率的要因が絡まず、両者の打てる手が対等で、盤面の情報が全て共有されており、打てる手が無くなった人が負ける」というタイプのゲームのみを考えることにします。Dawson's Kaylesはこのようなゲームの一例です。あとで見ますが、この種のゲームの局面についての命題を示す時は「ゲームが終わるまでの最長手数」に関する帰納法を使うことができる、ということに注意しましょう。

ゲームの局面Gについて、局面G'Gから一手で得られることをG'\in Gと表記します。

定義. ゲームの局面Gに対し、そのGrundyg(G)を以下のように帰納的に定める。
\displaystyle g(G)=\mathop{\mathrm{mex}}_{G'\in G}g(G')
ただし\mathop{\mathrm{mex}}_{x\in S}xSに現れない最小の非負整数(Sが空なら0)を指す。

このとき局面Gが後手必勝であることはg(G)=0と同値です。なぜなら(上に述べた帰納法で)Gが先手必勝となるのはG'\in Gで後手必勝のものが存在することと同値で、これは帰納法の仮定からg(G')=0なるG'が存在すること、すなわちその\mathop{\mathrm{mex}}0にならないことと同値だからです。

Grundy値はただの数字の割り当てではなく、際立った性質を持っています。それは「局面の直和」に対してうまく振る舞うということです。2つの局面G_1,G_2の直和G_1+G_2とは「2つの局面を並べた*1ゲームの局面」のことです。例えば1\times nのDawson's Kaylesの初期局面をK_nとすると、K_{10}の中央にタイルを置いた局面はK_4+K_4と書くことができます。

定理(Sprague-Grundy). ゲームの局面G_1,G_2についてg(G_1+G_2)=g(G_1)\oplus g(G_2). ただしA\oplus BA,Bの2進表記の排他的論理和である。

証明. 帰納法で示す。G'\in (G_1+G_2)G'_1+G_2~(G'_1\in G_1)またはG_1+G'_2~(G'_2\in G_2)と書くことができる。よって帰納法の仮定より

S=\{g(G'_1)\oplus g(G_2)\mid G'_1\in G_1\}\cup\{g(G_1)\oplus g(G'_2)\mid G'_2\in G_2\}

と定めた時

\displaystyle g(G_1+G_2)=\mathop{\mathrm{mex}}_{x\in S}x.

g(G_1)\oplus g(G_2)\not\in Sに注意すれば、示すべきことはx\lt g(G_1)\oplus g(G_2)\Rightarrow x\in Sと言い換えることができる。以下これを示す。

g(G_1)\oplus g(G_2)\oplus xの2進表記の桁数をmとする。自然数aの2進表記の下からm桁目を[a]_mと書くことにすると

[g(G_1)\oplus g(G_2)\oplus x]_m=1.

x\lt g(G_1)\oplus g(G_2)なので[x]_m=0, [g(G_1)]_m=0, [g(G_2)]_m=1としてよい。するとg(G_1)\oplus x \lt g(G_2)なので、g(G_2)の定義を考えればあるG'_2\in G_2があってg(G'_2)=g(G_1)\oplus xとなる。移項してx=g(G_1)\oplus g(G'_2)なのでx\in Sがわかった。~~~\square

 

周期性の証明

さて、Dawson's Kaylesに話を戻しましょう。H_n:=g(K_n)と書くことにします。定義よりH_0=0です。

これから示すGuy-Smith periodicityというのは大雑把に言うと「Grundy値がある範囲で周期的になっていればそこから先ずっと周期的になる」という定理です。これにより、数の小さい範囲で具体的に勝敗を計算して周期34の部分を見つけるだけで、その先の周期性まで示すことができるというわけです。

定理. 正整数i,pが存在してH_{n+p}=H_ni\leq n\lt 2i+p+2に対して成り立つならば、任意のn\gt iに対しても成り立つ。

 証明. n\geq 2i+p+2についてH_{n+p}=H_nであることを帰納法により示す。K_nから一手だけ打った後の局面は、a+b+2=nを満たすある非負整数a,bに対する直和K_a+K_bである。よってGrundy値の定義とSprague-Grundyの定理より

\displaystyle H_{n+p}=\mathop{\mathrm{mex}}_{a+b=n+p-2}H_a\oplus H_b.

ここでa+b=n+p-2\geq 2(i+p)よりa,bの少なくとも片方はi+p以上なので、b\geq i+pとしてよい。すると帰納法の仮定よりH_b=H_{b-p}なので、c=b-pとおけば

\displaystyle H_{n+p}=\mathop{\mathrm{mex}} _{a+c=n-2,~c\geq i}H_a\oplus H_c.

n-2\geq 2iより、a+c=n-2という分解においてc\geq iと仮定しても一般性を失っていない。よって上式は

\displaystyle \mathop{\mathrm{mex}} _{a+c=n-2}H_a\oplus H_c=H_n

に等しい。~~~\square

 

具体的な計算

それではDawson's KaylesのGrundy値が本当に周期34を持つのか確かめてみましょう。愚直に計算すると(コンピュータに計算させると)以下の結果が得られます。字が細いので別タブなどで拡大して見てください。

f:id:fibonacci_freak:20170904011542p:plain

H_{n+34}\neq H_nであるものは桃色で示されています。青で示したi=53\leq n\lt 2i+34+2=142の部分はH_{n+34}=H_nを満たしています。ゆえに先ほど示した定理により、この後もずっと周期34で繰り返すことがわかりました!

 

感想

ところで上の表を見ていると、私にはこの周期性が「数列の途中で偶然生じたものがGuy-Smith periodicityによって繰り返されてしまった」というものには思えず、最初から何か別の理由で周期性が生じているのではないか、という感覚が拭きれません(数学的ではありませんが)。青で塗られた周期的な列は、偶然できたにしては長すぎるように感じます。

今のところGrundy値の周期の長さを計算する方法は、上のように愚直に計算していって周期らしきものを見つける以外ありません。しかし私はいつか必ず34という数の本当の理由が明かされる日が来ると信じています。

*1:一度にどちらか一方だけに打てる。

ζ(2,1)=ζ(3)の2通りの証明

今回の登場人物は次の2つの実数です。

\displaystyle\zeta(2,1)=\sum_{m\gt n\gt 0}\frac{1}{m^2n},

\displaystyle\zeta(3)=\sum_{n=0}^\infty\frac{1}{n^3}.

\zeta(3)は有名なAperyの定数という無理数です。一方で\zeta(2,1)の方は初めて見た方も多いかもしれません。これは多重ゼータ値と呼ばれる実数の族のうち最も単純なものです。

さて、冒頭に「2つの実数」と書きましたがこれは厳密には嘘です。というのも、これらは実は同じ値だからです!今回はその証明を2通り紹介したいと思います。

 

証明1. 2つの級数を足すと

\displaystyle\zeta(2,1)+\zeta(3)=\sum_{m\geq n\gt 0}\frac{1}{m^2n}=\sum_{m=1}^\infty\left(\sum_{n=1}^m\frac{1}{n}\right)\frac{1}{m^2}.

ここで

\displaystyle\sum_{n=1}^m\frac{1}{n}=\sum_{n=1}^\infty\left(\frac{1}{n}-\frac{1}{m+n}\right)

と変形できるので

\displaystyle\zeta(2,1)+\zeta(3)=\sum_{m=1}^\infty\sum_{n=1}^\infty\left(\frac{1}{n}-\frac{1}{m+n}\right)\frac{1}{m^2}.\

さらに和の中身は

\displaystyle\left(\frac{1}{n}-\frac{1}{m+n}\right)\frac{1}{m^2}=\frac{1}{mn(m+n)}=\left(\frac{1}{m}+\frac{1}{n}\right)\frac{1}{(m+n)^2}

となるから

\displaystyle\zeta(2,1)+\zeta(3)=\sum_{n=1}^\infty\sum_{m=1}^\infty\left(\frac{1}{m(m+n)^2}+\frac{1}{n(m+n)^2}\right)=2\zeta(2,1).

移項すれば\zeta(2,1)=\zeta(3)を得る。~~~\square

 

証明2. まず-\log(1-t)の展開

\displaystyle\int_0^t\frac{du}{1-u}=-\log(1-t)=\sum_{n=1}^\infty \frac{t^n}{n}

の両辺をtで割って積分すると

\displaystyle\int_0^s\frac{1}{t}\int_0^t\frac{1}{1-u}dudt=\sum_{n=1}^\infty\frac{s^n}{n^2}.

さらに両辺をsで割って積分すると

\displaystyle\int_0^1\frac{1}{s}\int_0^s\frac{1}{t}\int_0^t\frac{1}{1-u}dudtds=\sum_{n=1}^\infty\frac{1}{n^2}\int_0^1 s^{n-1}ds=\zeta(3).

一方最初の式を1-tで割って積分すると

\displaystyle\int_0^s\frac{1}{1-t}\int_0^t\frac{1}{1-u}dudt=\sum_{n=1}^\infty\frac{1}{n}\int_0^s (t^n+t^{n+1}+\cdots) dt=\sum_{m\gt n\gt 0}\frac{s^m}{mn}.

さらに両辺をsで割って積分すると

\displaystyle\int_0^1\frac{1}{s}\int_0^s\frac{1}{1-t}\int_0^t\frac{1}{1-u}dudtds=\sum_{m\gt n\gt 0}\frac{1}{mn}\int_0^1 s^{m-1}ds=\zeta(2,1).

よって示すべき式は

\displaystyle\int_{0\lt u\lt t\lt s\lt 1}\frac{dudtds}{st(1-u)}\overset{?}{=}\int_{0\lt u\lt t\lt s\lt 1}\frac{dudtds}{s(1-t)(1-u)}.

これは(u,t,s)\mapsto(1-s,1-t,1-u)という変数変換により得られるのでよい。~~~\square

 

如何でしたでしょうか。この等式には上にあげた以外にも様々な証明が知られていて、以下の文献にはなんと32通りもの証明が載っています。気になった方はぜひ読んで見てください。

[math/0502034] Thirty-two Goldbach Variations

Gilbreath予想

たまには合コン受けする(?)タイプの小ネタを紹介したいと思います。

数学の未解決問題は山ほどありますが、中でも「マジかよ」感が高いものとしてGilbreath予想というのがあります。

予想の内容は小学生でも思いつきそうなほど簡単です。まず素数を小さい順に並べます。

f:id:fibonacci_freak:20170831221130p:plain

そして隣り合う2数の差の絶対値を下に書くことを繰り返します。

f:id:fibonacci_freak:20170831221325p:plain

するとなんと、左端に1が並びます!これが何段繰り返しても成立するというのがGilbreath予想です。

この予想は1958年に提出され、2017現在も未解決ですが、3.4\times 10^{11}段目までは正しいことが計算で確かめられています。かの有名な数学者Erdősは「この予想は恐らく正しいが、証明されるのは200年以上後のことだろう」と述べたそうです。

 

ちなみに何回か繰り返すとわかるように、1の後には0と2ばかりが並ぶ長い列ができます。これを確かめることで、何段も先まで愚直に計算しなくてもある程度先まで予想が正しいことが検証できます。完全な余談ですが、0と2のみからなる数列に新しい段を作る操作を2回繰り返すと、ちょうどルール90のセルオートマトンと同じ動きをします。

広告を非表示にする

HEXは先手必勝である

HEXは以下の記事で紹介したボードゲームです。

fibonacci-freak.hatenablog.com

 

実はHEXは先手必勝であることが知られています。このこともまた、ゲームの考案者の1人であるNashが証明しました。

しかもその証明法はあまりにも意外です。ふつう先手必勝といえば「各ターンでこういう手を打てば勝てる」という必勝法を見つけようと考えるでしょう。しかしなんとHEXにおいては具体的な必勝法はわからないのです。

今回はその不思議で圧倒的な証明を紹介したいと思います。

 

注意: ドロップダウンの中に証明があります。自分で考えてみたい方は見てしまわないようにご注意ください。

定理. HEXは先手必勝である。 

f:id:fibonacci_freak:20170826191219p:plain

このような議論はstrategy stealing argumentと言われていて、他にも様々なゲームに応用できます。しかしこんな証明は人間には思いつかないように思われます。Nashは宇宙人だったのでしょう。

広告を非表示にする

HEXの定理(2)

この記事は以下の記事の続きです:

fibonacci-freak.hatenablog.com

 

さて、前回はHEXの定理とBrouwerの不動点定理が実は同値であるということを紹介しました。今回はその証明を書こうと思います。それぞれのステートメントを確認しておきましょう。

定理(HEXの定理). HEXに引き分けは存在しない。すなわち全てのタイルが塗られていれば、どちらかの色は自陣をつないでいる。
定理(Brouwerの不動点定理). D=[0,1]^2とすると、任意の連続写像f:D\to D不動点f(x)=xなる点)をもつ。

証明のための第一歩はHEXの定理の次のような言い換えです。

命題. 下図のようなグラフG_nの頂点を赤と青の2色で塗り分ける。このとき次のいずれかが存在する。
(1)上下の辺を結ぶ道で赤い頂点からなるもの。
(2)左右の辺を結ぶ道で青い頂点からなるもの。
f:id:fibonacci_freak:20170824231208p:plain

HEXの盤面をそのままグラフに直せば、これがHEXの定理と同値であることがわかります。

それでは不動点定理との同値性を証明しましょう。

 

HEXの定理\Rightarrow不動点定理.

f:D\to D不動点が存在しないと仮定する。|f(x)-x|D上で最小値を持つのでそれを\varepsilon\gt0とする。また上図のグラフG_nを、上下左右の辺がDの上下左右の辺上に来るようにD内に配置する。このときグラフ上の任意の点についてfによるx座標, y座標の変化のいずれかは\varepsilon/2以上なので、前者なら赤に、後者なら青に塗る。両方を満たす場合はどちらに塗ってもよい。上の命題より上下の辺を結ぶ赤い頂点からなる道があるとしても一般性を失わない。

さらにこの道上の頂点を、fによりy座標が\varepsilon/2以上減少するならば白、増加するならば黒で塗り分ける。道の上端の点は白、下端の点は黒なので、道中の連続する2点A,Bで色が異なるものが存在する。nを十分大きくとれば|A-B|は任意に小さくでき、かつ|f(A)-f(B)|\gt\varepsilon/2とできる。これはfの一様連続性に反する。~~~\square

 

不動点定理\RightarrowHEXの定理.

上と同様にDG_nを埋め込む。命題の(1)(2)いずれも成立しない塗り分けがあったとすると、頂点集合には以下の4つの交わらない部分集合が存在する。

N=\{上の辺からの赤い道がある赤い頂点\}

S=\{Nに属さない赤い頂点\}

W=\{左の辺からの青い道がある青い頂点\}

E=\{Wに属さない青い頂点\}

そして十分小さい\varepsilon\gt 0をとり、g:V(G_n)\to DV(G)Gの頂点集合を表す)を以下のように定める。

v_1=\dbinom{0}{\varepsilon}, v_2=\dbinom{\varepsilon}{0}

g(P)=\begin{cases}P-v_2~~(P\in N)\\P+v_2~~(P\in S)\\P+v_1~~(P\in W)\\P-v_1~~(P\in E)\end{cases}

ただし仮定からgの像はDに入ることに注意する。

gを小三角形ごとに線形に補間することで連続写像f:D\to Dが得られる。不動点定理よりf不動点xが存在する。xを内部に含むG_nの小三角形の頂点P_1,P_2,P_3を取ると、\{f(P_i)-P_i\}の凸包は原点を含むので、これらの頂点はN,S,W,Eのうち相異なる3つに属する。P_1,P_2がそれぞれN,Sに属するとしても一般性を失わない。しかしP_1,P_2は辺で結ばれているからP_2は上の辺からの赤い道があることになりP_2\in Sに矛盾する。~~~\square

 

組み合わせ論と位相幾何の間のアナロジーは多々ありますが、このように綺麗に同値になる例は少ないように思います。

広告を非表示にする

HEXの定理(1)

HEXというボードゲームを知っていますか?

1940年代に作られたゲームなのですが、最近はスマホのアプリにもなっているようです。私が高校生の頃はよく同級生が遊んでいました。

HEXは六角形のタイルが敷き詰められたひし形の盤で遊びます。2人で交互にタイルを自分の色(赤か青)で塗り、自陣である向かい合う辺を自分の色のタイルでつないだ方が勝ちとなります。言葉で説明するのは難しいので、下の図を見てください。

f:id:fibonacci_freak:20170819110646p:plain

図の場合、赤が上下の赤の陣地をつないでいるので赤の勝ちとなります。

ここで自然に湧く疑問があります。

 

赤も青も勝たないまま全てのタイルが塗られてしまうことはあるのか?

つまり、HEXに引き分けはあるのか

 

結論から言うと、HEXに引き分けはありません。このことはHEXの考案者の1人であるNash(ゲーム理論で有名なあのNashです!)自身が証明し、HEXの定理と呼ばれています。

定理. HEXに引き分けは存在しない。すなわち全てのタイルが塗られていれば、どちらかの色は自陣をつないでいる。

証明. 便宜上、盤の外も自陣の色を延長して赤と青で塗られているとする。赤と青の接する境界線を全て描く(下図の白線)。

f:id:fibonacci_freak:20170819111526p:plain

 

曲がり角の塗られ方を考えれば、この線は途中で切れたり分岐したりしないことがわかる。よって図の左右から出ている4本の境界線は2本ずつ結ばれることになる。すなわち下図のいずれかのようになる。

f:id:fibonacci_freak:20170819113203p:plainf:id:fibonacci_freak:20170819113232p:plain

左の場合は青、右の場合は赤が勝っている。~~~\square

 

スマートな証明ですね。

しかしHEXの定理の面白さはその証明だけにとどまりません。なんとHEXの定理は2次元におけるBrouwerの不動点定理と同値なのです!

定理(Brouwerの不動点定理). D=[0,1]^2とすると、任意の連続写像f:D\to D不動点f(x)=xなる点)をもつ。

ここで証明を紹介したいのですが、とても面白い証明なので、まずは是非皆さん自身で考えてみてください(私自身は考える前に証明を読んでしまい少し悔しい思いをしました)。意外と素直に証明できます。ヒントが欲しい方はTwitterなどで連絡してください。

証明は次の「HEXの定理(2)」で紹介します。お楽しみに!

広告を非表示にする

痩せた集合・太った集合

私は痩せています。どのくらい痩せているかというと、アスパラぐらいです。

実は数学には「痩せた集合」という概念があって、私はだいぶ親近感を持っています。今日はその痩せた集合について書きたいと思います。

まずは痩せた集合の定義をしましょう。

定義. X位相空間Aをその部分集合とする。
(1) A稀薄であるとは、Aの閉包が内点を持たないことをいう。
(2) A痩せた集合(または第1類集合)であるとは、高々可算個の稀薄な集合の合併として表せることをいう。
(3) A太った集合(または第2類集合)であるとは、痩せた集合でないことをいう。

今回は位相空間と言ったら実数\mathbb{R}区間[0,1]などのことだと思っても差し支えありません。また太った集合というのはここだけのネーミングで、一般的ではありません。

例えばX=[0,1]とすると、A=\{\frac{1}{n}\mid n\in\mathbb{Z}_{\gt 0}\}\cup \{0\}は内点を持たない閉集合なので稀薄な集合で、とくに痩せた集合です。また[0,1]自身は太った集合になります。このことは次のBaireの範疇定理からわかります。

定理(Baireの範疇定理). 痩せた集合は内点を持たない。特に完備距離空間は(それ自身の部分集合として)太った集合である。

証明はいろんなところに書いてあるので省略します。

もう一つ痩せた集合の代表としてカントール集合が挙げられます。これは[0,1]から始めて「つながった区間を3等分して真ん中の開区間を取り除く」という操作を無限回繰り返して得られる集合です。開区間を取り除いているので出来上がる集合は閉集合になります。

f:id:fibonacci_freak:20170816234845p:plain

 真ん中を取り除くごとに連結成分1つ分の長さは\dfrac{1}{3}になるので、内点を持たない(区間を含まない)、つまり痩せた集合であることがわかります。また真ん中を取り除くごとに測度(長さの合計)は\dfrac{2}{3} になるので、カントール集合は測度0です。

 

さて、今回伝えたいのは「痩せた集合も結構すごい」という事実です。具体的には[0,1]の部分集合で、痩せた集合にもかかわらず正の測度を持つものが存在するのです!

それが「太ったカントール集合」です。「太った」と付いていますが、これは「カントール集合に比べたら太っている」という意味で、実態は痩せた集合です。

太ったカントール集合の構成は簡単です。まず区間[0,1]から始めて、中央から長さ\dfrac{1}{4}の開区間を取り除きます。次に残った2つの区間それぞれの中央から長さ\dfrac{1}{16}の開区間を取り除きます。次は\dfrac{1}{64}、その次は\dfrac{1}{256},\cdotsと、\dfrac{1}{4^n}の開区間を次々に取り除いてきます。これを無限回繰り返したとき残る集合が太ったカントール集合です。

f:id:fibonacci_freak:20170817115815p:plain

これも区間を取り除くごとに連結成分1つ分の長さが半分以下になるので、内点を持たず、痩せた集合であることがわかります。

太ったカントール集合の測度は

1-\dfrac{1}{4}-\dfrac{2}{16}-\dfrac{4}{64}-\cdots-\dfrac{2^n}{4^{n+1}}-\cdots\\=1-\left(\dfrac{1}{4}+\dfrac{1}{8}+\dfrac{1}{16}+\cdots\right)\\=\dfrac{1}{2}

となり、確かに正の測度\dfrac{1}{2}を持ちます!人は見かけで判断してはいけないのです。私も実は正の測度を持っているかもしれません。

 

さらに、太った集合にもかかわらず測度が0の雑魚集合も存在します。これは次のように作ります。

まず太ったカントール集合Sを用意します。Sにはたくさんの「開区間の穴」が空いていますが、その全てに「Sを相似縮小したもの」を詰め込みます。

f:id:fibonacci_freak:20170817115854p:plain

こうして得られたものをS_1とします。さらにS_1の全ての穴にSを詰め込んだものをS_2とし、S_3,S_4,\cdotsと順に気持ち悪い集合を作っていきます。そして最後に

\displaystyle{T=\bigcup_{n=1}^\infty S_n}

とします。Sを詰め込むたびに空白の部分の測度は半分ずつになるので、Tの測度は1になります。また各S_nは稀薄な集合なのでTは痩せた集合です。するとTの補集合は太った集合で*1、かつ測度0になります。

 

如何でしたでしょうか。皆さんも是非自分好みの気持ち悪い例を作って遊んでみてください。

*1:補集合も痩せているとすると[0,1]も痩せていることになりBaireの範疇定理に矛盾します。