※ 引述《babufong (哔哔)》之铭言： : 325. Stone Game II : http://projecteuler.net/index.php?section=problems&id=325 : 这游戏的玩法是两个人与两堆石头。 : 在她的回合，她从较大堆的石头中移除掉一些石头。 : 移除掉的石头数量必须为较小堆石头的正整数倍。 : 举个例子，(6,14)表示为较小堆的石堆有6颗石头，较大堆的石堆有14颗石头 : 先手可以从较大堆的石堆中拿6或12颗石头。 : 从某一堆拿走全部石头的玩家就胜利。 : 必胜型指的是先手可以迫使局面成为先手胜利。例如：(1,5) , (2,6) 还有 (3,12) : 都是必胜型，因为先手可以马上移除掉较大堆的石堆中所有的石头。 : 必败型指的是後手可以迫使局面成为後手胜利，无论先手做了什麽动作。 : 例如：(2,3) 和 (3,4) 都是必败型，先手任何合法动作皆会留下一个必胜型给後手。 : 定义 S(N) 为所有必败型 (xi,yi) 且 0 < xi < yi <= N 中，(xi+yi) 的总和 : 我们可以知道 S(10) = 211 且 S(10^4) = 230312207313。 : 请算出 S(10^16) mod 7^10。 终於搞懂了为何黄金比例是欧氏对局的致胜关键，蔡教授写得太复杂了 我有一个简单的证明 假设拿到的y/x < (sqrt(5)+1)/2 = phi = 1.618.... 因为y是x的1倍多一点，故只有一种选择，从y拿掉x的1倍 y/x < (sqrt(5)+1)/2 可推得 x/(y-x) > sqrt(5)+1)/2 拿到小於phi的人，丢给对手的两堆比值永远是大於phi 那麽，再来看拿到y/x大於phi的人的选择 假设 (sqrt(5)+1)/2 < y/x < 2，那也只有一种选择，从y拿掉x的1倍 y/x > (sqrt(5)+1)/2 可推得 x/(y-x) < sqrt(5)+1)/2 假设 2 < y/x 令 y除x的余数是 c，玩者可以拿光x的最大倍数，剩c x/c的结果只有2种，大於phi或小於phi(不可能等於phi，因为phi是无理数) 如果小於phi， 那很好，丢给对手 如果大於phi呢? 由x/c > (sqrt(5)+1)/2，可推得c/x < (sqrt(5)-1)/2， 再推得(x+c)/x < (sqrt(5)+1)/2 由於 y/x > 2，是足够留下x+c 因此拿到大於phi的人，永远可以留下比值小於phi的两堆给对手 拿到小於phi的，y无法整除x，永远没办法拿光其中一堆的石头 而且永远只有一种选择，处於被动状态 拿到大於phi的人，可以一直立於不败之地，而且有较多的选择 直到对方丢回来的数字是其中一堆为另一堆的倍数，便可获胜 用一个例子来看： 假设一开始两堆是977跟96，这是先手必胜的局 让我们来看看是否先手必胜? 977除以96，余数是17，96/17 > phi，故要留下(96+17,96)给後手 後手别无选择，只能丢回(17,96)给先手 96除以17，余数为11，17/11 < phi，故留下(17,11)给後手 後手别无选择，只能丢回(6,11)给先手 11除以6，余数为5， 6/5 < phi，故留下(6,5)给後手 後手别无选择，只能丢回(1,5)给先手 先手拿光5!! 获胜! 由此可看出後手根本别无选择，只能任人宰割 先手从一开始就立於不败之地，等待胜利! --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 58.115.130.168 ※ 编辑: utomaya 来自: 58.115.130.168 (02/24 12:57)