Re: [轉錄] 益智問題(拈 001,100,1枚~3倍)
簡單講一下,直覺這題應該是屬於NP,要解出來理論上要很久...
原文的解答,到15都是對的,不過20就錯了.
如果留20給對手,對手拿1,剩19還你,無法一手降到15,對方就可以走到15的安全局.
這題比較難是因為安全局不是一維的,要考慮前一手.
5->4是安全局,但是6->4就不是.
前面幾個安全局應該是:
5->4
7->6
(9~10)->8
(12~14)->11
(16~19)->15
下一手就開始複雜了,我也懶得想了.
※ 引述《supermicro (清流是要流到哪裡去?)》之銘言:
: ※ [本文轉錄自 Math 看板]
: 作者: sean0405 (灰) 看板: Math
: 標題: 益智問題
: 時間: Sun Apr 19 11:28:02 2009
: 玩法:一堆石頭有100個,兩人輪流取石,每次每人至少取一個,最多取上次對方取走的
: 石頭數的三倍。取走最後一個石頭的人贏得勝利。
: 問題:請分析這個遊戲是對先手有利,還是對後手有利?為什麼?
: 解答:
: 規則之「下ㄧ人取最多數為前人之三倍」,表示每個數字之最大可取之量為總量÷4之商
: ,總數如為4的倍數則可取之數為商-1。
: 例如100÷4=25,整除所以最大可取之數為25-1=24。
: 在此前提之下,先把問題簡化。從1倒算至關鍵數「8」,接著發現後兩數「9、10」之最
: 大可取數量為2,而11也為2。無法把對方逼到「8」,因此認定「11」也是關鍵數,接著
: 繼續往後推算發現15、20、27、36、48、64、86也均為關鍵數,所以在石頭數100顆的情
: 形下,先手取14顆剩下86顆則必勝。
: 有高手能清楚說明解答過程的嗎?感謝囉..
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.141.138.195
推
04/20 21:10, , 1F
04/20 21:10, 1F
→
04/20 21:10, , 2F
04/20 21:10, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容:
完整討論串 (本文為第 2 之 10 篇):