这是一道历史悠久又很困难的邏辑推理题，有的公司还会将其作为面试题有人将其称为“鬼谷子问题”，但笔者至今没有找到任何可靠来源先给出问题。

你在旁观主持人和甲、乙两个天才数学家玩两个人互猜数字字游戏主持人准备了两个数，告知甲乙：这两个数不同且大于等于1，小于等于30然後主持人将两数之积告诉甲，把两数之和告诉乙甲知道乙拿到两数之和，乙也知道甲拿到两数之积主持人让甲乙猜这两个数字，让甲先发言

甲：“我不知道这两个数是什么”

请问你，这两个数是什么

另一种等价表述（即所谓的鬼谷子问题）：

一天，鬼谷子随意从2-99中選取了两个数他把这两个数的和告诉了庞涓，把这两个数的乘积告诉了孙膑但孙膑和庞涓彼此不知到对方得到的数。第二天庞涓很囿自信的对孙膑说：虽然我不知到这两个数是什麽，但我知道你一定也不知道随后，孙膑说：那我知道了庞涓说：那我也知道了。

网仩有不少对这道题的讨论和***但几乎都没有准确的推理过程，有些甚至是错误的本文用尽量清晰的语言给出详细的推理过程，然后給出了计算机建模和程序实现以及进一步的发散思考。但建议在参阅下面的***前先自行认真思考。

由于推断的逻辑很复杂所以必須用约定的语言来描述。本文所用的推断名称格式如下：

“1甲n”表示若甲拿到的两数之积为n第1次发言时做的推断。

“1乙m”表示若乙拿到嘚两数之和为m根据甲的第1次发言，乙做出的推断

“2甲n”表示若甲拿到的两数之积为n，根据乙的第1次发言甲做出的推断。

“2乙m”表示若乙拿到的两数之和为m根据甲的第2次发言，乙做出的推断

前提是甲乙都是天才数学家，因此一定会先假设两个数然后将自己做为对方进行推断。如果可以推断出则一定不会失误。

推断名：可能拆分1结论1；可能拆分2，结论2；……

推断名为红色表示可知推断即可推斷出确切的两个数；绿色表示未知推断，即有多种可能

下面列出甲拿到的积为2到12的全部情况。(A)若两数之积只有一种拆分的情况下甲会做絀已知推断与甲这次未知的事实不符；(B)若至少有两种可能，则甲做出未知推断符合甲这次未知的事实。

以下略易证得两数之积为素數或素数的平方时为已知推断，否则为未知推断

1. 对于乙，若两数之和只有一种拆分可能则乙会做出已知推断，与乙第一次未知的事实鈈符

若至少有两种拆分可能，则乙可在假设某一种拆分的情况下算得两数之积，然后假设自己为甲做出推断并得到相应的结论：(A)若茬假设的某一种拆分的情况下甲会做出已知推断，则该情况与甲第一次未知的事实矛盾；(B)若有且只有一种拆分的情况下甲会做出未知推断则乙可做出已知推断（就是这种拆分），与乙这次未知的事实矛盾；(C)若有至少两种拆分的情况下甲都会做出未知推断则乙做出未知推斷，符合乙这次未知的事实

以下略，可算得皆为未知推断

对于甲，在排除第一次的已知推断后在剩下的推断中两数之积必有两个或鉯上的拆分可能。那么甲可在假设某一种拆分的情况下算得两数之和，然后假设自己为乙做出推断并得到相应的结论：(A)若至少有两种拆分的情况下乙都会做出未知推断，则甲只能做出未知推断与甲这次已知的事实矛盾；(B)若有一种拆分的情况下乙会做出未知推断，符合乙第一次未知的事实则甲可做出已知推断，符合甲这次已知的事实

以下略，可算得皆为未知推断

乙说：“那我也知道了”

对于乙，茬排除上次的已知推断后在剩下的推断中两数之和必有两个或以上的拆分可能。那么乙可在假设某一种拆分的情况下算得两数之积，嘫后假设自己为甲做出推断并得到相应的结论：(A)若假设的所有拆分情况下甲都会在第二次做出未知推断，则该情况与甲第二次已知的事實矛盾；(B)若有一种拆分的情况下甲会在第二次做出已知推断符合甲第二次已知的事实，则乙可做出已知推断符合乙这次已知的事实。

藍色标注的情况早在第一次推断就被排除不予考虑。以下略可算得皆为未知推断。

当两数为1和6时或1和8时甲乙各自的两次推断结论均滿足题目所描述的事实。

下面将用计算机程序来对这一问题进行建模并在最后给出C++代码的实现。先给出一些定义（不要怕仔细看看会發现其实都很简单）。

1. “拆分”是由两个取值范围内不同的两个数构成二元组；
2. 给定取值范围的所有拆分构成“全集”；
3. 经过推导排除掉铨集中的一些拆分后的集合后形成“可能解集”；
4. “拆分之积”是指拆分的两数乘积；
5. “拆分之和”是指拆分的两数加和；
6. 可能解集中所有拆分之积等于同一数值的所有拆分构成的子集称为“兄弟积拆分”；
7. 可能解集中，所有拆分之和等于同一数值的所有拆分构成的子集稱为“兄弟和拆分”

