フィボナッチ・フリーク

数学の小ネタ集。

Fibonacci Freak

定規だけで円に接線を引く

平面上に円が描かれており，その周上の一点Pが指定されているとします．Pでこの円に接する直線を，定規だけを用いて作図することはできるでしょうか？

この問題には面白い解答があります．

まず円周上にP以外に4つの点をとります．これは好きなようにとって構いません．次にこれら5点を星型に結び，下図のように2本の直線を引いて，交点をQとします．すると実は直線PQが接線になっているのです！

f:id:fibonacci_freak:20171027224350p:plain

証明はパスカルの定理を用いると簡単にできます．

パスカルの定理．二次曲線上の一般の位置にに6点A,B,C,D,E,Fをとると，ABとDEの交点，BCとEFの交点，CDとFAの交点は一直線上に並ぶ．
f:id:fibonacci_freak:20171027222909p:plain

今回の場合，接点Pを非常に近い2点P',P''に置き換えることで円周上に6点が並び，ちょうどP',P'',Qが一直線上に並ぶことが帰結されます．P',P''がPに近づく極限を考えることで，これが接線になることがわかります．

またパスカルの定理は円だけでなく一般の二次曲線に対して成り立つので，この方法は他の二次曲線にも使えることがわかります！

実際にこの方法で双曲線に接線をひいてみたものが下図です．

f:id:fibonacci_freak:20171027224429p:plain

イェイ！(*^^*)

ChompゲームとHilbertの基底定理

今回はChompというゲームに関する小ネタです．

Chompは石を使って2人で遊ぶゲームです．石をn\times mに並べます．プレイヤーは図のようにある1つの石を選んで，そこより右上にある石を全て取り去ります．これを交互に繰り返して，一番左下の石を取った方が負けです．

f:id:fibonacci_freak:20171020111249p:plain

実はChompは先手必勝であることを示すことができます（このブログで以前紹介した手法です。ぜひ考えてみてください）が，今回はその話ではなく，ゲームが有限の手数で終わるかどうかという点に着目します．

もちろんChompそのものは，有限個の石が一手ごとに減っていくわけなので，自明に有限手数で決着がつきます．

しかし，石が右と上方向に無限に続いているという設定にした「無限Chomp」を考えると話は難しくなります．果たして無限Chompは有限手数で決着がつくのでしょうか？

実は無限Chompは必ず有限の手数で終わることが証明できます．このことはもちろん初等的にも示せますが，今回は可換環論の定理であるHilbertの基底定理を使った証明を紹介したいと思います．

定理（Hilbertの基底定理）．Noether環上の多項式環はNoether環である．特に\mathbb{C}[x_1,\dots,x_n]はNoether環である．

 

最も左下の石を0行目0列目として，a行目b列目にある石を(a,b)と呼び，多項式環の元x^ay^b\in \mathbb{C}[x,y]を対応させます．

f:id:fibonacci_freak:20171020112834p:plain

 

さらに盤面の状態にイデアルIを次のように対応させます．まず初めはI=(0)とし，プレイヤーが(a,b)をとったらIをI+(x^ay^b)に変化させます．すると常に次の関係が成り立つことがわかります：

(a,b)が盤面から取り除かれている\Leftrightarrowx^ay^b\in I.

さて，前述のように\mathbb{C}[x,y]はNoether環であり，先ほどの考察よりIは真に大きくなり続けるので，ゲームが終わらなければ矛盾します．よってゲームは有限手数で終わります！

この証明は石のマスが3次元，4次元方向にも並んで（つまり\mathbb{Z}^n_{\geq 0}上に石が並んでいる），取る時もa \in \mathbb{Z}^n_{\geq 0}を選んでa+\mathbb{Z}^n_{\geq 0}を取り去るという「高次元無限Chomp」に対しても適用できます．

ベン図とグレイ符号

組み合わせ論

領域が4個のベン図を描きたい！ 

というのは誰もが一度は考えることだと思います（？）。しかし普通に描いてみると2^4=16通りすべての組み合わせができなかったり、同じ組み合わせの場所が2つできてしまったりと、なかなかうまくいきません。

f:id:fibonacci_freak:20171004115952p:plain

そこで今回は、領域がいくつのベン図であっても必ず機械的に書ける方法を紹介したいと思います！

