《我数学特强》通解是存在的！
精华修改于前天 10:0319 浏览攻略
《我数学特强》有没有万能公式呢？很久之前，一开始玩的时候，就想过这个问题，但面对复杂的变换路径，我完全没有头绪。
最近的研究让我找到了通用的解法，这不是用程序暴力搜索答案，也不是简要的技巧，而是公式化的解法。另外，游戏里要求使用最少步数的最优解，而通解一般不限步数。
介绍一下游戏。有三个自然数，玩家每次操作可以对这三个数进行分配，我称为偶变换和奇变换，偶变换是把一个偶数减半并将减半的部分加到另一个数上，奇变换是把一个奇数加到另一个数上，然后将其变为0。实际上，奇变换不限奇数，因为将偶数奇变换给另一个数，可以先一直偶变换直到变为奇数，再进行奇变换。游戏的最终目标是得到三个相等的数，用三元数组表示为{x, x, x}，不过显然只要三个数里有x或2x就能得到{x, x, x}。
有通解的前提是有解，而有解的充要条件是，三个数的最大公约数g整除x（可表示为g|x），且三个数不是一零二奇。先证明必要性，og和og'分别为三个数变换前后的最大奇公约数，易证og|og'，如果og'=x，则og|x，也就是说如果得到了{x,x,x}，则有og|x，因此og|x是有解的必要条件。另外，由g=(a,b,c)（三个数a,b,c的最大公约数写法为(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}，两者等价，所以三数不是一零两奇也是有解的必要条件。至于充分性，如果我们找到了g|x且不是一零两奇情况下的解法，就相当于将其证明了。
通解讨论的数组默认已通过以上判别法筛选，以保证有解及证明充分性。但要注意，有解的数组在变换后不一定有解，通解的操作应当保证数组在变换后依然可解，时刻有g|x。
下面的是我早期想的通解，经过计算机验证，x为奇数时，x>17后出现反例：
一、有x或2x则结束。
三、若三数都是正数，且不是两奇一偶，则尝试将其中一个数加给另外两个数中的一个数，选择三种操作进行后g整除x的数组；若三数都是正数，且两奇一偶，则将两奇数相加，或将偶数分配给两奇数使其变为两偶数，选择两种操作进行后g整除x的数组。
四、若数组中没有g*2^k满足g*2^k>=x，k是自然数，则不断在两正数之间进行偶变换（如果x是偶数，则需要保证两数都是偶数），如果找到g*2^k，则跳到步骤六。
五、在步骤四的循环中选择含有数被4整除得奇数（且该数减半小于x）的数组（如果x是偶数则选择被2整除的），将该数偶变换给0，再重新在两数之间不断进行偶变换（如果x是偶数，则需要保证两数都是偶数），出现g*2^k则结束，将另两个数合并。
六、用二进制数表示x/g，在左边补充0直到位数等于k，从最高位到最低位，若为1则将g*2^k分配给0（或者是步骤五中得到g*2^k一半的数），为0则分配给另一个数。这样就得到了x，结束。
虽然有很多漏洞，但大框架是对的。在下文逐步分析后，我们将会推导出一个正确的通解。
直接得到通解可能是困难的，于是我想着要不然先解决什么样的组合是可解的问题吧。反复观察变换路径后，我猜测g整除x应该和有解相关，并且还发现了og在变换的过程中不变或变大，而且变换后的og整除变换前的og。
然后，我再想的是解决相对简单的数组。在三个数之间变换是复杂的，暂未发现规律，所以我研究了只有一个数为0的数组。如果三个正数的数组都能转变为一零两正，那么通解问题就可以归约到一零两正如何变换出x或2x的问题。
我们需要保证三正变两正后，g依然满足g|x。如何操作呢？对于{a,b,c}，奇变换后得到的{0,a+b,c}, {0,b,a+c}和{a,0,b+c}三个数组中，一定有一个数组的g满足g|x。
证明：3x的质因数分解为m*3^n，(m,n)=1。先假设三个数组的g都不整除x。(a+b,c)=(3x,c)，(a+c,b)=(3x,b)，(b+c,a)=(3x,a)如果都不整除x，则(3^n)|(a,b,c)，又因为(a,b,c)|x，可得(3^n)|x，但3x=m*3^n，(m,3)=1，矛盾。
两奇一偶时（该偶数不为0），以上的三种操作可能会让数组变为一零两奇，因此我们要对该类情况作调整，它有两种变换：一、两奇相加；二、偶数拆分为两奇数，分别加给另外两奇数。这两种变换会使三正变一零两偶，且至少有一种使得g|x，证明类似上一个，不再赘述。这样的话，我们就将前面提到的可解的数组都转化为一零两正了。
前面说过{0,0,3x}是无解的，两个正数不能奇变换，那当然就只好偶变换了。当x为奇数时，两个数一奇一偶，偶变换的对象（即哪个数给另一个数一半）是确定的，得到的下一数组是唯一的。再加上数组的和是不变的，这样的数组个数有限，所以，经过有限次偶变换后，一定会回到原来的数组，形成偶变换循环。当x为偶数时，偶变换的路径是不唯一的，且不一定能不断偶变换，变换后还可能是一零两奇，比如{2,10}。x为偶数的这种情况，后续在改进偶变换的时候再提及。
我们的目标是在循环中找到t*2^k，t*2^k>=x，t|x，k>0，因为在有三个数时，将t*2^k偶变换分解，可以得到小于t*2^k任意一个自然数。但循环中并不一定有t*2^k（比如{5,28}），所以在早期的想法中，我想打破原有循环，把偶数偶变换分给第三个数，使得原来循环的两个数进入新的循环，以找到t*2^k。
在{a,b}的偶变换循环中，如果我们只关注其中一个数a，可以发现该数在作如下变换：偶数时减半，奇数时加上sum再减半，sum=a+b。冰雹猜想里的变换会迭代至2^k，而这里，迭代至t*2^k，a和sum要满足的所有条件是什么，是个open的问题。修改了几次进入新循环的方法后，程序依然发现反例。所以，探寻如何修正a和sum进入新的含有t*2^k的循环，这条路暂时行不通。
不小于x的t*2^k一定和小于x的t*2^k在同一循环中，找到其中一个便能找到其余的t*2^k。但要得到新的循环，就要将参与偶变换循环的两数之和sum减小，而最大的t*2^k满足t*2^k<sum<t*2^(k+1)，得t*2^k>sum/2。
这样我们就有一个新的思路，先找到小于x的t*2k，再保持t*2^k不变，将sum增大使得sum>2x，进行新一轮偶变换，得到不小于x的t*2^k。
在偶变换时，如果偶数减半后还是偶数，则将这一部分加到第三个数上，这样我们就将前面总和不变的循环改成了总和递减的。由于无论怎么变换三个数都必为自然数，循环的总和不能无限递减，那它的下界是多少呢？当不能再分配给第三个数时，总和不变，因此偶变换一次，对象就交换，此后的所有偶数除以2后都为奇数，假设(a,b)中a为偶数，此时偶数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个偶数和第n-1偶数的递推式为x_n+1=x_n/4+sum，x_0=a
可得通式x_n=(a-4sum/3)/4^n+4sum/3
当a>4sum/3时，x_n单调递增，当a<4sum/3时，x_n单调递减，数组的大小是有限的，不能单调递增或递减，因此a=4sum/3=2a/3+2b/3，可得a=2b，偶变换循环的过程中，a和b的最大奇公约数og始终不变，又因为b是奇数，b和2b的最大奇公约数为b，所以，当sum最小时，a=2b=2og。前面的三正变两正保持了g|x，所以b|x。
当x为奇数时，将{b,2b,3x-3b}转化为{b,3x-2b,0}，再对两正数偶变换即可得到t*2^k<=3x<=t*2^(k+1)，此时的t*2^k>=3x/2>x，可进行二进制分配。不过，我们不必操作至sum递减至3b，如果过程中出现了t*2^k，若其不小于x自然不用说，若小于x，则将另两个数合并再偶变换就能得到不小于x的。
当x为偶数时，3x-3b为奇数，如果a>=x，则a二进制分配即可得x，如果a<x，则b<x/2，3x-3b>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，出现小于x的t*2^k时，t*2^k一定是循环中最大的，大于与它偶变换的奇数u，设第三个数为v，v是奇数，则由t*2^k<x，u<t*2^k<x，可得v=3x-u-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，我们也能通过上述操作得到不小于x的t*2^k。
综上，我们得到了一个通解：
一、有x或2x则结束。
二、数组中是否有q=t*2^k，其中t|x，且q>x，k>0（第一次找到q或者q>x，需要将另两数合并），是则将q以外的另两个数合并，跳至六
三、是否q<x（如果x是偶数，q以外有一个正偶数，则将该偶数分成两奇数加给另外两数，第三个是奇数且大于另一个奇数则q应与第三个数偶变换），是则将q以外的另两个数合并，跳至五
四、若三数都是正数，且不是两奇一偶，则尝试将其中一个数加给另外两个数中的一个数，选择其中g整除x的数组；若三数都是正数，且两奇一偶，则将两奇数相加，或将偶数分成奇数给两奇数，选择其中g整除x的数组。
五、进行步骤一二三，若偶变换的数不是偶数，则交换对象，一个偶数减半后，若参与偶变换的两个数不都是奇数，则不断进行偶变换，否则分配给第三个数（如果已经找到q则永远不再分配给第三个数），继续五。
六、用二进制数表示x/t，在左边补充0直到位数等于k，从最高位到最低位，若为1则将q分配给0，为0则分配给另一个数。这样就得到了x，结束。
至此，我们从理论上推导证明了通解的可行性，此外，我还写了验证该解法的cpp代码，对0<=x<=1000的所有有解数组都进行了验证并且验证成功。
当然，也许还存在其他通解，我很期待看到新想法。