抓糖果的遊戲-有必勝法嗎? - 推理遊戲

此題屬於 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