ProjectEuler 325 Stone Game II - 拼圖

※ 引述《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!! 獲勝!

由此可看出後手根本別無選擇，只能任人宰割
先手從一開始就立於不敗之地，等待勝利!

--