※ 引述《superds (托福?..這東西能吃嗎?￾ )》之銘言： : 請教大家個問題 : 共有n個石子 兩名玩家輪流取石子 : 1. 第一名玩家 可以取 1 到 n-1 顆石子（但不能一次取完）。 : 2. 之後的每次最多取 前一位玩家取石數量的 3 倍，但至少要取 1 個石子。 : 3. 取完最後一顆石子的人獲勝。 : 是否有必勝策略。 : 基本上就是Fibonacci博弈 : 不過是取石數量從2倍改成3倍 : 又如果是4倍時，要如何解？ : 謝謝大家 : ----- : Sent from JPTT on my Xiaomi 2211133G. 設 前一手拿 p 顆, 還剩下 n 顆時 (p=0 代表初始回合) 不管 p,n 為何, 接下來遊戲一定會在有限回合內分出勝負(不會有平局) 而接下來可能的過程也是有限種 所以一定有先必勝或後手必勝策略 令 n>0 時 f(p,n) = { 1, 若先手有必勝法 0, 若後手有必勝法 當p=0時 (初始回合) 先手可以拿 1 ~ n-1個 f(0,n) = { 0, 若 f(k,n-k), k=1~n-1 都是 1 (後手有必勝法) 1, 若 f(k,n-k), k=1~n-1 中至少有一個為0, 先手獲勝策略就是拿走使得 f(k,n-k)=0 的k的數量的石子 當p>0時, 先手可以拿 1 ~ min(3p,n) 個 f(p,n) ={ 1, 若 p>=n/3, 直接拿完就獲勝 0, 若 p<n/3, 且f(k,n-k), k=1~3p 都是1, (後手有必勝法) 1, 若 p<n/3, 且f(k,n-k), k=1~3p 至少有一個是0, 先手獲勝策略為拿走使得 f(k,n-k)=0 的k 的數量的石子 從 n=1 開始建表 f(0,1) 未定義 f(p,1) = 1 對所有 p>=1 n=2 f(0,2) = 0, 因為拿走一顆之後, f(1,1)=1, f(p,2) = 1 對所有 p>=1 以此類推可以畫出一張表用填的 填法如下: 從左邊第一欄開始, 從上往下填 n=1時, 除了p=0無定義之外, 底下都是1 第二欄以後, 只要看(1,n-1)往左下斜過去的格子 ( (2,n-2), (3,n-3),... ), 只要有一個是0, 那(0,n) 就是1 (先手必勝), 否則就是0(後手有必勝法) 如果對過去第一個為零的格子是 (k,n-k), 那 0<p<k/3 的格子為0, p>=k/3 為1 如果對過去都是1, 那 p<n/3 的格子都是0, p>=n/3 的格子為1 用程式填到 n=100 的結果如下圖 (程式碼連結放在推文) https://i.imgur.com/8NInX0v.png 第一列 f(0,n) =1 的格子就是一開始先手有必勝法的情形 底下 f(p,n) = 1 就是當對手拿了 p 個之後剩下n 個, 輪到我的時候有必勝法的狀況 必勝的走法就是從f(1,n-1), f(2,n-2), ... 往左下找到第幾個格子是0,就拿幾個石頭 從圖上可以讀出100以內只有 n=2,3,4,6,8,11,15,21,29,40,55,76 時後手有必勝法, 其餘都是先手有必勝法 這個方法不管允許拿的最大數量是前一手的2倍(原始的斐波那契拈), 或是改成3倍或4倍都適用 --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.224.33.70 (臺灣) ※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1741272264.A.FC0.html ※ 編輯: mantour (36.224.33.70 臺灣), 03/06/2025 22:50:51 ※ 編輯: mantour (36.224.33.70 臺灣), 03/06/2025 22:53:48