必勝法って言葉、めっちゃ良いよな。

 

 これは京大アイマス研910Productionアドベントカレンダー2019,1日目の記事です.

adventar.org

 

 早速ですが,次の問題を考えてみてください.

任意の n \in \mathbb{N} について \displaystyle{\frac{c^ n}{ a^ n + b^ n }} \in \mathbb{Z} となるような正整数の組  \left( a,b,c \right) a,b は互いに素 )は a=b=1 以外に存在するか?

 

 記事の内容とは特に関係ありません.昨日のバイト中に考えていた問題です.最後に答えを載せます.

 

 

 というわけで改めましてトップバッターの一葉です,よろしくお願いします.それはさておき,もう三回後期の12月ってマジですか? 去年くらいに別サークルの先輩が全く同じセリフを叫んでいたことを鮮明に覚えているのですけれど,あの方はこのような気持ちだったのですね.こう,何もないはずなのに背後からせっつかれるような感覚.いや,何もなかったから今がこうなってんだよな.うん,わかるわかる.何にだってなれない.

 あとに続く会員たちの『こういうことを書きます』案をざーっと眺めてみると,思いのほか OTAKU-TALK が多そうなので,斜ぶって僕は趣味全開の話を書こうと思います(順では?).

 ところで僕は現在のところ数学科の三回生をしており,さていったい何を書いたものかなあと散々迷ったのですけれど,結局は数学の話をしようということになりました.といっても専門的な内容をここにつらつらと並べ立てても仕方がないので,高校数学の範囲で示すことのできる面白定理を一つ紹介しようと思います.今回扱う問題はこちら.

 

定義( N - 石取りゲーム)
N2 以上の整数とする. テーブルの上にある N 個の石を二人の人物が交互に 1 つ以上取り除き,すべての石を先に取り除いたプレイヤーを勝者とするゲームを行う.ただし,先手はすべての石を取ってはならず,任意のプレイヤーは直前に相手が取り除いた石の個数の 2 倍より多くを取り除いてはならない.

 

 ちょっとしたルールが設けられてはいるものの,石を取っていくだけの簡単なゲームです.しかし,このゲームにはちょっとした裏話があり,実は次のことが成り立ちます.

 

命題A
N – 石取りゲームは N が Fibonacci 数のとき後手必勝,そうでないとき先手必勝である.

 

 もう既にめちゃくちゃ面白くないですか? このこと自体は有名事実のようなのですが,自分が受験生だった当時,少なくとも自分の検索能力ではその証明をみつけることが出来ず,それでこの命題の証明に躍起になっていた日がありました.懐かしい(スマホに残っていた当時のメモを掘り返したのですが,ちょうど大晦日の日にこれを解いていたみたいです).

 詳しくは『二人零和有限確定完全情報ゲーム』なんかで検索すると wikipedia とかそれっぽいのがヒットするのですが,この手の一対一勝負は理論上「引き分け」,「先手必勝」,「後手必勝」のいずれかです(あくまで理論上).

 では早速証明していきましょう.必勝法の構成には勿論フィボナッチ数列を用います.

 

定義( Fibonacci 数列)
数列 \left\{ F_ n \right\}

(1)F_ 1 = 1 , F_ 2 = 2

(2)F_ {n+2} = F_ {n+1} + F_ n

によって定める.この数列の各項を Fibonacci 数という.

 

 最初に次の定理を示します.

 

定理( Zeckendorf )
任意の正整数 M は数列 \left\{ F_ n \right\} の幾つかの隣り合わない項の和として一意的に表すことができる.

このような表現を Zeckendorf 表現という.

(証明)

M についての帰納法M=1 のとき,M が Fibonacci 数のときはよい.そうでない場合を考える.

M \gt 1 のとき,M 未満の最大の Fabonacci 数を F_ i とおくと,帰納法の仮定より M - F_ i は隣り合わない Fibonacci 数の和として表せる.この表現に F_ {i-1} が含まれているとすると M \gt F_ i + F_ {i-1} = F_ {i+1} だから F_ i の最大性に矛盾する.よって M は隣り合わない Fibonacci 数の和で表せる.

一意性を示す.M \gt 1 のとき,M 未満の最大の Fabonacci 数を F_ i とおく.F_ i 未満の隣り合わない Fibonacci 数の和で作ることのできる最大の整数は F_ {i-1} + F_ {i-3} + \cdots だが Fibonacci 数列の性質から,これは  F_ i 以下なので特に M 未満.よって M を隣り合わない Fibonacci 数の和で表すとき,M 未満の最大の Fibonacci 数を必ず用いるので,帰納法より一意性が従う.

