Bowditch による4の力の天使の証明
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/03/01 14:16 UTC 版)
「エンジェル・プロブレム」の記事における「Bowditch による4の力の天使の証明」の解説
Bowditch は元のゲームに対する変種（game 2）としてルールに次の変更を加えた。 天使はかつて行ったことのあるいかなる地点にも戻ることができる（その後、悪魔によってブロックされようとした場合であっても） k-悪魔は、ある場所にブロックを置こうとするなら k 回そこにブロックを置こうと試みる必要がある 天使は東西南北のひとつ隣にだけ動ける 天使が勝つには"回り道"をする必要がある "回り道"は π = ∪ i = 1 ∞ ( σ i ∪ γ i ) {\displaystyle \pi =\cup _{i=1}^{\infty }(\sigma _{i}\cup \gamma _{i})} で定義される道である。ここで σ = ∪ i = 1 ∞ σ i {\displaystyle \sigma =\cup _{i=1}^{\infty }\sigma _{i}} は半無限の弧（自身と交差しない道で、開始点はあるが終了点が存在しないもの）であり、 γ i {\displaystyle {\gamma _{i}}} は互いに素な閉路で次の性質を満たす。 ∀ i : | γ i | ≤ i {\displaystyle \forall i:|\gamma _{i}|\leq i} で | γ i | {\displaystyle |\gamma _{i}|} は i 番目の閉路の長さを示す。 （Well-defined であるために、 γ i {\displaystyle \gamma _{i}} はその開始・終了点が σ i {\displaystyle \sigma _{i}} の終了点と同じでなければならず、 σ i {\displaystyle \sigma _{i}} は σ i + 1 {\displaystyle \sigma _{i+1}} の開始点で終わらなければならない。） さらにもうひとつゲームの変種（game 1）を考える。game 1 は上記のルール2と3を取り入れたもので、3では5-悪魔の存在を仮定する。論文では、この game 1 について天使の必勝法があれば、それは元のゲームで4の力の天使の必勝法も存在することを示す。そして、game 2 における5-悪魔に対しては、非常に単純なアルゴリズムで天使が勝利できることを示す。 以上をもとに、元のゲームでは4の力の天使は、game 2 における5-悪魔に対する仮想の天使を想像することで悪魔に勝てることを示す。 天使は仮想の天使の道を辿るが、閉路 γ i {\displaystyle {\gamma _{i}}} は避ける。 σ {\displaystyle \sigma } が半無限の弧であるために天使はかつて自らが通った場所には戻らずに進むことができる。
※この「Bowditch による4の力の天使の証明」の解説は、「エンジェル・プロブレム」の解説の一部です。
「Bowditch による4の力の天使の証明」を含む「エンジェル・プロブレム」の記事については、「エンジェル・プロブレム」の概要を参照ください。
- Bowditch による4の力の天使の証明のページへのリンク
