石子游戲的理論證明

1067：石子游戲的理論證明王靖軒Wythoffgame(威佐夫博弈)取石子游戲?qū)嶋H上是荷蘭人wythoff在1907年提出的。它屬于一種Nim博弈，后人也把這類問題叫做wythoff博弈另外一種不同的表示法關(guān)于取石子問題有另外一種表示方法(如右圖)兩人輪流控制一個國際象棋的(棋子)皇后。每一次行動可以向左或向下走，或向左斜下方前進(jìn)。最后走到(0,0)的人為負(fù)很顯然的，這個問題與取石子的問題等價如何考慮博弈問題關(guān)于博弈問題，一般需要進(jìn)行搜索。2，12，01，11，00，00，00，0更一般性的規(guī)律若(a,b)為先手必負(fù)的狀態(tài)如(2,1)(5,3)則(a+k,b)(a,b+k)(a+k,b+k)均為先手必勝態(tài)如何判定必勝態(tài)與必負(fù)態(tài)先手必勝態(tài)：通過一步變化可以轉(zhuǎn)化為必負(fù)態(tài)的形式先手必負(fù)態(tài)：所有一步變化均為先手必勝態(tài)的可以隱約的感覺到，(先手)必負(fù)態(tài)少而必勝態(tài)多必勝態(tài)與必負(fù)態(tài)分布對于1067而言…1067要求判定輸入是否必負(fù)，而沒有要求必須計算出其他狀態(tài)是否必負(fù)但是一般的解決思路:本狀態(tài)是否為必負(fù)取決于其自裝態(tài)是否有必負(fù)態(tài)進(jìn)行全盤搜索=高時間/空間復(fù)雜度輸入的數(shù)據(jù)越大越明顯(a=1618033988700b=2618033988700)所以我們需要尋找更簡單的辦法！從觀察開始首先觀察幾個數(shù)值較小的必負(fù)態(tài)組合12354761081391511181220142316261728可能存在的關(guān)系Bn=An+N？{An}∩{Bn}=Φ？Bn/An->常數(shù)？與Fibonacci數(shù)列有關(guān)？12354761081391511181220142316261728繼續(xù)觀察…每一個必負(fù)態(tài)的橫、縱、(左下-右上)斜行不存在另一個必負(fù)態(tài)由于(2,1)等價于(1,2)，我們可以只看45°之下的部分我們需要的是通項公式！猜想+證明{An}、{Bn}存在通項公式An=floor(nφ)；Bn=floor(nφ)+nFloor()為取下整函數(shù)，floor(1.5)=1φ=(1+√5)/2=1.618…φ+1=φ2

