Re: [轉錄] 益智問題（拈 001,100，1枚~3倍）
※ 引述《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顆則必勝。
: 有高手能清楚說明解答過程的嗎？感謝囉..
答案是對的，我是用逆向推理
輪到自己時的狀態以(m, n)表示剩m顆石頭，上一手取走n顆
一開始知道以下是必贏的狀態
(1, N) (2, N) (3, N) N表示正整數
因為n最少為1，故玩家能取走剩餘全部石頭
另外，(m, n >= m/3)也是必贏狀態，因為玩家這一手能夠取走全部石頭 ... 稱此為X
(4, 1)是必輸的狀態，因為只能取走1~3顆，皆會落入對方必贏狀態
因為X，(4, n >= 2)必贏
是故從(4, 1)只能導致其後一組必贏狀態: (5, N)
(6, 1)是必輸的狀態，因為取走1~3顆分別落入對方必贏狀態(5, N) (4, n>=2) (3, N)
因為X，(6, n >= 2)必贏
從(6, 1)同樣只能導致其後一組必贏狀態: (7, N)
接下來開始不同了，(8, n <= 2)皆為必輸狀態，因為取走1~6顆會落入對方必贏狀態
(7, N) (6, n >= 2) (5, N) (4, n >= 2) (3, N) (2, N)
因為X，(8, n >= 3)必贏
從(8, n <= 2)可以導致其後兩組必贏狀態: (9, N) (10, N)
玩家分別取走1顆或2顆即可令對方陷入(8, n <= 2)
我想規律從這邊開始應該就比較清楚了
(11, n <= 3)必輸
接下來3組(12~14, N)必贏
(15, n <= 4)必輸
接下來4組(16~19, N)必贏
...
(64, n <= 21)必輸
接下來21組(65~85, N)必贏
(86, n <= 28)必輸
故取走14顆，對方陷入(86, 14)必輸
必輸狀態為(m(k), n < m(k)/3)
m(1) = 4, m(k) = m(k-1) + ceiling(m(k-1)/3)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 128.61.82.163
推
04/21 13:49, , 1F
04/21 13:49, 1F
推
04/21 15:29, , 2F
04/21 15:29, 2F
推
04/21 15:33, , 3F
04/21 15:33, 3F
※ 編輯: ars1an 來自: 128.61.82.163 (04/22 10:05)
→
04/22 10:13, , 4F
04/22 10:13, 4F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 6 之 10 篇)：