Re: [問題] 有人知道這個數學問題的答案嗎

看板Hunter作者kerbi (可比)時間16年前 (2009/11/02 02:51)推噓3(3推 0噓 5→)

留言8則, 6人參與討論串30/33 (看更多)

感謝Xixan大提供的資料還正在看不過直接給想知道結論的人答案吧： ┌ 文章此處的確是寫32*33 ↓ "Berlekamp Conway已經證明在一個至少32*33的棋盤上，惡魔會贏過天使。" 然而他們還在繼續研究這種問題，稱為Angel Problem。首先定義這種一次只能以國王方式移動一步的天使為 "Angel of power 1" 則Angel Problem即為： "驗證在某些power底下的Angel能否贏過惡魔。" "Angel of power 1" 已經被solve 現在他們想往更高的power去解 Conway還證明了三個重要的結論： 1. 如果天使的每次移動從不減少她的y座標值的話，則惡魔有必贏策略。(1982) 2. 如果天使的每次移動都使她離(她的)原點越來越遠的話，則惡魔有必贏策略。(1996) 3. 如果某階天使擁有必贏策略的話，則在該策略中，如果天使跳開後，在她原本的起點所可能到的所有格子上都放上惡魔(不包括天使現在所在的格子)，天使依然必贏。 (此動作不算是惡魔的一步，是附加在天使移動後的動作) 文章中有一段提到說： "無論如何，如果天使能夠以騎士的方式移動，惡魔似乎就無法打敗天使了。這個推論可以進一步推論出惡魔也無法打敗能夠以國王方式移動但是卻可以一次移動兩格的天使(Angel of power 2)，因為很顯然兩倍國王比騎士強。但是你能證明嗎？" P.S 所謂的"Angel of power 2"是指下方的5*5棋盤皆為其可移動範圍而且因為天使有翅膀就算路徑上有惡魔也不會影響其移動 (意即如下圖中Ａ處有惡魔，天使依然可以移動到Ｂ處) ●：代表天使 ● ＡＢ Conway證明出的點3的意思就是假如二階天使有必贏策略，而天使現在跳到Ｂ了則在除了Ｂ以外的24格都放上惡魔，天使依然必贏。現在這篇文章將問題簡化成： "Angel of power 1000 是否能在無限大的棋盤上贏過惡魔。" 而結論是：Unknown。文章中指出此證明的難處在於惡魔的每一步基本上都不會是錯誤的，無論該步有多麼愚蠢因為惡魔每走一步，他的狀況都會比他走這步之前還要好 (因為惡魔所在之處很明顯只會妨礙天使) 文章中列出了幾種天使的逃脫策略而作者也證明了如果天使使用那些策略，最終惡魔會獲勝但最終天使仍然有一些策略是還未被討論的 (例如將之前某一策略中的某一限制拿掉後所形成的新策略) 所以目前結論仍然是Unknown 在最後作者也發出懸賞： "以100美金懸賞：證明出天使在足夠大的power下能獲勝。" (A sufficiently high-powered Angel can win.) "以1000美金懸賞：證明出惡魔能夠打敗有限power下的天使。" (Devil can trap an Angel of any finite power.) 以上 -- ╭ 哪裡～都那麼熟了～ ╮ 口桀口桀... ╭ 謝謝你們來參加我們的婚禮～ ◢███◣ ◢███◣ ◢███◣ ◢███◣ ◢███◣ ▄▄▄▄▄▆████◤ ███◥◥ ██◤◥██(◥◥◥◥█● █████ █████ ███ + ▆█▆█◥ ●▄●▄██ ◥████◤◥███◤◤ ██◤ ◤ ◥︺███◤◥－███◤ ◢ 同梯 ◣ ◢ 室友◣ ◢ 哥哥 ◣ ◢▼██◣ ◢▏█▉◣ bluename -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.40.86.180