※ 引述《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)