我數(shù)學(xué)特強(qiáng)《我數(shù)學(xué)特強(qiáng)》通解是存在的！如下：

《我數(shù)學(xué)特強(qiáng)》有沒有萬能公式呢？很久之前，一開始玩的時候，就想過這個問題，但面對復(fù)雜的變換路徑，我完全沒有頭緒。

最近的研究讓我找到了通用的解法，這不是用程序暴力搜索答案，也不是簡要的技巧，而是公式化的解法。另外，游戲里要求使用最少步數(shù)的最優(yōu)解，而通解一般不限步數(shù)。

介紹一下游戲。有三個自然數(shù)，玩家每次操作可以對這三個數(shù)進(jìn)行分配，我稱為偶變換和奇變換，偶變換是把一個偶數(shù)減半并將減半的部分加到另一個數(shù)上，奇變換是把一個奇數(shù)加到另一個數(shù)上，然后將其變?yōu)?。實(shí)際上，奇變換不限奇數(shù)，因?yàn)閷⑴紨?shù)奇變換給另一個數(shù)，可以先一直偶變換直到變?yōu)槠鏀?shù)，再進(jìn)行奇變換。游戲的最終目標(biāo)是得到三個相等的數(shù)，用三元數(shù)組表示為{x, x, x}，不過顯然只要三個數(shù)里有x或2x就能得到{x, x, x}。

有通解的前提是有解，而有解的充要條件是，三個數(shù)的最大公約數(shù)g整除x（可表示為g|x），且三個數(shù)不是一零二奇。先證明必要性，og和og'分別為三個數(shù)變換前后的最大奇公約數(shù)，易證og|og'，如果og'=x，則og|x，也就是說如果得到了{(lán)x,x,x}，則有og|x，因此og|x是有解的必要條件。另外，由g=(a,b,c)（三個數(shù)a,b,c的最大公約數(shù)寫法為(a,b,c)），可得g|3x，令g=og*2^m，則(og*2^m)|3x，(2^m)|(3x/og)，而(2^m,3)=1，所以(2^m)|(x/og)，(og*2^m)|x，可得g|x也是有解的必要條件，其逆否命題為，若g不整除x，則無解，而(0,0,3x)不整除x，一零兩奇時只能奇變換為{0,0,3x}，兩者等價(jià)，所以三數(shù)不是一零兩奇也是有解的必要條件。至于充分性，如果我們找到了g|x且不是一零兩奇情況下的解法，就相當(dāng)于將其證明了。

通解討論的數(shù)組默認(rèn)已通過以上判別法篩選，以保證有解及證明充分性。但要注意，有解的數(shù)組在變換后不一定有解，通解的操作應(yīng)當(dāng)保證數(shù)組在變換后依然可解，時刻有g(shù)|x。

下面的是我早期想的通解，經(jīng)過計(jì)算機(jī)驗(yàn)證，x為奇數(shù)時，x>17后出現(xiàn)反例：

一、有x或2x則結(jié)束。

三、若三數(shù)都是正數(shù)，且不是兩奇一偶，則嘗試將其中一個數(shù)加給另外兩個數(shù)中的一個數(shù)，選擇三種操作進(jìn)行后g整除x的數(shù)組；若三數(shù)都是正數(shù)，且兩奇一偶，則將兩奇數(shù)相加，或?qū)⑴紨?shù)分配給兩奇數(shù)使其變?yōu)閮膳紨?shù)，選擇兩種操作進(jìn)行后g整除x的數(shù)組。

四、若數(shù)組中沒有g(shù)*2^k滿足g*2^k>=x，k是自然數(shù)，則不斷在兩正數(shù)之間進(jìn)行偶變換（如果x是偶數(shù)，則需要保證兩數(shù)都是偶數(shù)），如果找到g*2^k，則跳到步驟六。

五、在步驟四的循環(huán)中選擇含有數(shù)被4整除得奇數(shù)（且該數(shù)減半小于x）的數(shù)組（如果x是偶數(shù)則選擇被2整除的），將該數(shù)偶變換給0，再重新在兩數(shù)之間不斷進(jìn)行偶變換（如果x是偶數(shù)，則需要保證兩數(shù)都是偶數(shù)），出現(xiàn)g*2^k則結(jié)束，將另兩個數(shù)合并。

六、用二進(jìn)制數(shù)表示x/g，在左邊補(bǔ)充0直到位數(shù)等于k，從最高位到最低位，若為1則將g*2^k分配給0（或者是步驟五中得到g*2^k一半的數(shù)），為0則分配給另一個數(shù)。這樣就得到了x，結(jié)束。

雖然有很多漏洞，但大框架是對的。在下文逐步分析后，我們將會推導(dǎo)出一個正確的通解。