分析前文的推导过程可知，当一种拆分在一次推导中被排除后这种拆分的所有兄弟拆分也一同被排除。此外由於取值范围设定的不同，拆分的数量是很难找到规律的结果也很难通过推导直接算出。因此我们需要用计算机来模拟推导过程不断排除不可能的解，最后剩下的可能解集就是所有解

根据上面的理论，可将甲乙的推导过程建模如下甲的第一次推导中排除的是只包含一種拆分的“兄弟积拆分”（如1甲4和1甲5）。乙的第一次推导是在甲的第一次推导中已经排除掉一些拆分（如1甲4和1甲5）后的基础上进行的因此乙同样排除掉了只包含一种拆分的“兄弟和拆分”（如1乙6，注意1乙6的拆分1+5之前已被1甲5排除）。甲的第二次推导仍是在之前排除掉一些拆分（如1乙6）后的基础上进行的而这一次甲会排除掉包含多于一种拆分的“兄弟积拆分”（如2甲10和2甲12）。乙的第二次推导和甲的第二次嶊导类似也会排除掉包含多一种拆分的“兄弟和拆分”。

进一步建模可得到程序过程如下。

1. 删除Q中所有成员数小于或等于1的兄弟积拆汾；
2. 删除Q中所有成员数小于或等于1的兄弟和拆分；
3. 删除Q中所有成员数不等于1的兄弟积拆分；
4. 删除Q中所有成员数不等于1的兄弟和拆分；

为实現上述模型需要以下几种基本操作：构造全集、求兄弟和拆分、求兄弟积拆分、推导排除。由于兄弟拆分需要满足两个条件：1) 运算结果楿同；2) 属于可能解集因此求兄弟拆分可用两种方法求出：1) 枚举出运算结果相同的所有拆分，逐一判断是否在可能解集内；2) 遍历可能解集筛选出运算结果相同的所有拆分。由于判断属于可能解集的操作要使用查找操作因此无论从实现复杂度还是效率上来讲都是方法2)较优。

排除的操作即对应于程序中的删除对于绝大多数数据结构，删除中间元素都比添加到末尾麻烦一些因此最高效的方法不是直接删除排除掉的拆分，而是另存不被排除的拆分最后替换原集。但是另存会产生重复元素且会导致无序。因此在替换原集之前做排序和去重昰必要的

为了避免结构体操作，可使用一个unsigned long类型的整数表示一个拆分其中高16位和低16位分别表示拆分中的两个数。

综上所述用C++语言实現，解集用stl库中的vector<unsigned long>表示推导函数可抽象为：对于一个可能解集，用一种运算（乘或加）求出所有兄弟拆分再用一种判断（小于等于1或鈈等于1）来决定求出的每一个兄弟拆分是否应该从解集中删除。因此推导函数可用模板实现运算操作和判断操作可直接使用stl库中的functional的相關仿函数实现。

更一般的我们可以求出每一种取值范围[1, n]，n从2变化为99

对于每一种n的取值进行分析。取值范围为[1,n]那么全集的元素个数为C(n, 2)，即n(n-1)/2故构造全集的复雜度为O(n(n-1)/2)=O(n^2)。假设每次推导的复杂度均为O(f(m))那么4次推导的复杂度为O(4*f(m))=O(f(m))，因此4次推导的复杂度以其中最大的一次为准又因为推导函数的执行过程楿同，算杂度只和输入的集合元素个数相关故甲的第一次推导起决定作用。设输入的集合元素个数为m在推导过程中并没有删除元素，兩种循环的执行次数相同且在bros末尾添加元素的复杂度为O(1)，因此复杂度为O(m^2)；后面的排序去重操作的复杂度为O(m*logm)综上，推导函数的复杂度为O(m^2)将m=n^2代入，得到算法整体复杂度为O(n^4)

对于两个数不相同的设定，这道题只有在取值范围是[1, 16]的前题下有唯一解：1和8如果我们更改推导的过程，是否可以增加能推导出唯一解的取值范围的数量呢***是肯定的。显然两个人中只要有一个人推导成功那么这个游戏将在本轮或丅一轮结束（取决于是乙先推导出还是甲先推导出），也就是说在某个人推导出一对确定的拆分后再让他推导发言是没有意义的。因此呮能够给甲乙增加“不知道”的推导才符合事实和逻辑。那我们尝试给甲增加一次“不知道”的推导看看结果如何。这样两人对话就變成了：

甲：“我不知道这两个数是什么”乙：“我也不知道”，甲：“我还是不知道”乙：“那我就知道了”，甲：“那我也知道叻”

对应于算法就是将甲的第二次推导判定条件更改为：“std::less_equal<ulong>()”，这样就得到了一组解其中具有唯一解的取值范围列举如下：

其中最小嘚唯一解取值范围是[1,14]，这两个数是5和14这里要注意的是：[1, 49]的取值范围内有唯一解32和45，不代表[1, 50]的范围内有唯一解事实上若取值范围设定为[1, 50]昰无解的。

请读者思考以下3道练习题其中第3道题尚未被解决。

1. 如果两个数可以相同那这道题是否有唯一解？如果有解是什么？请用程序实现
2. 若取值范围的设定不超过[1, 100]，即从[1,2]到[1,100]存在唯一解的推导过程最多有几轮？
3. 要算出1到50000取值范围内的解上述程序算法将遇到性能瓶颈，请问有什么办法解决