※ 引述《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://www.ptt.cc/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