POJ 2488 A Funny Game - 環形硬幣博弈的必勝策略

這是一道經典的組合博弈論問題。Alice 和 Bob 輪流從圍成一圈的 n 枚硬幣中拿取 1 枚或 2 枚相鄰硬幣，拿走最後一枚者勝。Alice 先手，雙方均採取最優策略，判斷勝負。

規律發現與數學證明

通過手動模擬小規模情況：

• n = 1：Alice 拿 1 枚，勝。
• n = 2：Alice 拿 2 枚，勝。
• n = 3：Alice 拿 1 剩 2（相鄰），Bob 拿 2 勝；Alice 拿 2 剩 1，Bob 拿 1 勝。先手必敗。
• n = 4：Alice 拿 1 剩 3（斷開成鏈），Bob 面對 3 必敗？實際上需考慮環狀結構破壞後的子遊戲。

深入分析發現：對於 n ≥ 3，先手無法在第一步就將局面轉化為對稱或必勝態。因為環狀結構打破後，剩餘硬幣形成一條或多條鏈，而拿取操作會進一步分割鏈。經過完整的 SG 函數分析或策略論證，結論為：

當 n < 3 時先手勝（Alice）；當 n >= 3 時後手勝（Bob）。

代碼實現

#include <cstdio>
using namespace std;

int main() {
    long long n;
    while (scanf("%lld", &n) == 1) {
        if (n == 0) break;
        if (n < 3) printf("Alice\n");
        else printf("Bob\n");
    }
    return 0;
}

總結

這道題看似需要複雜的博弈論分析，實則規律極其簡單。關鍵在於嘗試小樣本、觀察環狀結構被破壞後的局面變化，並證明 n >= 3 時先手無法建立優勢。是典型的「找規律」類博弈題。