猜两数问题

毒酒滴冻鸭

这也是本人以前在百度智力题贴吧发过的经典题目之一，性质跟本论坛的经典问题 毒酒问题(加强版) 有点相似，不过本题是相当于“分段性试毒”而不是“一次性试毒”。

以下是原题：

数学教授告诉我，在1至127这堆整数里任意选两个数，然后他每次给我一堆整数看看里面有没有包括我选的两个数中最少一个，我只需要答他是或否，这样13次下来他就能告诉我选的是哪两个数。这是如何做到的？

当时我是已经做出了“1至127”的解答方案，但是其复杂度超乎寻常，所以我想一步步从N=2开始，一直列举到N=126，把“1至N”的最优解法列举出来，最后才完成N=127的终极挑战。不过后来掉冷了太久也就让那个帖子沉没了。

这阵子刚巧有空，试试把那些结果搬运过来，并把N=127的解法重新整理一下（不能保证能否完成，看毅力是否足够）。

楼下开始分楼把结果搬过来，最后才挑战N=127。

毒酒滴冻鸭

教授告诉我，想一步登天是不可能的。。。所以先从小数量开始想，在1至N里任选两数，最少需要几次才能肯定猜出来呢？

N=2：在1至2里选两数，最少要问几次？因为答案肯定就是1和2，所以一次也甭问 (这不是废话么) 。。。结论：N=2→0次

N=3：在1至3里选两数，最少要问几次？因为这里有三种可能：[1,2]、[1,3]、[2,3]，而问一次是非题只能分辨2^1=2种结果，可知只问一次是不能肯定成功的。。。
那么问两次呢？第一次问：「<1>中吗？」第二次问：「<2>中吗？」如果两次都中，那么答案就是[1,2]。。。否则两次里必中一次，另一个选中的数字就是3。。。
结论：N=3→2次
这里咱们学到一个重要的技巧：当C(N,2)=N(N-1)/2大于2^k时，只问k次是不可能保证成功的。。。

N=4：这里有C(4,2)=6种不同可能情况，所以问两次是不能保证成功的 (2^2=4<6) 。。。但是2^3=8>6，所以问三次呢？
分别问<1>、<2>、<3>，如果里面中了两次就立刻得出答案，否则必定只中一次，而另一个选中的数就是4。。。结论：N=4→3次
这里咱又看出来另一个新技巧：从<1>开始，一直问到<N-1>，这样最多问N-1次就能肯定保证成功。。。

N=5：这里有C(5,2)=10种可能，而2^3<10<2^4，所以最少要问5-1=4次。。。
结论：N=5→4次

毒酒滴冻鸭

N=6：这里有C(6,2)=15种可能情况，而2^4=16>15。。。这样是否问4次就能肯定成功呢？来具体看看：

注意第一次只能从1至6里任意挑m个数 (0<m<5) 出来问，其他问法都毫无意义 (例如你挑<1~5>这5个数来问，答案肯定是「中」，而这样你完全得不到任何有用情报，等于白白浪费了一个问题) 。。。

如果第一次不中，那么选中的两数都在剩下来的6-m个数里，共C(6-m,2)种可能情况；如果第一次中，那么要么m个数里包含了全部两选中数，要么这两批分别有m、6-m的数字里各带一个选中数，所以总共有C(m,2)+m*(6-m)种可能情况。。。

(如果你有兴趣，可以自己验证一下「C(N-m,2)+C(m,2)+m*(N-m)=C(N,2)」这个恒等式是否永远成立。。。)

m=1：
中：C(1,2)+1*5=0+5=5
不中：C(5,2)=10

m=2：
中：C(2,2)+2*4=1+8=9
不中：C(4,2)=6

m=3：
中：C(3,2)+3*3=3+9=12
不中：C(3,2)=3

m=4：
中：C(4,2)+4*2=6+8=14
不中：C(2,2)=1

留意到了吗？无论哪个问法，都会有一个分支里剩下多于2^3=8的可能情况 (10、9、12、14) ，所以无论如何再问三次都不能保证成功。。。所以整体来说6个数问4次是不能保证成功的，最少得问6-1=5次。。。结论：N=6→5次

这次咱又领悟到一件重要的事：要在k次内保证成功，单单「C(N,2)<2^k」这个条件是不够的，还必须找到一个m，让C(m,2)+m*(N-m)、C(N-m,2)这两个数值都不多于2^(k-1)才行。。。

毒酒滴冻鸭

N=7：C(7,2)=21>2^4=16，所以4次肯定不够。。。那么5次又如何呢？

现炒现卖，就拿m=2测试一下：C(2,2)+2*5=1+10=11<16，C(5,2)=10<16，测试通过！所以问5次应该是能保证成功的。。。