直接得到通解可能是困難的，于是我想著要不然先解決什么樣的組合是可解的問題吧。反復(fù)觀察變換路徑后，我猜測g整除x應(yīng)該和有解相關(guān)，并且還發(fā)現(xiàn)了og在變換的過程中不變或變大，而且變換后的og整除變換前的og。

然后，我再想的是解決相對簡單的數(shù)組。在三個數(shù)之間變換是復(fù)雜的，暫未發(fā)現(xiàn)規(guī)律，所以我研究了只有一個數(shù)為0的數(shù)組。如果三個正數(shù)的數(shù)組都能轉(zhuǎn)變?yōu)橐涣銉烧?，那么通解問題就可以歸約到一零兩正如何變換出x或2x的問題。

我們需要保證三正變兩正后，g依然滿足g|x。如何操作呢？對于{a,b,c}，奇變換后得到的{0,a+b,c}, {0,b,a+c}和{a,0,b+c}三個數(shù)組中，一定有一個數(shù)組的g滿足g|x。

證明：3x的質(zhì)因數(shù)分解為m*3^n，(m,n)=1。先假設(shè)三個數(shù)組的g都不整除x。(a+b,c)=(3x,c)，(a+c,b)=(3x,b)，(b+c,a)=(3x,a)如果都不整除x，則(3^n)|(a,b,c)，又因?yàn)?a,b,c)|x，可得(3^n)|x，但3x=m*3^n，(m,3)=1，矛盾。

兩奇一偶時（該偶數(shù)不為0），以上的三種操作可能會讓數(shù)組變?yōu)橐涣銉善?，因此我們要對該類情況作調(diào)整，它有兩種變換：一、兩奇相加；二、偶數(shù)拆分為兩奇數(shù)，分別加給另外兩奇數(shù)。這兩種變換會使三正變一零兩偶，且至少有一種使得g|x，證明類似上一個，不再贅述。這樣的話，我們就將前面提到的可解的數(shù)組都轉(zhuǎn)化為一零兩正了。

前面說過{0,0,3x}是無解的，兩個正數(shù)不能奇變換，那當(dāng)然就只好偶變換了。當(dāng)x為奇數(shù)時，兩個數(shù)一奇一偶，偶變換的對象（即哪個數(shù)給另一個數(shù)一半）是確定的，得到的下一數(shù)組是唯一的。再加上數(shù)組的和是不變的，這樣的數(shù)組個數(shù)有限，所以，經(jīng)過有限次偶變換后，一定會回到原來的數(shù)組，形成偶變換循環(huán)。當(dāng)x為偶數(shù)時，偶變換的路徑是不唯一的，且不一定能不斷偶變換，變換后還可能是一零兩奇，比如{2,10}。x為偶數(shù)的這種情況，后續(xù)在改進(jìn)偶變換的時候再提及。

我們的目標(biāo)是在循環(huán)中找到t*2^k，t*2^k>=x，t|x，k>0，因?yàn)樵谟腥齻€數(shù)時，將t*2^k偶變換分解，可以得到小于t*2^k任意一個自然數(shù)。但循環(huán)中并不一定有t*2^k（比如{5,28}），所以在早期的想法中，我想打破原有循環(huán)，把偶數(shù)偶變換分給第三個數(shù)，使得原來循環(huán)的兩個數(shù)進(jìn)入新的循環(huán)，以找到t*2^k。

在{a,b}的偶變換循環(huán)中，如果我們只關(guān)注其中一個數(shù)a，可以發(fā)現(xiàn)該數(shù)在作如下變換：偶數(shù)時減半，奇數(shù)時加上sum再減半，sum=a+b。冰雹猜想里的變換會迭代至2^k，而這里，迭代至t*2^k，a和sum要滿足的所有條件是什么，是個open的問題。修改了幾次進(jìn)入新循環(huán)的方法后，程序依然發(fā)現(xiàn)反例。所以，探尋如何修正a和sum進(jìn)入新的含有t*2^k的循環(huán)，這條路暫時行不通。

不小于x的t*2^k一定和小于x的t*2^k在同一循環(huán)中，找到其中一個便能找到其余的t*2^k。但要得到新的循環(huán)，就要將參與偶變換循環(huán)的兩數(shù)之和sum減小，而最大的t*2^k滿足t*2^k sum/2。

這樣我們就有一個新的思路，先找到小于x的t*2k，再保持t*2^k不變，將sum增大使得sum>2x，進(jìn)行新一輪偶變換，得到不小于x的t*2^k。