\Box

 

 この定理を使って必勝法を構築するのですが,補題が一つ必要なので用意します.

 

補題
1 \leq m \lt M とする.M の Zeckendorf 表現に m 以下の Fibonacci 数が現れないならば,M-m の Zeckendorf 表現には 2m 以下の Fibonacci 数が少なくとも一つ存在する.

(証明)

背理法で示す.

M-m,m の Zeckendorf 表現をそれぞれ F_ {a_ 1} + \cdots + F_ {a_ p} , F_ {b_ 1} + \cdots + F_ {b_ q} とおく.ただし F_ {a_ i} \gt F_ {a _ {i-1} } , F_ {b_ i} \gt F_ {b _ {i-1} } が成り立つとする.すると M= F_ {a_ 1} + \cdots + F_ {a_ p} + F_ {b_ 1} + \cdots + F_ {b_ q} である.

仮定より F_ {a_ p} \gt 2m であって,また明らかに F_ {b_ 1} \leq m なので,a_ p \gt b_ 1 となる.ここでもし a_ p = b_ 1 +1 ならば,F_ {a_ p} = F_ {b_ 1 +1} = F_ {b_ 1} + F_ {b_ 1 -1} \leq 2m となり矛盾である.よって a_ p \gt b_ 1 +1 なので,特に M= F_ {a_ 1} + \cdots + F_ {a_ p} + F_ {b_ 1} + \cdots + F_ {b_ q}M の Zeckendorf 表現である.しかしこれは M の Zeckendorf 表現が m 以下の Fibonacci 数を持たないことに反する.

\Box

 

 これで準備が整いました.必勝法が存在することを示しましょう.

 

命題A-1
N が Fibonacci 数でないなら N – 石取りゲームは先手必勝である.

(証明)

N = F_ {a_ 1} + \cdots + F_ {a_ p}N の Zeckendorf 表現(ただし F_ {a_ i} \gt F_ {a _ {i-1} } )とする.N は Fibonacci 数でないから p \geq 2 である.

先手は初手に F_ {a_ p} 個の石を取る( F_ {a_ p} \lt N なのでこの操作は可能である).すると後手は 2 F_ {a_ p} 個以下の石しか取れないが,Zeckendorf表現と Fibonacci 数列の性質より F_ {a_ {p -1} } \geq F_ {a_ p+2} \gt 2 F_ {a_ p} だから,後手がすべての石を取り除くことは不可能である.

後手が m 個の石を取り除いたとする.すると補題より N - F_ {a_ p} - m の Zeckendorf 表現は 2m 以下の Fibonacci 数をもつので,先手はその Fibonacci 数だけの石を取り除くことが出来る.以上より初めと同じ操作を繰り返すことができ,その過程で後手が勝利することはないので,したがって先手が必ず勝利できる.

\Box

 

命題A-2
N が Fibonacci 数なら N – 石取りゲームは後手必勝である.

(証明)

N= F_ kk \geq 2 )とし,先手が初手に取り除く石の個数を m とおく.

m \geq F_ k - F_ {k-1} のとき,数列 \left\{ F_ n \right\} の各項について \displaystyle{ F_ {n+1} \geq \frac{3}{2} F_ n } となることが帰納法より分かるので,特に F_ {k-1} \leq 2 \left( F_ k - F_ {k-1} \right) が成り立つ.仮定の不等式と合わせて F_ k - m \leq F_ {k-1} \leq 2 \left( F_ k - F_ {k-1} \right) \leq 2m が従い,ゆえに後手はすべての石を取り除くことができる.

1 \leq m \lt F_ k - F_ {k-1} のとき F_ {k-1} \lt F_ k - m \lt F_ k なので F_ k -m は Fibonacci 数でない.よってこの場合は N が Fibonacci 数でない場合に帰着され,命題A-1から後手必勝である.

\Box

 

 以上で証明完了です(一意性のところだけ少し端折ってしまいましたが).簡単な規則だけに従ったゲームなのにフィボナッチ数が絡んでくるという辺りがとても興味深いですよね.京大理学部の特色入試では石を取る個数を平方数のみに限定した場合の先手必勝・後手必勝を問う問題が出題されており,僕がこの N – 石取りゲームを知ったのも,その入試問題がきっかけでした(というどうでもいい補足).ちなみに Fibonacci 数絡みの定理で一番好きなのは,Fibonacci 累乗数は自明なものを除けば 8144 しか存在しない,というやつです.2006に証明されたらしく,比較的新しい定理です.

 

 

 では最後に冒頭の問題の答えを載せて終わりましょう.問題を再掲します.

