Re: [轉錄] 益智問題（拈 001,100，1枚~3倍）
假設先手不能全拿，小於等於4個就不討論了~
(1)當有5個石頭時，先手勝
就先拿一個，不管對方怎麼拿，都可以全部拿光
(2)當有6個石頭時，後手勝
先手不能拿超過兩個，不然對手直接拿光就輸了
所以先手只能拿一個，變成剩下五個，還是輸
(3)當有7個石頭時，先手勝
先手先拿一個，對方也只能跟著拿一個
這時剩下五個，先手勝
(4)當有8個石頭時，後手勝
先手不能拿超過兩個，不然對手直接拿光輸掉
先手拿一個，變成7個石頭的case，對方變成新的先手，獲勝
(5)當有9個石頭時，先手勝
拿一個石頭，然後變成8個石頭的case，原先手變成新的後手，新的後手勝
(6)當有10個石頭時，先手勝
拿兩個石頭，變成8個石頭的case，這時對手不能拿超過兩個
(7)當有11個石頭時，後手勝
因為這時先手要拿3個石頭才能變成8個石頭的case
但是若拿3個對手可以直接全部拿光，所以先手不會贏
(8)12個石頭，先手勝
先拿一個石頭變成11個石頭的case
(9)13個石頭，先手勝
先拿兩個石頭變成11個石頭的case
(10)14個，先手勝
先手拿3個
(11)15個石頭，後手勝
先手若拿4個會自爆
(12)16個石頭，先手勝
先拿一個石頭，變成15個石頭的case
......
以下類推
所以關鍵數應該是拿完後所剩的石頭數會是後手勝的case
到目前為止是6,8,11,15,20也是
感覺很像a(n)=a(n-1)+n 可惜不是(我一開始也以為答案錯)
不過這邊要借一下原PO的最大可取數
16取1 (表示若有16個石頭，先手先拿一個可以贏)
17取2
18取3
19取4 以上皆為先手勝
20取5 這一個先手贏不了，表示這種情況後手必勝
21取1
22取2
23取3
24取4 (以上這四組最大可取數量為5)
25取5
26取6 以上至此先手必勝
27取7 這一個先手會自爆，後手勝
28取8 (以上這四組最大可取數量為6)
當X取Y的最小Y大於可取數量Z時，該X為關鍵數 <--好爛的描述啊
這邊關鍵數為27
28取1 找到關鍵數後要重來
29取2
30取3
31取4
32取5 以上最大可取數量7
33取6
34取7
35取8
36取9 以上最大可取數量8
所以這邊關鍵數為36
37 1
38 2
39 3
40 4 最大可取為9
41 5
42 6
43 7
44 8 最大可取為10
45 9
46 10
47 11
48 12 最大可取為11
關鍵數為48
以下類推~不過在下寫不出漂亮的一般式啊
--
很像以前會作弄小朋友的一個題目
任寫兩個數字，比方說20,12
規則是可以兩邊同減一個數或者是任一邊減去一個數
(當然不能減到為負數)
兩人輪流，先讓兩邊同時為0者就是贏家
我過了好一陣子才知道為什麼一開始友人都以這兩個數字開頭並且讓我當先手啊~
※ 引述《O00O (喔喔喔喔)》之銘言：
: 簡單講一下,直覺這題應該是屬於NP,要解出來理論上要很久...
: 原文的解答,到15都是對的,不過20就錯了.
: 如果留20給對手,對手拿1,剩19還你,無法一手降到15,對方就可以走到15的安全局.
: 這題比較難是因為安全局不是一維的,要考慮前一手.
: 5->4是安全局,但是6->4就不是.
: 前面幾個安全局應該是:
: 5->4
: 7->6
: (9~10)->8
: (12~14)->11
: (16~19)->15
: 下一手就開始複雜了,我也懶得想了.
: ※ 引述《supermicro (清流是要流到哪裡去?)》之銘言：
: : 作者: sean0405 (灰) 看板: Math
: : 標題: 益智問題
: : 時間: Sun Apr 19 11:28:02 2009
: : 玩法：一堆石頭有100個，兩人輪流取石，每次每人至少取一個，最多取上次對方取走的
: : 石頭數的三倍。取走最後一個石頭的人贏得勝利。
: : 問題：請分析這個遊戲是對先手有利，還是對後手有利？為什麼？
: : 解答：
: : 規則之「下ㄧ人取最多數為前人之三倍」，表示每個數字之最大可取之量為總量÷4之商
: : ，總數如為4的倍數則可取之數為商-1。
: : 例如100÷4=25，整除所以最大可取之數為25-1=24。
: : 在此前提之下，先把問題簡化。從1倒算至關鍵數「8」，接著發現後兩數「9、10」之最
: : 大可取數量為2，而11也為2。無法把對方逼到「8」，因此認定「11」也是關鍵數，接著
: : 繼續往後推算發現15、20、27、36、48、64、86也均為關鍵數，所以在石頭數100顆的情
: : 形下，先手取14顆剩下86顆則必勝。
: : 有高手能清楚說明解答過程的嗎？感謝囉..
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.70.151.17
※ 編輯: homeik 來自: 219.70.151.17 (04/20 23:43)
※ 編輯: homeik 來自: 219.70.151.17 (04/20 23:47)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 4 之 10 篇)：