Bn=floor(nφ2)Bn/An->φ！證明(必要條件)重要的是要滿足題目中關(guān)于必勝態(tài)與必敗態(tài)的限制及分布規(guī)律數(shù)字不重復(fù)出現(xiàn)->有重復(fù)出現(xiàn)則說明該狀態(tài)通過一步變化可達(dá)到之前的某一必敗態(tài)Bn=An+n->必然不存在(i<n) 使得Bi+x=Bn且Ai+x=An->一個必敗態(tài)的左下/右上不存在另一必敗態(tài)引理：Beatty定理及相關(guān)證明Beatty定理：存在無理數(shù)a,b，滿足 1/a+1/b=1An={floor(na)n是自然數(shù)} Bn={floor(nb)n是自然數(shù)}An、Bn構(gòu)成一個關(guān)于自然數(shù)集的劃分即{An}∩{Bn}=Φ且{An}∪{Bn}=NBn={floor(nb)n是自然數(shù)}故在小于等于L的所有自然數(shù)中x必屬于{An}{Bn}其中之一1067要求判定輸入是否必負(fù)，而沒有要求必須計算出其他狀態(tài)是否必負(fù)=floor(nφ)+n驗證Bn/An的關(guān)系即可{An}∩{Bn}=Φ？大家有機(jī)會還是應(yīng)該看看Wythoff的原文，畢竟那是他老人家一輩子最偉大的成就=floor(nφ)+n1067要求判定輸入是否必負(fù)，而沒有要求必須計算出其他狀態(tài)是否必負(fù)An、Bn構(gòu)成一個關(guān)于自然數(shù)集的劃分先手必負(fù)態(tài)：所有一步變化均為先手必勝態(tài)的因為t、i、j均為正整數(shù)，所以矛盾！-> (L+1)/a-1<u<(L+1)/a數(shù)字不重復(fù)出現(xiàn)->有重復(fù)出現(xiàn)則說明該狀態(tài)通過一步變化可達(dá)到之前的某一必敗態(tài)Bn={floor(nb)n是自然數(shù)}證明{An}∩{Bn}=Φ與Fibonacci數(shù)列有關(guān)？t<ia<t+1->t/a<i<(t+1)/a①-> (L+1)/a-1<u<(L+1)/a先手必負(fù)態(tài)：所有一步變化均為先手必勝態(tài)的{An}∩{Bn}=Φ？因為t、i、j均為正整數(shù)，所以矛盾！對于小于L的自然數(shù)，所有的必敗態(tài)都符合通向公式每一個必負(fù)態(tài)的橫、縱、(左下-右上)斜行不存在另一個必負(fù)態(tài){An}{Bn}構(gòu)成自然數(shù)集的一個劃分=floor(nφ)+n{An}、{Bn}存在通項公式故可以構(gòu)造Beatty序列，使得{An}{Bn}構(gòu)成自然數(shù)集的一個劃分到此為止1067已經(jīng)很簡單了證明{An}∩{Bn}=Φ反證法：假設(shè)存在t屬于{An}∩{Bn}，則由定義有t=floor(ia)=floor(jb)i,j均為自然數(shù)t<ia<t+1->t/a<i<(t+1)/a①t<jb<t+1->t/a<j<(t+1)/b②①+②->t(1/a+1/b)<i+j<(t+1)(1/a+1/b) ->t<i+j<t+1因為t、i、j均為正整數(shù)，所以矛盾！所以不存在這樣的元素t既屬于{An}又屬于{Bn}證明{An}∪{Bn}=N任取一個自然數(shù)L，對于小于等于L的任意自然數(shù)x,欲證x或者屬于{An}或者屬于{Bn}An中小于等于L的元素有u=floor((L+1)/a)個floor(ua)<=LANDfloor((u+1)/a)>=L+1-> (L+1)/a-1<u<(L+1)/a-> u=floor((L+1)/a)Bn則同理,有v=floor(L+1/b)個元素小于等于L u+v<L+1<u+v+2 u+v=L故在小于等于L的所有自然數(shù)中x必屬于{An}{Bn}其中之一通項公式滿足必敗態(tài)1，數(shù)字不重復(fù)出現(xiàn)2，An+n=Bn證明：令φ=aφ2=b因為1/a+1/b=1 故可以構(gòu)造Beatty序列，使得 {An}{Bn}構(gòu)成自然數(shù)集的一個劃分 =數(shù)字必不重復(fù)出現(xiàn) 1得證通項公式滿足必敗態(tài)2，證明：因為φ+1=φ2

Bn=floor(nφ2) =floor(nφ)+n =An+n 2證畢綜上，通項公式的元素必滿足必敗態(tài)條件必要條件證畢！充分條件？！利用必要條件+歸納法證明對于小于L的自然數(shù)，所有的必敗態(tài)都符合通向公式那么等于L的那組必敗態(tài)也必符合通項公式或反證，假設(shè)存在一個必敗態(tài)(a,b)不在通項公式內(nèi)，證明其必然不是一個必敗態(tài) 因為已有通項公式的必敗態(tài)覆蓋了所有其他情況，所以無論(a,b)取何值，必然可以一步內(nèi)找到一個通項公式內(nèi)的必敗態(tài)

1234567891011121314151611011111111111111201111111111111113xx110111111111114xxx11101111111115xx0x1111111111116xxxxx111101111117xxx0xx11111111118xxxxxxx1111101119xxxxxxxx1111110110xxxxx0xxx111111111xxxxxxxxxx11111112xxxxxxxxxxx1111113xxxxxxx0xxxx111114xxxxxxxxxxxxx11115xxxxxxxx0xxxxx1116xxxxxxxxxxxxxxx1Floor()為取下整函數(shù)，floor(1.假設(shè)存在t屬于{An}∩{Bn}，則由定義有1067要求判定輸入是否必負(fù)，而沒有要求必須計算出其他狀態(tài)是否必負(fù)Wythoff在1907年的論文到處都找不到了1067要求判定輸入是否必負(fù)，而沒有要求必須計算出其他狀態(tài)是否必負(fù)An={floor(na)n是自然數(shù)}φ+1=φ2Bn=floor(nφ2)可以隱約的感覺到，(先手)必負(fù)態(tài)少而必勝態(tài)多最后走到(0,0)的人為負(fù)An、Bn構(gòu)成一個關(guān)于自然數(shù)集的劃分{An}、{Bn}存在通項公式-> u=floor((L+1)/a)大家有機(jī)會還是應(yīng)該看看Wythoff的原文，畢竟那是他老人家一輩子最偉大的成就An中小于等