okamoto7の日記 天使と悪魔の問題

解かれたらしい．知らなかった． どういう問題かというと，2次元の無限正方格子のある1点に天使がいる．天使は1回にある決められた量だけ格子にそって動くことができる．しかし，その後，悪魔は格子の1点を(天使がいるところ以外は)どこでも壊すことができる．天使と悪魔が交互に自分の手を指していくが，最終的に天使がある有界の領域に閉じ込められてしまうかどうか，を考える．つまり，天使は悪魔に閉じ込められないようにしたいのである． 天使の1回の移動量が十分に大きいとき，天使は必ず逃げ切れる，というものがConwayによる予想だった．これが肯定的に解かれた，というのがニュース． もう少し詳しいことはwikipediaを参照． ちなみに，天使が1回に1歩しか動けない場合，天使はつかまってしまう． 原稿をようやく書き終えた．結局3ページぐらいになってしまった．端折りすぎたかも．

[lockcole]

逃げる天使と追う悪魔についての証明問題が解かれたということらしい。