Re: [問題] 抓糖果的遊戲-有必勝法嗎?已刪文

看板Inference (推理遊戲)作者cutekid (可愛小孩子)時間8年前 (2016/12/07 14:51)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串2/2 (看更多)

此題屬於 Impartial Game 根據 Sprague-Grundy 定理所寫的程式碼: http://codepad.org/TY9K0HuG 查詢 OEIS 的結果: n = 71 開始出現規律(週期 = 12) https://goo.gl/KOLXU1 先手勝型、輸型判斷法: 將每堆糖果的 g(n) 值做「二進位 xor 總和」得到 Nimber Nimber 為 0 (輸型) Nimber 不為 0 (贏型) 例: 3 堆糖果(7,7,7), g(7) = 2 Nimber = 2 ^ 2 ^ 2 = 2(贏型) 例: 2 堆糖果(1,4), g(1) = 1, g(4) = 1 Nimber = 1 ^ 1 = 0(輸型) 例: 3 堆糖果(2,3,4), g(2) = 2, g(3) = 3, g(4) = 1 Nimber = 2 ^ 3 ^ 1 = 0(輸型) 以此類推 ※ 引述《dsnsid (豪洨人)》之銘言： : 有一個遊戲是這樣的， : 給你一共14顆的糖果，如下圖： : ○○○○○○○ : ○○○○○○○ : 你一次只能夠抓一顆，或是兩顆，位置隨你選擇。 : 如：或 : ●●○○○○○ ○○○●○○○ : ○○○○○○○ ○○○○○○○ : 但是不可以這樣抓。 : 如：或或 : ○○○○○○○ ●○○○○○○ ●○○○○○○ : ○●○○○○● ●○○○○○○ ○○○○●○○ : 如果最後一顆被你抓到，你就贏了。 : 請問這樣要怎麼樣才能夠必勝？ : -------------------------- : 自己的想法是 : 似乎要後攻才能必勝 : 對手：我：對手：我： : ●○○○○○○ ●○○○○○○ ●○○●●○○ ●○○●●○○ : → → → : ○○○○○○○ ●○○○○○○ ●○○○○○○ ●○○●●○○ : 對手：我： : ●●●●●○○ ●●●●●○○ : → 至此，推測剩下的可能，應該不會輸。 : ●○○●●○○ ●●●●●○○ : 紅色是我 : case1： case2： : ●●●●●●● ●●●●●●○ ●●●●●●● : → : ●●●●●●● ●●●●●●○ ●●●●●●● : 只是會這麼順利嗎.... : 而且我也說不出來是甚麼原理.. : 請教各位有沒有甚麼想法可以討論一下。 : 另，還有進階的玩法，如下，玩法一樣也是一次選兩顆，這個也有必勝法嗎? : ○○○○○○○ : ○○○○○○○ : ○○○○○○○ : 請益各位謝謝大家。 ※ 編輯: cutekid (210.61.233.210), 12/07/2016 14:53:15