※ 引述《supermicro (清流是要流到哪里去?)》之铭言： : ※ [本文转录自 Math 看板] : 作者: 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颗则必胜。 : 有高手能清楚说明解答过程的吗？感谢罗.. 答案是对的，我是用逆向推理 轮到自己时的状态以(m, n)表示剩m颗石头，上一手取走n颗 一开始知道以下是必赢的状态 (1, N) (2, N) (3, N) N表示正整数 因为n最少为1，故玩家能取走剩余全部石头 另外，(m, n >= m/3)也是必赢状态，因为玩家这一手能够取走全部石头 ... 称此为X (4, 1)是必输的状态，因为只能取走1~3颗，皆会落入对方必赢状态 因为X，(4, n >= 2)必赢 是故从(4, 1)只能导致其後一组必赢状态: (5, N) (6, 1)是必输的状态，因为取走1~3颗分别落入对方必赢状态(5, N) (4, n>=2) (3, N) 因为X，(6, n >= 2)必赢 从(6, 1)同样只能导致其後一组必赢状态: (7, N) 接下来开始不同了，(8, n <= 2)皆为必输状态，因为取走1~6颗会落入对方必赢状态 (7, N) (6, n >= 2) (5, N) (4, n >= 2) (3, N) (2, N) 因为X，(8, n >= 3)必赢 从(8, n <= 2)可以导致其後两组必赢状态: (9, N) (10, N) 玩家分别取走1颗或2颗即可令对方陷入(8, n <= 2) 我想规律从这边开始应该就比较清楚了 (11, n <= 3)必输 接下来3组(12~14, N)必赢 (15, n <= 4)必输 接下来4组(16~19, N)必赢 ... (64, n <= 21)必输 接下来21组(65~85, N)必赢 (86, n <= 28)必输 故取走14颗，对方陷入(86, 14)必输 必输状态为(m(k), n < m(k)/3) m(1) = 4, m(k) = m(k-1) + ceiling(m(k-1)/3) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 128.61.82.163 ※ 编辑: ars1an 来自: 128.61.82.163 (04/22 10:05)