2017-09-30

不思議な確率論

※今回の内容は箱（@o_ccah）さんから教えていただきました。

問題です。

平面上に10個の点を書きます。このときどんな書き方をしても、交わらないいくつかの単位円板で全てを覆うことはできるでしょうか？

f:id:fibonacci_freak:20170930144028p:plain

いくつか具体的にやってみると（コインなどを使ってみましょう）、どうやらできそうだという感覚が得られます。しかし厳密な証明はそう簡単には得られません。任意の書き方について示さなければならない、というのは無謀にも思えます。

しかし、実はこの問題は確率論的手法を使うと鮮やかに解くことができます。確率論的手法とは、ランダムな試行を考え、確率や期待値を計算することで何かの存在を導くという手法です。つまり確率的なのは手法だけで、得られる結果は常に成り立つのです。以下にその不思議な解法を紹介します。

10点を固定し、これらを必ず覆うことができることを示します。まず単位円板を平面全体に最密に充填した図形を考えます。これを $S$ としましょう。

f:id:fibonacci_freak:20170930143943p:plain

次に $S$ を平面上のランダムな場所に配置（平行移動）し、これを $S'$ とします。平面全体の中からランダムに選ぶことは難しいですが、幸い $S$ は周期的になっているので、1周期ぶんの有界な領域から一点選ぶことと同一視できます。

ここで10点のうち $S'$ に含まれる点の個数の期待値を計算します。これは1点ずつそれぞれが $S'$ に含まれる確率を10倍すれば求まります。 $S$ が平面全体に占める割合を計算すると $\dfrac{\pi}{2\sqrt3}=0.906\dots$ となるので、期待値は $9.06\dots$ 個となります。

どんな配置をしても10点のうち9点以下しか含まないと仮定すると、期待値は当然9以下になるはずです。しかし結果は9より真に大きくなっています！よって10点を含むような $S'$ の配置があることが示されました。

騙されたような気がしてしまいますが、これはもちろん正当な数学的証明です。

ちなみに何点までなら必ず覆えるかは未解決問題だそうです。現在知られている最良の評価は $13\leq n\leq 45$ （ $n$ は覆えない配置が存在する最小の点の個数）です。

2017-09-04

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

組み合わせ論

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

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

f:id:fibonacci_freak:20170902015458p:plain

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

(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$ に対し、そのGrundy値 $g(G)$ を以下のように帰納的に定める。

$\displaystyle g(G)=\mathop{\mathrm{mex}}_{G'\in G}g(G')$

ただし $\mathop{\mathrm{mex}}_{x\in S}x$ は $S$ に現れない最小の非負整数（ $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 B$ は $A,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_n$ が $i\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:一度にどちらか一方だけに打てる。

2017-09-02

ζ(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

2017-08-31

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のセルオートマトンと同じ動きをします。

2017-08-26

HEXは先手必勝である

組み合わせ論

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

fibonacci-freak.hatenablog.com

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

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

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

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

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

証明. 背理法で示す。先手必勝でないならば後手必勝である（HEXの定理と、残り手数についての帰納法でわかる）。この仮定のもとで先手の戦略を考える。先手は初手はどこを塗ってもよい。この一手を無視し、先手は後手の必勝手順の通りにゲームを進める。ただし途中で塗るべきタイルが既に塗られている場合はどこを塗ってもよい。このとき先手は必勝手順よりさらに1手分得をしているので必ず勝つことができる。これは後手必勝に矛盾している。ゆえに先手必勝である。 $~~~\square$

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

2017-08-25

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$

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

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

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

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

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

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

そして十分小さい $\varepsilon\gt 0$ をとり、 $g:V(G_n)\to D$ （ $V(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$