【面试题】解答Microsoft的一道逻辑推理题

阅读本文需要5分钟

以下是微软有名的一道逻辑推理题，网上有不少人给出了答案，但是推理过程都有些问题，在这里我给出我的推理过程：

教授选出两个从2到9的数，把它们的和告诉学生甲，把它们的积告诉学生乙，让他们轮流猜这两个数

　　甲说：“我猜不出”

　　乙说：“我猜不出”

　　甲说：“我猜到了”

　　乙说：“我也猜到了”

　　问这两个数是多少

[我的解答]

设甲听到的和为M, 乙听到的积为N，则：

M == A11 + B11 == A12 + B12 == …… == A1n + B1n( n >= 2)

N == A21 * B21 == A22 * B22 == …… == A2k * B2k (k >= 2)

且：

存在{i, j}满足：

（i）(A1i == A2j && B1i == B2j (j>=2 && j<=k))

（ii）(A1i, B1i中至少有一个是合数 && 另一个数乘以前面那个合数的最小因子（>1）得到的积不超过9)

-> 否则乙不会说不知道（如果不同因数分解的个数为1，则乙知道答案；而为1的可能就是：

1）因数分解为两个质数的组合；

2）因数分解为一个合数乘以另一个数，该数乘以前面那个合数的最小因子(>1)得到的积会超过9）

（iii）(对于任意的t, t<=n && t>= 2 && t!=i：A1t和B1t均为质数 || 一个为合数，而对于另一个数，如果乘以前面那个合数的最小因子(>1)，会超过9)

-> 否则甲不会在乙说不知道的情况下又知道了（其实就是对上面一步的结论求逆命题）

（iiii）(对于任意的x, x<=k && x>=2 && x!=j: A2x, B2x中有一个数乘以另一个数的最小因子(>1)超过9 || A2x与B2x的和只能转化成一个合数与另一个数相加的形式，其中“另一个数”乘以这个合数的最小因子(>1)得到的积不超过9)

-> 否则乙不会在甲说知道的情况下又知道了(这句话也是最难映射成数学表达的一句话：乙能在这一步得出答案，说明{A2j, B2j}(即{A1i, B1i})有{A2x, B2x}所没有的特征。而到目前为止，我们所掌握的{A2j, B2j}的特征只有：

1）A2j, B2j中至少有一个是合数

-> A2x, B2x均为质数（这不可能）

2）A2j, B2j中任何一个数乘以另一个数的最小因子(>1)不超过9

-> A2x, B2x中有一个数乘以另一个数的最小因子(>=1)超过9

3）A2j与B2j的和可以转化成两个质数相加的形式或者可以转化成一个为合数与另一个数相加的形式：其中“另一个数”乘以这个合数的最小因子(>1)得到的积超过9

-> A2x与B2x的和只能转化成一个合数与另一个数相加的形式，其中“另一个数”乘以这个合数的最小因子(>1)得到的积不超过9

为了求出符合题意的A1i和B1i, 我们要使用逼近法来缩小范围。

从甲的角度看：

2-9这8个数字中只有4，6，8，9这4个合数，它们与2-9中的数相加，满足条件(ii)的只有和：{6， 7， 8， 9， 10， 11， 12}

再从乙的角度来考察，检验每个和：

如果M == 6: 此时{A1i, B1i}({A2j, B2j}) == {2, 4}({3， 3}不满足条件(ii))。此时N = 2 * 4 = 8。但是8只能分解成{2， 4}（注意取值只能在2-9之间），这与k >= 2矛盾。

如果M == 8: 存在{2, 6}, {4, 4}，{3， 5}，不满足条件(iii)。

如果M == 9: 此时{A1i, B1i}({A2j, B2j}) == {3, 6}}({2， 7}不满足条件(ii))。

此时N = 3 * 6 = 18 = 2 * 9。2 + 9 = 11 = 4 + 7 = 3 + 8。 9的最小因子(>1)为3， 2 * 3 < 9 -> 不满足条件(iiii)的第一个“或”部分；

4的最小因子(>1)为2，7 * 2 > 9 -> 不满足条件(iiii)的第二个“或”部分（与“只能”矛盾）。故：不满足条件条件(iiii)。

如果M == 10: 存在{2, 8}，{4， 6}，{5， 5}不满足条件(iii))。

如果M == 11: 存在{2, 9}, {3, 8}, {4， 7}, {5, 6}，不满足条件(iii))。

如果M == 12: 存在{3, 9}({6， 6}, {4, 8}，{5， 7}，不满足条件(iii))。

最后得出：M只能是7，对应的{A1i, B1i} == {3, 4}

[注] 这个推理可以改进的地方在于：“对于任意的x, x<=k && x>=2 && x!=j: A2x, B2x中有一个数乘以另一个数的最小因子(>1)超过9 || A2x与B2x的和只能转化成一个合数与另一个数相加的形式，其中“另一个数”乘以这个合数的最小因子(>1)得到的积不超过9”这句话的映射。应该有更好的同构的数学表达。

END