第一次：<1,2>
如果不中，那么两选中数都在3~7五个数里，这样再问4次必定能够问出来。。。

如果第一次中，要么答案就是[1,2]，要么其中一数是1或2，另一数是3~7这五数其中之一。。。咱可以用这个代表式来表达：「[1,2]+(1,2)(3~7)」。。。

第二次：<1>
如果不中，那么2肯定是一个选中数，另一数是3~7这五数之一。。。还剩下3个问题，能否保证成功呢？当然可以，因为5<2^3=8，所以用「二分法」肯定能成功把另一数问出来。。。至于具体问法，各位看倌可以自行推敲。。。

如果第二次中，那么1肯定是一个选中数，另一数是2~7这六数之一。。。因为6<2^3=8，所以用「二分法」还是能保证成功的！

结论：N=7→5次

这个例子教晓了咱们什么呢？如果你能把其中一个选中数确定，而另一数收窄在一个不超过2^k个数的范围里，那么再问k次就能保证成功。。。

毒酒滴冻鸭

N=8：C(8,2)=28<2^5=32，那么问5次足够吗？

让咱们来测试一下不同的m值：

m=1：
不中：C(7,2)=21>16，再问4次不够！
m=2：
不中：两选中数都在剩下的6个里，从之前N=6的结论中得知再问4次不够！
m=3：
中：C(3,2)+3*5=3+15=18>16，再问4次不够！
m>3：
中：因为8-m<5，可知C(8-m,2)<C(5,2)=10，故C(m,2)+m*(8-m)=C(8,2)-C(8-m,2)>28-10=18>16，再问4次不够！

可知整体来说，问5次肯定不能保证成功！最少得问6次：

方案1：
第一次：<1~4>
第二次：<5~8>
如果两次只中一次，那么两选中数都在4个数的范围里，再问3次肯定成功；否则两次都中，则1~4、5~8各包含一个选中数 (用「(1~4)(5~8)」代表此情况) ，则再问两次确定1~4里哪个中，另两次确定5~8里哪个中，合共问6次肯定成功！

方案2：
前四次分别问：<1,2>、<3,4>、<5,6>、<7,8>
如果四次里只中一次，那么答案立刻就出来了，甭再问；否则中了两次，则其中两对数各包含一个选中数，再问两次肯定成功！

结论：N=8→6次

这个例子带给我们不少新启发：

一、考虑问k次能否成功，除了C(m,2)+m*(N-m)、C(N-m,2)两者必须都不超过2^(k-1)外，还要看N-m数里包含两数的情况下再问k-1次能否保证成功！

二、如果证实了C(m,2)+m*(N-m)大于2^(k-1)，那么更大的m值也会出现相同情况，甭再测试；同理如果证实了C(N-m,2)的情况下再问k-1次不够，那么更小的m值也是一样，甭再测试！

三、如果能把两选中数各自确定在两个分别有2^p、2^q数且互不重复的范围里，则再问p+q次肯定能保证成功！ (这招对以后更大规模的情况非常有用！)

毒酒滴冻鸭

N=9：C(9,2)=36>2^5=32，所以5次肯定不够。。。那么6次又如何呢？

测试一下m=2：C(2,2)+2*7=1+14=15<32，C(7,2)的情况再问5次也足够，所以6次应该能保证成功！

第一次：<1,2>
如果不中，那么两选中数都在3~9七个数里，再问5次必定能够问出来。。。
如果第一次中，要么答案就是[1,2]，要么其中一数是1或2，另一数是3~9这七数其中之一。。。咱可以用这个代表式来表达：「[1,2]+(1,2)(3~9)」。。。

第二次：<1>
如果不中，那么2肯定是一个选中数，另一数是3~9这七数之一。。。还剩下3个问题，因为7<2^3=8，所以用「二分法」再问3次肯定能成功把另一数问出来。。。
如果第二次中，那么1肯定是一个选中数，另一数是2~9这八数之一。。。因为2^3=8，所以再问3次还是能保证成功的！

注意这个演化咱们可以这样表达：
[1,2]+(1,2)(3~9) = [1](2~9)+[2](3~9)

结论：N=9→6次

毒酒滴冻鸭

N=10：C(10,2)=45<2^6=64，问6次应该足够：

第一次：<1~4>
如不中，则5~10六数里包含两数，再问5次肯定成功；如中，则合共C(4,2)+4*6=6+24=30种情况，少于2^5=32，再问5次也应该能保证成功：

第二次：<5~8>
如中，则1~4、5~8各含一数，再问2+2=4次肯定成功；如不中：

