益智問題（拈之變形） - 拼圖

原文恕刪

以前上演算法時有看過類似的題目

只是當時的題目是兩倍

我把之前做的題目po出來給大家看看

Consider a variant of Nim game played by two players: Initially, at least two
matches are placed on the table between two players. The first player removes
as many matches as he likes, except that he must take at least one and he must
leave at least one. Thereafter, each player in turn must remove at least one
match and at most twice the number of matches his opponent just took. The
player who removes the last match wins. Determine a winning strategy for this
game.


這題我們後來找出的必勝法跟 Fibonacci數列 有關

也就是盡量拿完後剩下的數為 Fibonacci數

Fibonacci數列 定義
F(n) = F(n-1) + F(n-2) for n>2
F(1) = 1
F(2) = 2

假設目前剩下 N 支火柴

則先找最接近 N 且比 N 小的 F(k)

接下來的目標就是拿到剩下 F(k) 支火柴

也就是拿掉 N-F(k) 支火柴

如果沒辦法一次拿成功

則遞迴下去當作剩下 N-F(k) 支火柴的情況下去拿


拿完剩下 F(k) 支火柴時

接下來又輪到對方拿

不管對方拿完剩多少火柴

又可以繼續用上述的方法來拿

當然如果可以一次全部拿完時就一次拿

這樣就直接贏了


因此先手要輸的話

只有一開始的火柴數剛好為 Fibonacci數 時才會輸


不過這是兩倍的情形

原題目是三倍

我想用的技巧應該是差不多才對

以上

--