HDU 1846 Brave Game：巴什博奕（Bash Game）必勝態分析

遊戲規則

一堆 n 顆石子，雙方輪流取，每次取 1..m 顆，取走最後一顆者勝。雙方均用最優策略，判斷先手勝否。

數學分析：必勝/必敗態

設 P 為先手必勝態，N 為先手必敗態（後手必勝）。

• n = 1..m：先手全取 → P
• n = m+1：先手取 k，剩 m+1-k ∈ [1,m]，後手全取勝 → N
• n = m+2 .. 2m+1：先手取 n-(m+1) 留 m+1 給後手 → P
• n = 2(m+1)：無論先手取多少，後手均可取補至 m+1 的倍數 → N

結論：n % (m+1) == 0 時先手必敗（輸出 second），否則先手必勝（輸出 first）。

證明策略

先手策略：若 n % (m+1) = s ≠ 0，先取 s 顆，剩下 (m+1)×k。之後後手取 x，先手取 m+1-x，始終保持剩餘為 m+1 的倍數，最終先手取走最後一顆。

C++ 極簡代碼

#include 
int main() {
    int T, n, m;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        puts(n % (m + 1) ? "first" : "second");
    }
    return 0;
}

擴展：變體遊戲

• 誤ère 遊戲：取最後一顆者負。策略略有不同（留 1 顆給對手）
• 多堆石子：尼姆博弈，用異或和判斷
• 取石子數受限集合：SG 函數計算

核心收穫

巴什博奕是組合博弈論最基礎的模型，核心思想是保持不變量（剩餘石子數為 m+1 的倍數）。這類「周期性必勝態」在許多博弈問題中反覆出現，掌握其分析方法至關重要。