Think

鬼谷子的数学难题

题目概述

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

解题报告

看了题目，思索一下，这是一个猜数字的游戏。那么该和从入手呢。假设这两个数字是a,b.那么令M=a+b;N=a•b;所以庞涓拿到了M，孙膑拿到了N.如此我们对他们的对话稍加研究。

  1. 首先庞涓说：虽然我不知到这两个数是什么，但我知道你一 也不知道。
    • 立即得到推论1:a和b不能同时为素。解释：同时为素说明N只能拆成两个素数的因子，素数本身不包含其他大于等于2的因子，所以有N必知这两个素数是什么。推论1得到。也就是说，庞涓手中的数字能够判断这两个数并不都是素数。
    • 对于推论1稍加思索，可得推论2：a和b若为一素一合，那么素数最大不得超过47。解释：比47再大的素数就是53，若另一个数有大于1的因子可拆出，最小是2，2•53>99。所以推论2得到。
    • 通过推轮1和推论2我们得知在5到197中可行的M有：11 17 23 27 29 35 37 41 47 51 194 197(通过程序计算得出)
  2. 稍加观察，立即排除197,因为M=197,a,b只可能是98,99，这样的话庞涓和孙膑就都知道结果了。另外我们发现11到51基本连续，但是到达194产生了跳跃，所以对于194拆分。194=98+96，194=96+95；结合以上推论，立即排除194。
  3. 这时只剩下：11 17 23 27 29 35 37 41 47 51
    • 于是我们考虑他们的第二句对话：孙膑：那我知道了。而对于仅剩的数字我们再做分析：
    • 11=2+9=3+8=4+7=5+6;
    • 17=2+15=3+14=4+13=5+12=6+11=7+10=8+9；
    • 23=2+21=3+20=4+19=5+18=6+17=7+16=8+15=9+14=10+13=11+12；
    • 先观察这3组，我们看到5•6=2•15=30;5•12=3•20=60;如此，那么这样的话如果孙膑拿到了30，11，17均有可能，60的话17，23均有可能，所以要删掉相同的积，得到推论3：不得有相同的积存在。这时有下面这样有趣的结果：
      • 11: 2+9 3+8 4+7
      • 17: 4+13
      • 23: 4+19 7+16 10+13
      • 27: 2+25 4+23 5+22 7+20 8+19 9+18 10+17 11+16
      • 29: 2+27 4+25 6+23 7+22 8+21 10+19 11+18 12+17 13+16
      • 35: 3+32 4+31 5+30 6+29 7+28 8+27 9+26 10+25 12+23 14+21 16+19
      • 37: 5+32 6+31 8+29 9+28 14+23 16+21 17+20
      • 41: 3+38 4+37 7+34 9+32 10+31 12+29 13+28 15+26 16+25 17+24 18+23 19+22
      • 47: 4+43 6+41 7+40 10+37 11+36 13+34 14+33 15+32 16+31 17+30 18+29 19+28 21+26 22+25
      • 51: 2+49 3+48 4+47 5+46 7+44 8+43 10+41 11+40 12+39 13+38 14+37 16+35 17+34 18+33 19+32 20+31 21+30 22+29 23+28 24+27
  4. 好了，敏锐的你应该发现了什么。根据庞涓和孙膑的最后一句对话，庞涓：那我也知道了。

庞涓知道什么了？如果庞涓拿到的是除了17以外的数字，例如11，那他有3个可能。孙膑对于18，24，28这三个任意的N，都能推出11是可行的和，也即都能知道是哪两个数字。要是这样庞涓做不出决定到底是哪个。问题是庞涓做出了决定，所以M一定17。而且此刻要Hack一下，因为我们已经找到了结果，所以不用考虑两个数字都是合数的情况了。XD

  • M = 17; N = 52;
  • a + b = 17; a • b =52
  • a = 4; b = 13; (反之亦然)

本题目计算量稍大，我借助了程序辅助做排除工作，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<fstream>
#include<cmath>
using namespace std;
bool    nn[198];
int     okay[198],tot=0;
short   del[9703];
bool isprime(int num){
    for(int i=2;i<=sqrt(num);i++)
        if(num%i==0) return 0;
    return 1;
}
int main(){
    freopen("output.txt","w",stdout);
    int num[29]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,51,53,57,59,61,67,71,73,79,83,87,89,91,97};
    for(int i=0;i<29;i++)
        for(int j=i+1;j<29;j++)
            if(num[i]+num[j]<198)
                nn[num[j]+num[i]]=1;
    for(int i=7;i<198;i++)
        if(!nn[i]){
            for(int j=16;j<29;j++)
            	//两个数字要满足在界内，同时另一个数字是合数，然后剔掉这些数字。
                if((i-num[j]<=99) && (!isprime(i-num[j])) && (i-num[j]>3)){
                    nn[i]=1;
                    break;
                }
        }
    for(int i=7;i<198;i++){
        if(!nn[i]){
            cout<<i<<' ';
            okay[++tot]=i;
        }
    }
    //step2
    cout<<endl<<endl;
    tot-=2;//手动删除194,197;
    for(int i=1;i<=tot;i++)
        for(int j=2;j<=okay[i]/2;j++)
            if(del[j*(okay[i]-j)]==0)
                del[j*(okay[i]-j)]=1;
            else if(del[j*(okay[i]-j)]==1)
                del[j*(okay[i]-j)]=-1;
    for(int i=1;i<=tot;i++){
        cout<<okay[i]<<':';
        for(int j=2;j<okay[i]/2;j++)
            if(del[j*(okay[i]-j)]==1){
                cout<<' '<<j<<'+'<<okay[i]-j;
            }
        cout<<endl;
    }
    return 0;
}