1  2  3  4  5  Contents

單堆遊戲

玩法四 (雙倍遊戲)：

        置若干火柴（或小石子）於桌上，兩人輪流取，先取的一方可任意取，但不可全部取走，之後每人每次至少取一根火柴，最多不可超過前一人所取火柴數的兩倍，取得最後一根火柴者為勝。假設桌上有n根火柴，甲、乙兩人輪流取，致勝關鍵為何？

 

分析：在開始玩前，有件事值得我們注意：

若一開始有n根火柴，而甲先取，甲只能取少於根火柴；
也就是說，若甲取k根火柴，則必須是 k < 。
因為甲若取大於等於根火柴，即 k
則剩下的火柴數為 n – k  n –
                                            n –  =
                                            2
                                            2k

所以對手可以將剩下的火柴全部取走。

 

註：是指大於或等於的整數中，最小的那一個。

例如：

  n = 2，則  =  = 1；
  n = 7，則  =  = 3；
  n = 15，則  =  = 5。

 

那麼現在開始玩玩看：

1. 開始時是2根火柴，甲必輸，因為
   210

2. 開始時是3根火柴，甲必輸，因為
   320

3. 開始時是4根火柴，甲可贏，因為
   43  參考B的情形，但甲乙順序相反。

4. 開始時是5根火柴，甲必輸，因為
   54
   乙只能取1，否則甲可以將剩下的火柴全部取走。參考C的情形，但甲乙順序相反。

5. 開始時是6根火柴，甲必贏，因為
   65
   乙只能取1，否則甲可以將剩下的火柴全部取走。乙只能取1，參考D的情形，但甲乙順序相反。

6. 開始時是7根火柴，甲可贏，因為
   75
   乙只能取1，否則甲可以將剩下的火柴全部取走。參考D的情形，但甲乙順序相反。

7. 開始時是8根火柴，甲必輸，因為
   87  參考F的情形，但甲乙順序相反。
   86  參考E的情形，但甲乙順序相反。

8. 開始時是9根火柴，甲可贏，因為

   98	7  參考F的情形。
   	6 參考E的情形。

9. 開始時是10根火柴，甲可贏，因為
   108  乙只能取1或2，參考G的情形，但甲乙順序相反。

10. 開始時是11根火柴，甲可贏，因為
    118  乙只能取1或2，參考G的情形，但甲乙順序相反。

11. 開始時是12根火柴，甲可贏，因為
    1211 10  參考I的情形。
    1211 9  參考H的情形。

12. 開始時是13根火柴，甲必輸，因為
    131211 10
    參考J的情形，但甲乙順序相反。
    1312
    假設乙不是笨蛋，乙不會取2，
    1312108
    如G，但甲乙順序相反；如此則讓甲有贏的機會。
    1311 （參考J的情形，但甲乙順序相反）
    1310 （參考I的情形，但甲乙順序相反）
    139 （參考H的情形，但甲乙順序相反）

        由以上的例子中可以觀察到，當火柴數為2, 3, 5, 8, 13時，對先取者不利。此外，當火柴數為4, 6, 9, 12時，先取者只要取1根，火柴數為7, 10時，取2根，火柴數為11時，取3根，就能立於不敗之地。

        繼續推演下去你會發現，只要開始時的火柴數為費氏數( Fibonacci numbers)，如2, 3, 5等，對先取者不利。（註：雖然1亦是費氏數，但不予考慮，因為若一開始的火柴數為1，則遊戲無法進行。）反之，若開始時的火柴數不為費氏數如10, 11, 12等，則先取者可贏，當然他得懂得其中的竅門。

        當一開始的火柴數n不是費氏數時，先取者甲該怎麼取才能拿到最後一根火柴？

        若n不是費氏數，則n一定可以寫成某些費氏數之和，而且這些費氏數在費氏數列中互不相鄰（證明）：

n = ++ … +,
其中 >> … >，
而且k₁k₂+2,  k₂k₃+2, … , k_r–1k_r+2。

此時，取上列費氏數中最小的數，甲就可以贏得勝利。
　

例如：

12可以寫成 12 = 8 + 3 + 1，其中 8 =, 3 =, 1 =，都不是相鄰的費氏數。因此，當開始的火柴數為12時，甲應取的火柴數即為費氏數8, 3, 1中最小的1。

又如：

4 = 3 + 1，甲應取1；
6 = 5 + 1，甲應取1；
7 = 5 + 2，甲應取2；
9 = 8 + 1，甲應取1；
10 = 8 + 2，甲應取2；
11 = 8 + 3，甲應取3；
15 = 13 + 2，甲應取2。