任意の n \in \mathbb{N} について \displaystyle{\frac{c^ n}{ a^ n + b^ n }} \in \mathbb{Z} となるような正整数の組  \left( a,b,c \right) a,b は互いに素 )は a=b=1 以外に存在するか?

 

 どう考えてもそんな都合のいい組はなさそうです.実際ありません.それを示します.

 

(証明)

a=b=1 のときはよい.ab \neq 1 であるような組は存在しないことを示す.

素数全体からなる集合の部分集合 S_ n を,ある 1 \leq i \leq n に対して a^ {2^ {2i-1}} + b^ {2^ {2i-1}} を割り切るような素数全体として定義する.c を割り切る素数は高々有限個だから,n が正整数全体を動くときある a^ n + b^ n を割り切るような素数全体の集合も有限.ゆえに題意を満たす組が存在するならば,k \geq N なる任意の k に対して S_ N = S_ k となるような正整数 N が存在する.

p \gt q \geq 1 は整数とする.このとき a^ {2^ {2p-1}} + b^ {2^ {2p-1}}a^ {2^ {2q-1}} + b^ {2^ {2q-1}} をともに割り切る素数2 以外に存在しないことを示し,さらに a^ {2^ {2p-1}} + b^ {2^ {2p-1}}2 以外の素数を素因数に持つことを示す.このことが示せれば集合 S_ {p}S_ {q} よりも真に大きく,よって列 S_ 1 \subset S_ 2 \subset \cdots \subset S_ {k} \subset \cdots は真の増大列となるので,先に述べたことから題意を満たすような正整数の組は存在しないことがわかる.

a^ {2^ {2p-1}} + b^ {2^ {2p-1}}a^ {2^ {2q-1}} + b^ {2^ {2q-1}} をともに割り切る素数が存在すると仮定して,それを p とおく.a^ {2^ {2p-1}} + b^ {2^ {2p-1}} – a^ {2^ {2p-1} - 2^ {2q-1}} \left( a^ {2^ {2q-1}} + b^ {2^ {2q-1}} \right) = b^ {2^ {2q-1}} \left( b^ {2^ {2p-1} - 2^ {2q-1}} - a^ {2^ {2p-1} - 2^ {2q-1}} \right) で,pb を割り切らないから b^ {2^ {2p-1} - 2^ {2q-1}} - a^ {2^ {2p-1} - 2^ {2q-1}} を割り切る.さらに b^ {2^ {2p-1} – 2^ {2q-1}} - a^ {2^ {2p-1} – 2^ {2q-1}} + a^ {2^ {2p-1} - 2^ {2q}} \left( a^ {2^ {2q-1}} + b^ {2^ {2q-1}} \right) = b^ {2^ {2q-1}} \left( a^ {2^ {2p-1} - 2^ {2q}} + b^ {2^ {2p-1} - 2^ {2q}} \right) なので pa^ {2^ {2p-1} - 2^ {2q}} + b^ {2^ {2p-1} - 2^ {2q}} を割り切る.同様の操作を繰り返すことにより pa^ {2^ {2p-1} - 2^ {2p-2}} + b^ {2^ {2p-1} - 2^ {2q-2}} = a^ {2^ {2p-2}} + b^ {2^ {2p-2}} を割り切ることがわかる.これより p \left( a^ {2^ {2p-2}} + b^ {2^ {2p-2}} \right) ^ 2 = a^ {2^ {2p-1}} + 2 a^ {2^ {2p-2}} b^ {2^ {2p-2}} + b^ {2^ {2p-1}} を割り切るが,最初の仮定から結局 p2 を割り切る.よってそのような素数があるとすれば,それは 2 に限る.

a^ {2^ {2p-1}} + b^ {2^ {2p-1}}2 の冪なら ab \neq 1 より 4 以上である.特に a^ {2^ {2p-1}} + b^ {2^ {2p-1}}4 で割り切れる.しかし a,b はともに奇数で,奇数の偶数乗を 4 で割った余りは 1 だから,これは矛盾である.ゆえに a^ {2^ {2p-1}} + b^ {2^ {2p-1}}2 の冪でない.

\Box

 

 

 以上,初日のアドベントカレンダーはこんな感じでした.高校時代の自分は整数問題とゲーム理論チックなそれが好きだったので,その延長として本記事を書かせていただきました.たとえ趣味繋がりの相手でも学術的な話題を扱えたりするのが京大という場のいいところの一つだと思うので,書くこと何もねえ~って後続の人は自分が専攻している分野の話とかを書いてみてもいいんじゃないかと思います.まあ,あんまり難しすぎるとアレだけども.

 

twitter.com