使う数学的概念は「グレイ符号」というものです。

 

グレイ符号とは何か？

（※グレイ符号を知っている方はこの節は読み飛ばして構いません）

「符号」というのは数や文字列に対して別の数や文字列を対応させる規則のことです。ここではわかりやすく、2進列（0と1の並び）を別の2進列に変換する規則を考えます。

しかし、そもそもなぜ2進列を別の2進列に変換することなどを考えるのでしょうか。例えば実用的な話として、何かの棒の回転角度を検出するセンサーを作ることを考えてみましょう。基準となる位置から反時計回りに測った角度を\thetaとして、

0^\circ\leq \theta\lt 45^\circ\to 000,

45^\circ\leq \theta\lt 90^\circ\to 001,

90^\circ\leq \theta\lt 135^\circ\to 010,

135^\circ\leq \theta\lt 180^\circ\to 011,

というように2進表記の0,1,2,3,\dotsの順番で信号が出力されるようにするのが普通でしょう。しかし実はこのような決め方では不具合が生じる可能性が高いのです。

たとえば棒の角度がちょうど90^\circ付近で動いている時、信号は001と010の間を行き来します。ここで各桁の信号が変化するタイミングが少しでもずれたら、その瞬間に000や011という全く別の信号が出力される可能性があるのです。これでは安定的な信号が得られません。

そこで同じく45^\circ区切りに、次の順番で信号が出力されるようにしてみます。

000,001,011,010,110,111,101,100

こうすれば信号が乱れることはありません。なぜなら隣り合う2つの信号は1桁しか違わないからです。実は000,001,010,\dotsにそれぞれ000,001,011,\dotsを割り当てるこの規則こそが、3桁のグレイ符号と呼ばれるものです。

具体的に作り方を定義しましょう。

n桁のグレイ符号とは,、0,1の列a_1\dots a_nに対し別の列b_1\dots b_nを対応させる規則であって、次のように帰納的に定義されるものである。
・1桁のグレイ符号はa_1=b_1（何もしない）。
・n桁のグレイ符号は、b_1\dots b_{n-1}がa_1\dots a_{n-1}に対応するn-1桁のグレイ符号で、末尾b_nはa_{n-1}=a_nならば0、そうでなければ1。

具体的には次のようになります。

f:id:fibonacci_freak:20171004123811p:plain

隣り合う自然数の2進表記に対応する符号は1桁しか違わないことが見て取れます。これは定義からただちに証明できます。実際a_1\dots a_{n-1}が変化するのはn=a_1\cdots a_n（2進表記で自然数とみなす）が奇数から偶数になるときですが、末尾の2桁の差が変化するのはnが偶数から奇数になるときで、これらは同時に変化することがないので帰納的に示せます。

 

領域がn個のベン図の描きかた

グレイ符号がわかってしまえば、実はベン図を描くのはとても簡単です。領域1個から初めて、次のように帰納的に描いていきます。n個まで描けたとして、n+1個目の領域を描きましょう。まず今あるベン図の2^n個の部屋に2進列を割り当てるのですが、上からk桁目は「その部屋がk番目に描いた領域の内部に入っているかどうか」を見て、入っていれば1、入っていなければ0とします。たとえばn=3なら次のようになります。

f:id:fibonacci_freak:20171004122854p:plain

全ての領域に2進列を割り当てたら、自然数0,1,2,\dotsの2進表記に対応するグレイ符号の順番に線を結んで新しい領域を作ります。すると全ての部屋を1回ずつ通るので、全ての部屋が新しい領域で2分され、2^{n+1}個の部屋からなる正しいベン図が書けるのです！グレイ符号を使ったのは、線を跨ぐごとに隣りあう部屋（=1桁のみ違う部屋）にしか行くことができないから、というわけです（領域を描いている途中で「飛び地」に行かなければいけない状況は、この作り方なら発生しません。気になった方は帰納法で示してみましょう）。

最後にこうして描ける領域6個（部屋は2^6=64個）のベン図を鑑賞して終えることにしましょう。

f:id:fibonacci_freak:20171004125757p:plain

楽しい！(*^^*)

不思議な確率論

※今回の内容は箱（@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は覆えない配置が存在する最小の点の個数）です。

勝敗が周期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:一度にどちらか一方だけに打てる。

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