必勝法って言葉、めっちゃ良いよな。
これは京大アイマス研910Productionアドベントカレンダー2019,1日目の記事です.
早速ですが,次の問題を考えてみてください.
記事の内容とは特に関係ありません.昨日のバイト中に考えていた問題です.最後に答えを載せます.
というわけで改めましてトップバッターの一葉です,よろしくお願いします.それはさておき,もう三回後期の12月ってマジですか? 去年くらいに別サークルの先輩が全く同じセリフを叫んでいたことを鮮明に覚えているのですけれど,あの方はこのような気持ちだったのですね.こう,何もないはずなのに背後からせっつかれるような感覚.いや,何もなかったから今がこうなってんだよな.うん,わかるわかる.何にだってなれない.
あとに続く会員たちの『こういうことを書きます』案をざーっと眺めてみると,思いのほか OTAKU-TALK が多そうなので,斜ぶって僕は趣味全開の話を書こうと思います(順では?).
ところで僕は現在のところ数学科の三回生をしており,さていったい何を書いたものかなあと散々迷ったのですけれど,結局は数学の話をしようということになりました.といっても専門的な内容をここにつらつらと並べ立てても仕方がないので,高校数学の範囲で示すことのできる面白定理を一つ紹介しようと思います.今回扱う問題はこちら.
ちょっとしたルールが設けられてはいるものの,石を取っていくだけの簡単なゲームです.しかし,このゲームにはちょっとした裏話があり,実は次のことが成り立ちます.
もう既にめちゃくちゃ面白くないですか? このこと自体は有名事実のようなのですが,自分が受験生だった当時,少なくとも自分の検索能力ではその証明をみつけることが出来ず,それでこの命題の証明に躍起になっていた日がありました.懐かしい(スマホに残っていた当時のメモを掘り返したのですが,ちょうど大晦日の日にこれを解いていたみたいです).
詳しくは『二人零和有限確定完全情報ゲーム』なんかで検索すると wikipedia とかそれっぽいのがヒットするのですが,この手の一対一勝負は理論上「引き分け」,「先手必勝」,「後手必勝」のいずれかです(あくまで理論上).
では早速証明していきましょう.必勝法の構成には勿論フィボナッチ数列を用います.
(1) ,
(2)
によって定める.この数列の各項を Fibonacci 数という.
最初に次の定理を示します.
このような表現を Zeckendorf 表現という.
(証明)
についての帰納法. のとき, が Fibonacci 数のときはよい.そうでない場合を考える.
のとき, 未満の最大の Fabonacci 数を とおくと,帰納法の仮定より は隣り合わない Fibonacci 数の和として表せる.この表現に が含まれているとすると だから の最大性に矛盾する.よって は隣り合わない Fibonacci 数の和で表せる.
一意性を示す. のとき, 未満の最大の Fabonacci 数を とおく. 未満の隣り合わない Fibonacci 数の和で作ることのできる最大の整数は だが Fibonacci 数列の性質から,これは 以下なので特に 未満.よって を隣り合わない Fibonacci 数の和で表すとき, 未満の最大の Fibonacci 数を必ず用いるので,帰納法より一意性が従う.
この定理を使って必勝法を構築するのですが,補題が一つ必要なので用意します.
(証明)
背理法で示す.
の Zeckendorf 表現をそれぞれ , とおく.ただし , が成り立つとする.すると である.
仮定より であって,また明らかに なので, となる.ここでもし ならば, となり矛盾である.よって なので,特に は の Zeckendorf 表現である.しかしこれは の Zeckendorf 表現が 以下の Fibonacci 数を持たないことに反する.
これで準備が整いました.必勝法が存在することを示しましょう.
(証明)
を の Zeckendorf 表現(ただし )とする. は Fibonacci 数でないから である.
先手は初手に 個の石を取る( なのでこの操作は可能である).すると後手は 個以下の石しか取れないが,Zeckendorf表現と Fibonacci 数列の性質より だから,後手がすべての石を取り除くことは不可能である.
後手が 個の石を取り除いたとする.すると補題より の Zeckendorf 表現は 以下の Fibonacci 数をもつので,先手はその Fibonacci 数だけの石を取り除くことが出来る.以上より初めと同じ操作を繰り返すことができ,その過程で後手が勝利することはないので,したがって先手が必ず勝利できる.
(証明)
( )とし,先手が初手に取り除く石の個数を とおく.
のとき,数列 の各項について となることが帰納法より分かるので,特に が成り立つ.仮定の不等式と合わせて が従い,ゆえに後手はすべての石を取り除くことができる.
のとき なので は Fibonacci 数でない.よってこの場合は が Fibonacci 数でない場合に帰着され,命題A-1から後手必勝である.
以上で証明完了です(一意性のところだけ少し端折ってしまいましたが).簡単な規則だけに従ったゲームなのにフィボナッチ数が絡んでくるという辺りがとても興味深いですよね.京大理学部の特色入試では石を取る個数を平方数のみに限定した場合の先手必勝・後手必勝を問う問題が出題されており,僕がこの – 石取りゲームを知ったのも,その入試問題がきっかけでした(というどうでもいい補足).ちなみに Fibonacci 数絡みの定理で一番好きなのは,Fibonacci 累乗数は自明なものを除けば と しか存在しない,というやつです.2006に証明されたらしく,比較的新しい定理です.
では最後に冒頭の問題の答えを載せて終わりましょう.問題を再掲します.
どう考えてもそんな都合のいい組はなさそうです.実際ありません.それを示します.
(証明)
のときはよい. であるような組は存在しないことを示す.
素数全体からなる集合の部分集合 を,ある に対して を割り切るような素数全体として定義する. を割り切る素数は高々有限個だから, が正整数全体を動くときある を割り切るような素数全体の集合も有限.ゆえに題意を満たす組が存在するならば, なる任意の に対して となるような正整数 が存在する.
は整数とする.このとき と をともに割り切る素数は 以外に存在しないことを示し,さらに は 以外の素数を素因数に持つことを示す.このことが示せれば集合 は よりも真に大きく,よって列 は真の増大列となるので,先に述べたことから題意を満たすような正整数の組は存在しないことがわかる.
と をともに割り切る素数が存在すると仮定して,それを とおく. で, は を割り切らないから を割り切る.さらに なので は を割り切る.同様の操作を繰り返すことにより は を割り切ることがわかる.これより は を割り切るが,最初の仮定から結局 は を割り切る.よってそのような素数があるとすれば,それは に限る.
が の冪なら より 以上である.特に は で割り切れる.しかし はともに奇数で,奇数の偶数乗を で割った余りは だから,これは矛盾である.ゆえに は の冪でない.
以上,初日のアドベントカレンダーはこんな感じでした.高校時代の自分は整数問題とゲーム理論チックなそれが好きだったので,その延長として本記事を書かせていただきました.たとえ趣味繋がりの相手でも学術的な話題を扱えたりするのが京大という場のいいところの一つだと思うので,書くこと何もねえ~って後続の人は自分が専攻している分野の話とかを書いてみてもいいんじゃないかと思います.まあ,あんまり難しすぎるとアレだけども.