斐波那契拈
斐波那契拈（英文：Fibonacci nim）係一隻減法博弈（subtraction game），係拈（nim）嘅一個變體。博弈入邊有一堆金幣，兩位玩家輪流攞走金幣，每次最少攞一個，第一次可以攞任意數量嘅金幣，不過唔可以攞嗮，之後每次最多只可以攞上一手嘅兩倍，攞到最後一個金幣就贏。喺呢個博弈嘅分析入邊，斐波那契數好重要，事實上呢個博弈嘅解係，如果一開始嘅金幣數係斐波那契數就後手贏，唔係就先手贏。如果得一堆金幣嘅話，呢個博弈係已經解決咗，但係多過一堆就係未解嘅。
斐波那契數係一列用遞歸關係定義嘅數列，第一、二項都係 1，之後每項就係上兩項加埋：1+1 = 2、1+2 = 3、2+3 = 5咁，頭十項係：1、1、2、3、5、8、13、21、34、55（OEIS數列A000045）。
規則同歷史
[編輯]斐波那契拈係雙人博弈，佢哋輪流攞同一堆金幣，第一吓唔可以攞嗮，之後每一步最多可以攞上一步嘅兩倍。博弈跟正常博弈慣例，攞最後一個金幣就贏。[1]
Michael J. Whinihan喺1963年第一個講呢個博弈，佢話係俄勒岡州立大學數學家Robert E. Gaskell發明嘅。佢依家叫斐波那契拈係因為喺分析入邊會出現斐波那契數。[2]
小心唔好同另一個有時都叫斐波那契拈嘅博弈撈亂，喺嗰個博弈入邊每位玩家每次可以攞走某一個斐波那契數咁多嘅金幣。[3]
例子
[編輯]假如一開局有 10 個金幣[4]：
- 10 嘅 Zeckendorf 表示係 10 = 8 + 2，最細出現嘅斐波那契數係 2；開局限額係 9，大過 2，所以第一個玩家攞 2 個金幣，剩低 8 個。
- 依家有 8 個金幣，新限額係 4。第二個玩家無必勝策略，而且攞 3 或者 4 個金幣嘅話第一個玩家可以即刻贏，假設第二個玩家攞 2 個金幣，剩低 6 個。
- 依家有 6 = 5 + 1 個金幣，新限額係 4。第一個玩家攞 1 個金幣，剩低 5 個。
- 5 個金幣，新限額係 2。如果第二個玩家攞 2 個金幣會即刻輸，假設佢攞 1 個金幣，剩低 4 個。
- 4 = 3 + 1 個金幣，新限額係 2。第一個玩家攞 1 個金幣，剩低 3 個。
- 無論第二個玩家依家攞 1 個定 2 個金幣，下一步第一個玩家都夠限額攞嗮，第一個玩家贏咗。
策略
[編輯]
斐波那契拈嘅最佳策略需要識得將金幣數量寫成一拃斐波那契數加埋。[2]一個數可以有好多種方法寫做一拃斐波那契數加埋，但係如果要額外符合呢兩個條件：
- 每個斐波那契數只用一次
- 唔用連續兩個斐波那契數
咁就只有一種方法，呢個寫法就叫 Zeckendorf 表示。舉個例，10 嘅 Zeckendorf 表示係 8 + 2，點解其他寫法唔得呢？例如 5 + 5 就用咗重覆嘅斐波那契數，5 + 3 + 2 就用咗連續兩個斐波那契數，因為(2, 3)、(3, 5)都係連續嘅。一個數嘅 Zeckendorf 表示可以用貪婪算法搵出嚟：每次都減走比個數細嘅最大斐波那契數，直到 0 為止。[5]
搵策略仲要定義一個數叫「限額」，寫做 q ，係代表依家呢一步最多可以攞幾多個金幣。喺第一步，唔可以攞嗮，但係無其他限制，所以如果一開始有 n 個金幣嘅話，限額就係 q = n - 1 。之後每一步，限額都係上一步攞嘅兩倍。[2]
根據上邊嘅定義，一個玩家如果佢嘅限額 q 係大過或者等於當前金幣數量嘅 Zeckendorf 表示之中出現嘅最細斐波那契數，咁就有必勝策略，細過嘅話就對家有必勝策略。喺一個贏位，若果限額夠大嘅話，就攞嗮所有金幣直接贏場博弈；如果唔夠，就攞「Zeckendorf 表示之中出現嘅最細斐波那契數」咁多嘅金幣，因為咁攞嘅話，對家嘅新限額就會細過剩低金幣數量嘅 Zeckendorf 表示之中出現嘅最細斐波那契數，咁對家就會輸。[2]另外亦都有其他嘅必勝策略。[6]
一個斐波那契數嘅 Zeckendorf 表示就係佢自己（即係 21 = 21 咁樣），所以如果一開局金幣數量就係斐波那契數 n，佢嘅「Zeckendorf 表示之中出現嘅最細斐波那契數」就係 n 自己，而一開始嘅限額係 n - 1，所以先手玩家會輸。不過，只要開局數量唔係斐波那契數，咁佢嘅 Zeckendorf 表示入邊就一定有細啲嘅斐波那契數，呢個數會細過個限額，即係話先手玩家會贏。[1]
幾堆金幣
[編輯]斐波那契拈係一個無偏博弈，即係話喺每一個位置可以做嘅選擇唔取決於玩家嘅身份，所以可以用 Sprague-Grundy 定理去分析呢一種變體：有幾堆金幣，每次只可以喺一堆入邊攞走金幣，而且限額係呢一堆上次被人攞嘅數量嘅雙倍。想分析呢個變體嘅話就要計每堆嘅拈值（nim-value）；成個博弈嘅值就係呢拃拈值嘅拈和，不過未有人完整描述所有嘅呢啲值。[7]
另一個變體嘅玩法係咁嘅：都係有幾堆金幣，每次只可以喺一堆入邊攞走金幣，不過限額就係上一步攞嘅數量嘅雙倍，無論上一步係喺邊一堆度攞。[8]
參考
[編輯]- ↑ 1.0 1.1 Vajda, Steven (2007), "Fibonacci nim", Mathematical Games and How to Play Them, Dover Books on Mathematics, Courier Corporation, pp. 28–29, ISBN 9780486462776
- ↑ 2.0 2.1 2.2 2.3 Whinihan, Michael J. (1963), "Fibonacci Nim" (PDF), Fibonacci Quarterly, 1 (4): 9–13
- ↑ For the game of subtracting Fibonacci numbers of coins, see Alfred, Brother U. (1963), "Exploring Fibonacci numbers" (PDF), Fibonacci Quarterly, 1 (1): 57–63, "Research project: Fibonacci nim", p. 63; Pond, Jeremy C.; Howells, Donald F. (1963), "More on Fibonacci nim" (PDF), Fibonacci Quarterly, 1 (3): 61–62
- ↑ 10 個金幣起手要攞 2 個，同埋下邊堆數嘅 Zeckendorf 表示，可以喺Allen & Ponomarenko (2014) p.818 表1 度搵到
- ↑ Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1994), Concrete Mathematics (第2版), Addison-Wesley, pp. 295–296, ISBN 0-201-55802-5
- ↑ Allen, Cody; Ponomarenko, Vadim (2014), "Fibonacci Nim and a full characterization of winning moves", Involve, 7 (6), doi:10.2140/involve.2014.7.807
- ↑ Larsson, Urban; Rubinstein-Salzedo, Simon (2016), "Grundy values of Fibonacci nim", International Journal of Game Theory, 45 (3): 617–625, arXiv:1410.0332, doi:10.1007/s00182-015-0473-y, MR 3538534
- ↑ Larsson, Urban; Rubinstein-Salzedo, Simon (2018), "Global Fibonacci nim", International Journal of Game Theory, 47 (2): 595–611, doi:10.1007/s00182-017-0574-x, MR 3842045