※ 引述《Liuying (流螢)》之銘言：
: 在正五邊形的頂點上寫上１，２，３，４，５等數字，並連接所有頂點的連線。
: 甲乙輪流移動一個放在頂點上的硬幣，每次都要將硬幣從一個頂點移到另外4
: 個中的一個頂點。開始的人可以決定硬幣放在哪個數字上，然後累加兩人數字
: 的和。剛好加到20的人獲勝，超過的人算輸。
: 例如：甲(3)->乙(2)->甲(4)->乙(1)->甲(5)
: 總和 3 5 9 10 15
: 此時乙就輸定了....甲一定拿得到20
: 請問這個遊戲的必勝法為何？
把原題目換成一個等效概念：
「甲乙2人在玩Nim的遊戲，一次只能拿1~5個，且不能拿和前一個人相同的數目
拿到最後一個石頭的算贏，一開始有N個石頭」
假設甲先乙後
N=1~5，甲必贏，拿光所有石頭即可
N=6 甲必贏!!!甲可以先拿3個，乙不能拿3個，只能拿1或2，剩下的甲拿光
N=7 甲拿2~5，剩下的乙拿光，若甲拿一，剩下6，是必贏數字留給乙，乙必贏
N=8~12，甲皆可以留下7給乙，甲必贏
N=13，除了3以外，不管甲怎麼拿，乙都可以把他導向7，讓甲必輸
甲的唯一策略是拿3，讓乙無法拿3，但乙可以直接拿5, 剩5，而甲無法拿5，乙贏
N=14~18，甲都可以拿到剩下13，13是必輸數字，甲贏
N=19，甲拿3，乙無法把他導向13，不管乙怎麼拿，甲都可以把它導向13或7
乙輸
N=20，甲拿2~5，乙都可以導向13，甲的最佳策略是拿1，剩19，乙可以拿3
剩下的如同甲乙對調在N=19的情況，甲必輸
N=21~25，同N=8~12
N=26，同N=13
N=27~31,同N=14~18
(以下陷入循環)
.
.
.
所以甲在N=7,13,20,26,33,39,46,52,.....是必輸
也就是甲在N=13*k或13*k+7是必輸的，其它必贏
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.70.181.249
※ 編輯: utomaya 來自: 219.70.181.249 (12/09 16:22)