石子游戲的理論證明

1067：石子游戲的理論證明王靖軒Wythoffgame(威佐夫博弈)取石子游戲?qū)嶋H上是荷蘭人wythoff在1907年提出的。它屬于一種Nim博弈，后人也把這類問(wèn)題叫做wythoff博弈另外一種不同的表示法關(guān)于取石子問(wèn)題有另外一種表示方法(如右圖)兩人輪流控制一個(gè)國(guó)際象棋的(棋子)皇后。每一次行動(dòng)可以向左或向下走，或向左斜下方前進(jìn)。最后走到(0,0)的人為負(fù)很顯然的，這個(gè)問(wèn)題與取石子的問(wèn)題等價(jià)如何考慮博弈問(wèn)題關(guān)于博弈問(wè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)：通過(guò)一步變化可以轉(zhuǎn)化為必負(fù)態(tài)的形式先手必負(fù)態(tài)：所有一步變化均為先手必勝態(tài)的可以隱約的感覺(jué)到，(先手)必負(fù)態(tài)少而必勝態(tài)多必勝態(tài)與必負(fù)態(tài)分布對(duì)于1067而言…1067要求判定輸入是否必負(fù)，而沒(méi)有要求必須計(jì)算出其他狀態(tài)是否必負(fù)但是一般的解決思路:本狀態(tài)是否為必負(fù)取決于其自裝態(tài)是否有必負(fù)態(tài)進(jìn)行全盤(pán)搜索=高時(shí)間/空間復(fù)雜度輸入的數(shù)據(jù)越大越明顯(a=1618033988700b=2618033988700)所以我們需要尋找更簡(jiǎn)單的辦法！從觀察開(kāi)始首先觀察幾個(gè)數(shù)值較小的必負(fù)態(tài)組合12354761081391511181220142316261728可能存在的關(guān)系Bn=An+N？{An}∩{Bn}=Φ？Bn/An->常數(shù)？與Fibonacci數(shù)列有關(guān)？12354761081391511181220142316261728繼續(xù)觀察…每一個(gè)必負(fù)態(tài)的橫、縱、(左下-右上)斜行不存在另一個(gè)必負(fù)態(tài)由于(2,1)等價(jià)于(1,2)，我們可以只看45°之下的部分我們需要的是通項(xiàng)公式！猜想+證明{An}、{Bn}存在通項(xiàng)公式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)與必?cái)B(tài)的限制及分布規(guī)律數(shù)字不重復(fù)出現(xiàn)->有重復(fù)出現(xiàn)則說(shuō)明該狀態(tài)通過(guò)一步變化可達(dá)到之前的某一必?cái)B(tài)Bn=An+n->必然不存在(i<n) 使得Bi+x=Bn且Ai+x=An->一個(gè)必?cái)B(tài)的左下/右上不存在另一必?cái)B(tài)引理：Beatty定理及相關(guān)證明Beatty定理：存在無(wú)理數(shù)a,b，滿足 1/a+1/b=1An={floor(na)n是自然數(shù)} Bn={floor(nb)n是自然數(shù)}An、Bn構(gòu)成一個(gè)關(guān)于自然數(shù)集的劃分即{An}∩{Bn}=Φ且{An}∪{Bn}=NBn={floor(nb)n是自然數(shù)}故在小于等于L的所有自然數(shù)中x必屬于{An}{Bn}其中之一1067要求判定輸入是否必負(fù)，而沒(méi)有要求必須計(jì)算出其他狀態(tài)是否必負(fù)=floor(nφ)+n驗(yàn)證Bn/An的關(guān)系即可{An}∩{Bn}=Φ？大家有機(jī)會(huì)還是應(yīng)該看看Wythoff的原文，畢竟那是他老人家一輩子最偉大的成就=floor(nφ)+n1067要求判定輸入是否必負(fù)，而沒(méi)有要求必須計(jì)算出其他狀態(tài)是否必負(fù)An、Bn構(gòu)成一個(gè)關(guān)于自然數(shù)集的劃分先手必負(fù)態(tài)：所有一步變化均為先手必勝態(tài)的因?yàn)閠、i、j均為正整數(shù)，所以矛盾！-> (L+1)/a-1<u<(L+1)/a數(shù)字不重復(fù)出現(xiàn)->有重復(fù)出現(xiàn)則說(shuō)明該狀態(tài)通過(guò)一步變化可達(dá)到之前的某一必?cái)B(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}=Φ？因?yàn)閠、i、j均為正整數(shù)，所以矛盾！對(duì)于小于L的自然數(shù)，所有的必?cái)B(tài)都符合通向公式每一個(gè)必負(fù)態(tài)的橫、縱、(左下-右上)斜行不存在另一個(gè)必負(fù)態(tài){An}{Bn}構(gòu)成自然數(shù)集的一個(gè)劃分=floor(nφ)+n{An}、{Bn}存在通項(xiàng)公式故可以構(gòu)造Beatty序列，使得{An}{Bn}構(gòu)成自然數(shù)集的一個(gè)劃分到此為止1067已經(jīng)很簡(jiǎn)單了證明{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因?yàn)閠、i、j均為正整數(shù)，所以矛盾！所以不存在這樣的元素t既屬于{An}又屬于{Bn}證明{An}∪{Bn}=N任取一個(gè)自然數(shù)L，對(duì)于小于等于L的任意自然數(shù)x,欲證x或者屬于{An}或者屬于{Bn}An中小于等于L的元素有u=floor((L+1)/a)個(gè)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)個(gè)元素小于等于L u+v<L+1<u+v+2 u+v=L故在小于等于L的所有自然數(shù)中x必屬于{An}{Bn}其中之一通項(xiàng)公式滿足必?cái)B(tài)1，數(shù)字不重復(fù)出現(xiàn)2，An+n=Bn證明：令φ=aφ2=b因?yàn)?/a+1/b=1 故可以構(gòu)造Beatty序列，使得 {An}{Bn}構(gòu)成自然數(shù)集的一個(gè)劃分 =數(shù)字必不重復(fù)出現(xiàn) 1得證通項(xiàng)公式滿足必?cái)B(tài)2，證明：因?yàn)棣?1=φ2

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

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