フィボナッチ・フリーク

数学の小ネタ集。

Fibonacci Freak

組み合わせ論

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

先日、いつものように夜眠れずに布団の中で数学のことを考えていたところ、ふと面白いゲームを思いつきました。 ルールは簡単です。のマス目に2人で交互にのタイルを置いていきます。タイルは重なってはいけません。先に置けなくなったプレイヤーが負けです…

HEXは先手必勝である

// HEXは以下の記事で紹介したボードゲームです。 fibonacci-freak.hatenablog.com 実はHEXは先手必勝であることが知られています。このこともまた、ゲームの考案者の1人であるNashが証明しました。 しかもその証明法はあまりにも意外です。ふつう先手必勝と…

HEXの定理(2)

この記事は以下の記事の続きです: fibonacci-freak.hatenablog.com さて、前回はHEXの定理とBrouwerの不動点定理が実は同値であるということを紹介しました。今回はその証明を書こうと思います。それぞれのステートメントを確認しておきましょう。 定理(HEX…

HEXの定理(1)

HEXというボードゲームを知っていますか? 1940年代に作られたゲームなのですが、最近はスマホのアプリにもなっているようです。私が高校生の頃はよく同級生が遊んでいました。 HEXは六角形のタイルが敷き詰められたひし形の盤で遊びます。2人で交互にタイル…

素数の無限性の一風変わった証明

素数が無限に存在することはもはや人類の常識と言えますが、その証明を沢山知っている人は少ないように感じます。 私は証明そのものを鑑賞するのが好きなタイプなので、以前からずっと素数の無限性のオリジナル証明を作れないかと考えていたのですが、この間…

格子点を2色で塗り分ける問題

先日、Twitterで次のような問題を見かけました。 問題. 平面上の格子点(座標が整数の点)を2色で塗り分ける。どのように塗っても、辺が軸に平行で4つの頂点が同色の正方形が存在することを示せ。 その日の夜ベッドで考えながら寝たところ、朝起きて5分ほど…

グラフと素数:Erdős-Evansの定理

からまでの整数から相異なる数を取り、「がと互いに素ならを結ぶ」という規則でたちを頂点とするグラフを作ってみましょう。例えばとしてを選ぶと下のようなグラフが得られます(小さい数字は)。 グラフをこのような方法で作ることができるとき、はで表現可…

あるサイズの巡回置換だけで任意の置換を作る

任意の置換は互換の積に表すことができます。では同じように、3元の巡回置換(は相異なる)だけを組み合わせて任意の置換を作ることはできるでしょうか? 答えはNoです。(置換は右から合成する)と書けるので、3元の巡回置換は偶置換です。偶置換の積は偶置…

石取りゲームとFibonacci数

2人で次のようなゲームをします。 石が個積まれている()。交互に1つ以上の石を取り去り、最後の石を取れば勝ちである。ただし次のルールを守らなければいけない。 (1) 先手は最初に全ての石をとってはいけない。 (2) 相手が直前に取った石の数の2倍より多く…

置換の下降数と減少数

置換には興味深い性質がたくさんあります。ここではその一つを紹介します。 上の置換の全体をと書きます。に対し、その下降数をなるの総数と定めます。例えばという置換にはとの2箇所に「下降」があるため、下降数はです。 また、置換の減少数をなるの総数と…