第三次：<9,10>
如中，则1~4、9~10各含一数，再问1+2=3次肯定成功；如不中，则1~4包含两数，再问3次也肯定成功！

结论：N=10→6次

这个例子里出现了一个很强而有力的方案，概念如下：

假设：
「{a_1~a_m}」代表a_1~a_m这个范围里包含两选中数
「(b_1~b_p)(c_1~c_q)」代表b_1~b_p、c_1~c_q这两个互不重复的范围里各含一选中数

则：
{1~10}
=(1~4)(5~10)+{1~4}+{5~10}
=(1~4)(5~8)+(1~4)(9,10)+{1~4}+{5~10}
情况数量
=4*4+4*2+C(4,2)+C(6,2)
=16+8+6+15
=45=C(10,2)

关键就是要弄出(1~4)(5~10)+{1~4}这个部分，其中牵涉到两个范围，一个有4数，一个有2^k-2数，这样再问k+2次就能肯定成功！

毒酒滴冻鸭

N=11：C(11,2)=55<2^6=64，那么问6次足够吗？

让咱们来测试一下不同的m值：

m=2：
不中：C(9,2)=45>32，再问5次不够！
m<2：
不中：因11-m>9，C(11-m,2)>C(9,2)=45>32，再问5次不够！

m=3：
不中：两选中数都在剩下的8个里，从之前N=8的结论中得知再问5次不够！

m=4：
中：C(4,2)+4*7=6+28=34>32，再问5次不够！
m>4：
中：因11-m<7，C(11-m,2)<C(7,2)=21，故C(m,2)+m*(11-m)=C(11,2)-C(11-m,2)>55-21=34>32，再问5次不够！

可知整体来说，问6次肯定不能保证成功！最少得问7次：

第一次：<1~4>
第二次：<5~8>
第三次：<9~11>
如果三次只中一次，那么两选中数都在4或3个数的范围里，再问3次肯定成功；否则三次中两次，例如1~4、5~8各包含一个选中数 (用「(1~4)(5~8)」代表此情况) ，则再问两次确定1~4里哪个中，另两次确定5~8里哪个中，合共问7次肯定成功！

结论：N=11→7次

毒酒滴冻鸭

N=12：C(12,2)=66>2^6=64，6次肯定不够，最少得问7次：

第一次：<1~4>
第二次：<5~8>
第三次：<9~12>
如果三次只中一次，那么两选中数都在4个数的范围里，再问3次肯定成功；否则三次中两次，例如1~4、5~8各包含一个选中数 (用「(1~4)(5~8)」代表此情况) ，则再问两次确定1~4里哪个中，另两次确定5~8里哪个中，合共问7次肯定成功！

结论：N=12→7次



N=13：C(13,2)=78>2^6=64，6次肯定不够，最少得问7次：

第一次：<1~4>
第二次：<5~8>
第三次：<9~12>
如果三次中两次，例如1~4、5~8各包含一个选中数 (用「(1~4)(5~8)」代表此情况) ，则再问两次确定1~4里哪个中，另两次确定5~8里哪个中，合共问7次肯定成功；如果三次只中一次，例如是1~4：

第四次：<13>
如中，则13为一选中数，另一选中数在1~4里，再问2次肯定成功；如第四次不中，则1~4含两选中数，再问3次肯定成功！

结论：N=13→7次



N=14：C(14,2)=91>2^6=64，6次肯定不够，最少得问7次：

第一次：<1~4>
第二次：<5~8>
第三次：<9~12>
如果三次中两次，例如1~4、5~8各包含一个选中数 (用「(1~4)(5~8)」代表此情况) ，则再问两次确定1~4里哪个中，另两次确定5~8里哪个中，合共问7次肯定成功；如果三次只中一次，例如是1~4：

第四次：<13,14>
如中，则两选中数分别在1~4、13~14里，再问2+1=3次肯定成功；如第四次不中，则1~4含两选中数，再问3次肯定成功！

结论：N=14→7次



看我示范了这么多个例子，是时候来个小挑战了：N=15，最少需要问多少次？如何问？

毒酒滴冻鸭

N=15：C(15,2)=105>2^6=64，6次肯定不够，最少得问7次：

第一次：<1~5>
第二次：<5~9>
如果两次都不中，则10~15六数含两数，再问5次肯定成功！

如果只中一次，例如只中第一次，要么1~4、10~15各含一数，要么1~4含两数 (「(1~4)(10~15)+{1~4}」) ，从N=10的例子可知再问5次肯定成功！

如果两次都中：
第三次：<5>
如中，则一数是5，另一数在其余14个数里，再问4次肯定成功；如不中，则1~4、6~9各含一数，再问2+2=4次肯定成功！

结论：N=15→7次