拈（節錄） - 拼圖

※ 引述《jimasd (海水正藍)》之銘言：
: ※ [本文轉錄自 Math 看板 #1CTgdoQ4 ]
: 作者: jimasd (海水正藍) 看板: Math
: 標題: [其他] 趣味數學
: 時間: Fri Aug 27 01:52:47 2010
: 現在有20個豆子 分成3堆
: 每堆豆子數量都不同
: 假設有2個人玩遊戲
: 規則：甲先拿可以從A.B.C其中選1堆（只能拿你選的那堆）拿取任何數量的豆子（最少1顆
: ）換乙 同上方法 兩人互相交替 誰拿到所有最後1個就輸了
: 問題1.假設A堆只有1顆 剩下2堆 奇數個>偶數個 要怎樣抓 反過來偶數個>奇數個
: 要怎樣抓
: 問題2.假設A堆只有2顆 剩下2堆 偶數個（B堆）>偶數個（C堆） 要怎樣抓
: 反過來 奇數個（B堆）>偶數個（C堆）
: .
: .
: .
: 當A堆數量慢慢增加時 在對應B.C堆應該要如何抓
: 不知道是否有通式？？
: 還有如果雙方都知道必勝法則 那誰先誰後才能必贏
: ------------------------------------------------------------------------------
: 第一次在這po文 如有不清楚的 可以發問 也請各位多包涵

以下摘自「寓數學於遊戲」第二輯 趙文敏編著
P.74 拈（一）
------------------
取一些棋子，分成若干堆
兩人輪流從其中拿走一些棋子
取走最後一粒的人獲勝

但每人每次只少要取走一粒
而且所拿走的棋子必須是在同一堆裡
（即在一堆中可取1或取全部，一次不能取不同堆）
------------------
本世紀初 Charles Bouton 曾對它的數學道理作了一番詳盡的剖析
只需使用二進位法


二進位表示法：
5 = (0101)
10 = (1010)
15 = (1111)
------------------
必勝法：二進位維持各位數個別和均為偶數即可

例如：
（一）遊戲一開始有三堆，分別為 3、5、7 個
表示成二進位：
3 = (011)
5 = (101)
7 = (111)

把這表示成的二進位，三位數分開看，個別加起來
總和為 (223)
所以此時必勝法，就是將結果變成 (222)
也就是拿掉 (001)

所以可以選擇從 3 的那堆拿掉 1 個，變成 2、5、7
或是從 5 的那堆拿掉 1 個，變成 3、4、7
或是從 7 的那堆拿掉 1 個，變成 3、5、6

只要維持你拿後的結果，各位數個別和均為偶數即可
------------------
理由很簡單：
表示成二進位後，各位數個別和均為偶數的狀況
不論接著拿掉哪一種
各位數個別和必至少有一為奇數
而接著可以減去某一數，又可回到各位數個別和均為偶數的狀況

拿掉最後一個，各位數個別和均為 0，均為偶數
所以只要維持 (全偶)-(非全偶)-(全偶)-(非全偶)-... 的情勢
最後你必可拿到最後一個
（詳細證明可參考該書）
------------------
再來看一種比較複雜的例子：
（二）遊戲一開始有四堆，分別為 3、5、7、9 個
你要選擇先，還是後？

表示成二進位
3 = (0011)
5 = (0101)
7 = (0111)
9 = (1001)
和 (1224)

所以我們選擇先
從 9 的那堆拿掉 8 個，變成
3 = (0011)
5 = (0101)
7 = (0111)
1 = (0001)
和 (0224)

接著假如對方從 7 的那堆拿掉 3 個，變成
3 = (0011)
5 = (0101)
4 = (0100)
1 = (0001)
和 (0213)

我們選擇
★從 3 的那堆拿掉 3 個（全部），變成
0 = (0000)
5 = (0101)
4 = (0100)
1 = (0001)
和 (0202)

接著假如對方從 4 的那堆拿掉 1 個，變成
0 = (0000)
5 = (0101)
3 = (0011)
1 = (0001)
和 (0111)

我們選擇
★從 5 的那堆拿掉 3 個（全部），變成
0 = (0000)
2 = (0010)
3 = (0011)
1 = (0001)
和 (0022)

（後續略，打★部分要動一點腦筋想）
這樣就立於不敗之地
注意拿的時候不是隨意拿
而是要考慮拿了以後，變成各位數個別和均為偶數的狀況

------------------
------------------
P.78 拈（二）
拈的變形
Wythoff 遊戲（似乎是原 PO 說的威氏）

一開始只有兩堆（數目不一定一樣）
每個人可以在一堆取任意個數
或同時在兩堆取相同個數
取到最後一個者勝

必勝法：
取完後讓剩下兩堆的數字
個別表示成數個費布納西(Fabonacci)數字的和

符合情況：
第一堆 F(n1)+F(n2)+....+F(nr)
第二堆 F(n1+1)+F(n2+1)+....+F(nr+1)

你就必勝

例如拿後剩下 24、39
24 = F(8)+F(4)
39 = F(9)+F(5)


費布納西(Fabonacci)數列：
1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , ....
F(1)=F(2)=1，F(n)=F(n-1)+F(n-2)在n≧3時

例如：
兩堆棋子分別為 15、23 個
因為
15 = F(7) + F(3)
23 = F(8) + F(3)
符合上面情況
所以讓對方先拿

假如對方從 23 那堆拿走 12 個，
15 = F(7) + F(3)
11 = F(6) + F(4)

你從兩堆同時拿走 5 個棋子
10 = F(6) + F(3)
6 = F(5) + F(2)
符合上面情況

（後續略）
證明可參考本書，或網路資料

--
rehearttw 許老師（Reheart-易懷），愛生公式，愛胡思亂想
自 1980 年摸魔術方塊，1981 年學基本公式，2006 年學 CFOP
許技江的第五個魔術方塊網頁 http://teach.ymhs.tyc.edu.tw/t1086/R-C.htm
縮網址：http://ppt.cc/DHXY （98/1/6換址）
益智玩具：http://teach.ymhs.tyc.edu.tw/t1086/puzzle.htm http://ppt.cc/lOY8
個人網頁：http://ppt.cc/7~wQ 請多多指教！

--