在偶變換時，如果偶數(shù)減半后還是偶數(shù)，則將這一部分加到第三個數(shù)上，這樣我們就將前面總和不變的循環(huán)改成了總和遞減的。由于無論怎么變換三個數(shù)都必為自然數(shù)，循環(huán)的總和不能無限遞減，那它的下界是多少呢？當(dāng)不能再分配給第三個數(shù)時，總和不變，因此偶變換一次，對象就交換，此后的所有偶數(shù)除以2后都為奇數(shù)，假設(shè)(a,b)中a為偶數(shù)，此時偶數(shù)a的變換如下：

a

a/2

a/4+sum

a/8+sum/2

a/16+sum/4+sum

a/32+sum/8+sum/2

a/64+sum/16+sum/4+sum

...

第n個偶數(shù)和第n-1偶數(shù)的遞推式為x_n+1=x_n/4+sum，x_0=a

可得通式x_n=(a-4sum/3)/4^n+4sum/3

當(dāng)a>4sum/3時，x_n單調(diào)遞增，當(dāng)a<4sum/3時，x_n單調(diào)遞減，數(shù)組的大小是有限的，不能單調(diào)遞增或遞減，因此a=4sum/3=2a/3+2b/3，可得a=2b，偶變換循環(huán)的過程中，a和b的最大奇公約數(shù)og始終不變，又因?yàn)閎是奇數(shù)，b和2b的最大奇公約數(shù)為b，所以，當(dāng)sum最小時，a=2b=2og。前面的三正變兩正保持了g|x，所以b|x。

當(dāng)x為奇數(shù)時，將{b,2b,3x-3b}轉(zhuǎn)化為{b,3x-2b,0}，再對兩正數(shù)偶變換即可得到t*2^k<=3x<=t*2^(k+1)，此時的t*2^k>=3x/2>x，可進(jìn)行二進(jìn)制分配。不過，我們不必操作至sum遞減至3b，如果過程中出現(xiàn)了t*2^k，若其不小于x自然不用說，若小于x，則將另兩個數(shù)合并再偶變換就能得到不小于x的。

當(dāng)x為偶數(shù)時，3x-3b為奇數(shù)，如果a>=x，則a二進(jìn)制分配即可得x，如果a 3x/2>b，讓a和3x-3b偶變換得到新的t*2^k，滿足t*2^k<=3x-b<=t*2^(k+1)，于是

t*2^k>=(3x-b)/2>=5x/4>x。同樣地，我們不一定要等sum減到3b，出現(xiàn)小于x的t*2^k時，t*2^k一定是循環(huán)中最大的，大于與它偶變換的奇數(shù)u，設(shè)第三個數(shù)為v，v是奇數(shù)，則由t*2^k x，讓t*2^k和v偶變換得到的新的最大的t*2^k滿足t*2^k>=(t*2^k+v)/2=(3x-u)/2>x。這樣一來，即使t*2^k

綜上，我們得到了一個通解：

一、有x或2x則結(jié)束。

二、數(shù)組中是否有q=t*2^k，其中t|x，且q>x，k>0（第一次找到q或者q>x，需要將另兩數(shù)合并），是則將q以外的另兩個數(shù)合并，跳至六

三、是否q

四、若三數(shù)都是正數(shù)，且不是兩奇一偶，則嘗試將其中一個數(shù)加給另外兩個數(shù)中的一個數(shù)，選擇其中g(shù)整除x的數(shù)組；若三數(shù)都是正數(shù)，且兩奇一偶，則將兩奇數(shù)相加，或?qū)⑴紨?shù)分成奇數(shù)給兩奇數(shù)，選擇其中g(shù)整除x的數(shù)組。

五、進(jìn)行步驟一二三，若偶變換的數(shù)不是偶數(shù)，則交換對象，一個偶數(shù)減半后，若參與偶變換的兩個數(shù)不都是奇數(shù)，則不斷進(jìn)行偶變換，否則分配給第三個數(shù)（如果已經(jīng)找到q則永遠(yuǎn)不再分配給第三個數(shù)），繼續(xù)五。

六、用二進(jìn)制數(shù)表示x/t，在左邊補(bǔ)充0直到位數(shù)等于k，從最高位到最低位，若為1則將q分配給0，為0則分配給另一個數(shù)。這樣就得到了x，結(jié)束。

至此，我們從理論上推導(dǎo)證明了通解的可行性，此外，我還寫了驗(yàn)證該解法的cpp代碼，對0<=x<=1000的所有有解數(shù)組都進(jìn)行了驗(yàn)證并且驗(yàn)證成功。

當(dāng)然，也許還存在其他通解，我很期待看到新想法。

我數(shù)學(xué)特強(qiáng) 類型:休閑 平臺:安卓 狀態(tài):運(yùn)營

安卓版下載 蘋果版暫無下載