CodeGize

失眠，原因很多

昨夜失眠，竟然是因为想到一个数学题

一开始是这样的，双方投掷2个骰子，一般的规则就是每个人用加法把自己的2个骰子点数加起来，然后比大小

但是有时候会出现双方相同的情况，比如1+6和2+5

所以就在想，如果排除掉点数完全一样的情况下，有没有一种数学算法，可以一次计算比出大小

扩展和归纳起来就是：

对于一个整数对a,b（ab不分先后，即1/6和6/1视为同一个整数对），设计一种算法，使得对于不同的整数对，计算出来的结果为整数且唯一？

想不到好的办法，一开始先试试乘法即f(a,b)=a*b

显然，这个算法很快就被排除了，原因很简单，比如2*3=1*6或者2*2 = 1*4

既然乘法不行，是不是可以和加法结合起来呢，比如f(a,b)=a*b+a+b

睡不着，想了2个小时，发现一个反例，2*3+2+3 = 11 = 1*5+1+5

好吧，自己解决不了，就去请求万能的朋友圈

恍恍惚惚，半睡半醒之间，感觉找到了突破口，就是查二维表

做游戏我们常常会有查表的操作，细细一想，不就是查个二维表么，只要构建一个可以利用一个一元公式构建的二维表就行

比如最简单有序的6*6的表

那么对于每一行a和每一行b就可以得到唯一的解(a-1)*6+b=a*6+b-6，-6不影响所以也可以去掉

这么一推广就可以得到这样的公式

f(a,b)=a*N+b

但是很显然有个问题，比如对于f(a,b)=a*6+b来说

随便取个ab，比如3和4，结果为3*6+4 = 22，那么我也可以a取个2，然后找到b使得结果也为22，即2*6+10=22

难道这样是思路是错误的么？

再看2*6+10这个例子，可以看到原因在于表里面根本就没有第10列，所以数据是超出了查表的范围的

那怎么办？既然超出列数，我们增加列数就可以。让列处于我们可查询的范围内。那么

N的最小值可以等于b。

那么公式就简化为f(a,b)=a*b+b= (a+1)*b

从公式上看就很神奇，之前f(a,b)=a*b不行，但是a加了一个1就可以

那么怎么从数学上证明这个公式是可行的呢？

来个反证法，

如果存在2对不同的整数对(a1,b1)和(a2,b2)，使得(a1+1)*b1 = (a2+1)*b2，那么我们的公式就是错误的，否则肯定是正确的。

好吧，下面不会了，等想到数学证明方法再继续

最终解决办法见《配对函数Cantor pairing》