Mathe による2の力の天使の証明
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/03/01 14:16 UTC 版)
「エンジェル・プロブレム」の記事における「Mathe による2の力の天使の証明」の解説
Máthé は行儀のよい悪魔 (nice devil) の概念を作った。この悪魔は、かつて天使がいた場所および一つ前の手で天使が行くことができた地点にはブロックを置かない。天使がこの悪魔を相手にする場合には、悪魔の勝利条件を「盤上の有界領域に天使を閉じ込められたか」とする(でなければ、天使はある二地点を延々と行き来するだけで勝利できてしまう。天使が勝つには、その領域から抜け出る必要がある)。証明は大きく二段階からなる。 行儀のよい悪魔に勝つ天使は、本物の悪魔にも勝てる 行儀のよい悪魔に対する明示的な必勝法を示す 二つ目の部分は、天使は(すでに置かれているブロックに加えて)西側の面がすべてブロックされたと仮定して、そのブロックを迷路の壁と見立てて左手法によって迷路の中を進む。つまり、天使は左手を迷路の壁において、壁に沿って進んでいく。この戦略を取る天使を行儀のよい悪魔は捉えられないことが示せる。 一つ目の部分は背理法によるため、この証明からは本物の悪魔に対して直ちに明示的な必勝法を得ることはできない。ただし、Máthé は論文の中で原理上はこの証明から明示的な戦略を導き出すことができるだろうと述べている。
※この「Mathe による2の力の天使の証明」の解説は、「エンジェル・プロブレム」の解説の一部です。
「Mathe による2の力の天使の証明」を含む「エンジェル・プロブレム」の記事については、「エンジェル・プロブレム」の概要を参照ください。
- Mathe による2の力の天使の証明のページへのリンク