#数楽 岩波数学辞典にも載っていないので知らない人が多いのだと思いますが、コンウェイさんの組合せゲーム理論の方法を使えば全ての実数と全ての順序数を含む実閉体を自然に構成できます。例えば1/√ωのような数を含む。所謂超現実数の話。続くhttps://twitter.com/mod_poppo/status/832646696467263489 …

#数楽 続き。確かに整列集合の「連結」で順序数の足し算を定義すると順序数の足し算は非可換になります。しかし、２つのゲームの盤面を合わせたゲームを考えるというアイデアで加法を定義すると自明に可換になります。続くhttps://twitter.com/mod_poppo/status/832644767645184000 …

#数楽 例えば将棋と囲碁の和は、自分の出番のときに将棋盤と囲碁盤のどちらか片方で着手するという新しいゲームになります。順序数は自分もしくは相手だけが着手できるゲーム。可能な着手は「より小さな順序数を選ぶ」。石の山から石を好きなだけ取り除く様子をイメージすると分かりにくい易い。続く

#数楽 ２つの順序数aとbの和は山aと山bのどちらか片方から好きなだけ石を取り除くことが可能な着手のゲームになる。これを対戦型にすることで、順序数の和と順序数単体の大小関係を決めることができます。続く

#数楽 私は順序数aとbの山を2つ所有している。あなたは順序数cの山を保有している。私とあなたで自分の山の1つから石を取り除く着手を交互に繰り返し、自分の出番で着手できなくなった方(自分が取れる石が0個で自分の出番になった側)の負けというルール。続く

#数楽 続き。先に取れる石が無くなった方が負けというルールなので、先手が不利。そこで先手と後手を交代して勝負する。双方最善を尽くしたとき、どちらが先手でも後手必勝なとき、順序数の和a+bと順序数cは等しいと定義できます(well-defined)。大小関係も定義できる。続く

#数楽 続き。自分が保有する石の山(順序数個の石を含む)の一つから石を取り除くという単純(過ぎる)ゲームでなくても、同様の考え方でゲームの局面に加法を定義できます。基本ルールは先に可能な着手が無くなった方が負け。コンウェイさんは趣味の囲碁を数学的に扱いたかったようです。

#数楽 続き。先の石取りゲームでは自分が保有する山からのみ石を取ることができましたが、「二人のプレーヤーが同じ山(達のどれか一つ)から石を取れて、自分の出番で山の石を0個にできたら勝ち」というルールのゲームは有名です。山が一つなら、先手がその山の石をすべて取れるので先手必勝。続く

#数楽 続き。所謂「石取りゲーム」の話。山が２つ以上の場合は山が1つのゲームの和になります。各山が含む石の数が有限個の場合には石取りゲームの意味での自然数の和が何であるかが分かれば「必勝法」が判明するわけです。そういう和の話(ニム和の話)も結構有名だと思います。続く

#数楽 山が2つの場合。片方の山がa個でもう一方の山がb個のとき、後手必勝であるための必要十分条件はa=bであるこです。a=bのとき先手がどちらかの山から石を取ったら後手はもう一方の山から石を取って２つの山の大きさを同じにすれば後手必勝。続き

#数楽 続き。a≠bなら、先手は大きな山から石を取って２つの山を同じサイズにすれば、１つ前に述べた方法によって、先手必勝です。後手必勝の石取りゲームは初期条件で石が0個ゲーム0と同値(これを0の定義と思って良い)。石取りゲームの意味での和を⊕と書くと〜続き

#数楽 続き〜、a⊕b=0とa=bが同値であることがわかりました。特にa⊕a=0です。だからa≠bのときのa⊕bの正体を知るためにはa⊕b⊕c=0になるための必要十分条件が分かれば良い。そのとき両辺にcを⊕するとa⊕b=cとなります。すなわち、山が3つの石取りゲームが〜続く

#数楽 続き〜解ければ(必勝法が分かれば)、石の山がn個の場合の石取りゲームの必勝法が分かるわけです。山の石の個数がそれぞれa_1,…,a_nのとき、後手が必勝であることと、a_1⊕…⊕a_n=0は同値になる。ニム和a⊕bが計算できれば(3山石取りゲームの必勝法がわかれば)よい。

#数楽 続き。答え：a⊕b=(aとbを二進数表示したときの排他的論理和)です。aとbが最初から二進数表示されているなら、ニム和はa⊕b=a XOR b。証明のためには、a XOR b XOR c≠0のとき、a,b,cのどれかを小さくしてXORを0にできることを示せば十分。続く

#数楽 続き。a⊕b⊕c=dが(二進表示で)m桁ならばa,b,cのどれかのm桁目は1になります。それがaだとしてよい。aの下m桁分をeと書くと、d⊕e=fはm-1桁以下になる。だから、aの下m桁をfで置き換えたものをa'と書くと、a'はaより小さくなる。続く

#数楽 続き。すみません。文字数の関係でXORを⊕と書いています。ニム和を⊕と書き、排他的論理和をXORと書くとき、それらが等しいことが証明したい定理なので、論理的スキルが不十分でないせいでその辺の訂正をノータイムでできない人は気になるかもしれません。続く

#数楽 続き。そのとき、a'=a⊕e⊕fなので、a'⊕b⊕c=a⊕e⊕f⊕b⊕c=a⊕b⊕c⊕e⊕f=d⊕e⊕f=f⊕f=0となる。これで、a,b,cの排他的論理和が0でないならばa,b,cのどれか1つを小さくして排他的論理和を0にできることを示せました。続く

#数楽 例:無断で二進表示も使う。1110=141010=100111=7個の石の山があるとき、これらのXORは11≠0。11と14の下2桁のXORは01で、それで14の下2桁を置換すると1101=13になる。同様に10は9になり、7は4になる。続く

#数楽 続き。14個の山から1つ取ると1101=131010=100111=7でXORは0000になる。これが必勝着手の1つ。他にも、10の山から1つ、7の山から3つ取る着手は必勝着手になります。こういうネタを知っていると子供を相手にするときに役に立つかも。続く

#数楽 続き。必勝法を教えてもらった子供が学校で必勝法を広めるというようなことになれば愉快だと思う。

#数楽 続き。石取りゲームは「排他的論理和が非自明な形でどのように役に立つか」の1つの解になっているので、昔からコンピューターの雑誌なんかでは定番のネタとしと取り上げられて来たと思います。その背景には組合せゲーム全体にアーベル群の構造が入るという事実がある。

#数楽 より正確に言うと組合せゲームの同値類にアーベル群の構造が入る。順序数も組合せゲームだし、石取りゲームも組合せゲーム。適切にルールを訂正すれば将棋や囲碁も組合せゲーム。

#数楽 さらに付け足すと、組合せゲームのあいだにはゲーム的に自然に射が定義されて、組合せゲームの圏が得られます。この辺のことまで定番のネタになると面白いのですが、まだ、面白い具体的な話のネタが発掘されていない感じかも。

#数楽combinatorial game category Joyal を検索https://www.google.co.jp/search?q=combinatorial+game+category+Joyal …

#数楽 良い具体例がない話はやはり苦しいと思う。

#数楽 訂正誤「組合せゲームの同値類にアーベル群の構造が入る」正「組合せゲームの同値類全体のクラスにアーベル群の構造が入る」https://twitter.com/genkuroki/status/832787116149010433 …

#数楽 以前、(コンウェイの)組合せゲーム理論と超現実数と囲碁の関係について #CgoT タグをつけて連続ツイートしていたことがありました。まとめて読みたい人は→ http://twilog.org/genkuroki/hashtags-CGoT …