﹝前言﹞
數學系圖書館新進的大陸書，《300個最新世界著名數學
智力趣題》一書中所挑出的題目。
﹝問題﹞
Nim是種雙人玩的遊戲，最常見的搶30大概是最簡單的一種。有一定
數量的棋子，兩人輪流取子(取子有一些固定的限制)，取到最後一顆
為勝(有些規則為敗)。
現在的問題是有1000顆棋子，兩人輪流取，但每次取時要為 p^i個棋
子(p是質數，i是非負整數)，能取到最後一顆者為勝，問在這1000顆
的情形下，要當先手或後手，怎樣的策略是必勝取法。
如甲先取 5^4=625 剩 375個，
乙再取 101^1=101 剩 274個，
甲再取 2^7=256 剩 18個，
乙再取 2^0=1 剩 17個，
甲再取 17^1=17 剩 0個。
故甲取到最後一個，因此甲獲勝。
﹝備註﹞
關於 Nim還有各種不同的變形，以後有機會再陸續介紹，或者等其他網
友補充。我高中時曾花了很多時間去想" Nim三角形"，許久的時間下來
，只是很死的畫出樹狀圖，得出先手為勝，但沒什麼好的策略。或許等
待其他網友是否有其他好的方法，或知相關的文獻資料。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.249.83
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.249.83
※ 編輯: arist 來自: 140.112.249.83 (06/02 12:09)
> -------------------------------------------------------------------------- <
作者: smartboy (爛掉了爛掉了) 看板: puzzle
標題: Re: 【雙人遊戲】Nim,籌碼遊戲
時間: Mon Jun 3 23:59:49 2002
※ 引述《arist ( 川 )》之銘言：
: 關於 Nim還有各種不同的變形，以後有機會再陸續介紹，或者等其他網
: 友補充。我高中時曾花了很多時間去想" Nim三角形"，許久的時間下來
: ，只是很死的畫出樹狀圖，得出先手為勝，但沒什麼好的策略。或許等
: 待其他網友是否有其他好的方法，或知相關的文獻資料。
我是知道系上教授曾做過用電腦來下這種棋, 細節我就不清楚了
http://www.csie.ntu.edu.tw/~schsu/b5/publish.html
S.C. Hsu,“ 三角殺棋的電腦解法及其實現” ，
電腦季刊, 第16 卷, 第4 期, pp.15-23, Dec. 1982.
S. C. Hsu, “ 利用電腦探討七層三角殺棋的勝負問題” ，
Proc. of 1985 NCS, pp. 798-802, Dec. 1985.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.70.142.187
> -------------------------------------------------------------------------- <
作者: hiei81 (域外悠風) 看板: puzzle
標題: Re: 【雙人遊戲】Nim,籌碼遊戲
時間: Sat Jun 8 22:56:32 2002
※ 引述《arist ( 川 )》之銘言：
: : ﹝問題﹞
: : 現在的問題是有1000顆棋子，兩人輪流取，但每次取時要為 p^i個棋
: : 子(p是質數，i是非負整數)，能取到最後一顆者為勝，問在這1000顆
: : 的情形下，要當先手或後手，怎樣的策略是必勝取法。
: : 如甲先取 5^4=625 剩 375個，
: : 乙再取 101^1=101 剩 274個，
: : 甲再取 2^7=256 剩 18個，
: : 乙再取 2^0=1 剩 17個，
: : 甲再取 17^1=17 剩 0個。
: : 故甲取到最後一個，因此甲獲勝。
: 這題的答案其實蠻簡潔的 都沒人想回答看看嗎
每次取完剩6的倍數即可~:)
所以1000取4個是解, 當然取16個也是解...
且唯一的必勝取法是先手取4,16,64,256四種...
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.18.93
> -------------------------------------------------------------------------- <
作者: hiei81 (域外悠風) 看板: puzzle
標題: Re: 【雙人遊戲】Nim,籌碼遊戲
時間: Sat Jun 8 23:03:54 2002
※ 引述《hiei81 (域外悠風)》之銘言：
: ※ 引述《arist ( 川 )》之銘言：
: : 這題的答案其實蠻簡潔的 都沒人想回答看看嗎
: 每次取完剩6的倍數即可~:)
: 所以1000取4個是解, 當然取16個也是解...
: 且唯一的必勝取法是先手取4,16,64,256四種...
首先考慮從一個開始,
1,2,3,4,5先手必可一次取完, 但6不行,
故勝6個後手必勝, 所以先手取完剩6個即必勝...
6是必勝型, 則先手取完剩7,8,9,10,11都會輸,
但先手取完剩12個也會贏, 故12又是必勝形,
接下來的工作只需證明必勝形就是所有六的倍數,
最後, 1000拿完剩六的倍數必須拿掉偶數個
故n為偶數, 又n=p^i, p是質數, 故p=2
=>1000-2^i是六的倍數=> 500-2^(i-1)是三的倍數,
可以發現i是偶數...
故2^2, 2^4, 2^6, 2^8事先手必勝的取法:)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.18.93