现在的位置: 首页 > 综合 > 正文

SP之问——经典

2018年02月20日 ⁄ 综合 ⁄ 共 1364字 ⁄ 字号 评论关闭

设有两个自然数X,Y,2<=X<=Y<=99,S先生知道这两个数的和S,P先生知道这两个数的积P,他们二人进行了如下对话:

S:我确信你不知道这两个数是多少,但我也不知道。

P:一听你这句话,我就知道这两个数是什么了。

S:我也是,现在我也知道了。

现在你能通过他们的话推断出这两个数是多少吗?(当然,S先生和P先生都是非常聪明的。)

第一句话的分析

S先生第一句话,“我确信你不知道这两个数是多少,但我也不知道。”那么,在什么条件下S先生能够确认P先生不知道这两个数呢?

首先考虑在什么情况下P先生能够通过两个数的积推出这两个数。假如P先生知道的数字P=21,那么21可以唯一写成21=3x7,因为2<=X<=Y<=99。

这提示我们假如P先生的数字P可以唯一分解,那么P先生肯定可以推出这两个数。

同理,如果S先生的数字S也可以唯一分解的话,那么他也可以推出这两个数字。

这样,我们就有了如何分析的工具了。称P先生的上述分解叫做P分析,S先生的叫做S分析。

符合S先生第一句话的数字应该满足如下条件:若S=X1+Y1=X2+Y2=…=Xn+Yn,其中Xi与Yi满足2<=Xi<=Yi<=99,i=1…n,表示S的n个互异的分解。设P1=X1xY1,P2=X2xY2,…,Pn=XnxYn,表示n个因子的乘积。对Pi进行P分析,如果Pi可以唯一分解,那么S先生只能说他不确定,而不是确定。所以S先生的话等于Pi都不能唯一分解。

假设S先生知道的数字是11,分析过程如下:

 

可以看到Pi都不能唯一分解,因此11符合S先生第一句话对应的集合SArr。

假如S先生知道的数字是10,分析过程如下:

 

可以看到P2=21是唯一分解的,所以10不属于集合SArr。

通过枚举4到198之间的数字进行上述分析可以得到集合SArr的全部元素。

SArr={11,17,23,27,29,35,37,…}

第二句话的分析

P先生知道S先生的第一句话后也同样可以推出集合SArr,P先生是在什么条件下说出第二句话的呢?

P先生将自己的数字P进行分解,P=X1xY1=...=XmxYm,其中Xi与Yi满足2<=Xi<=Yi<=99,i=1…m,表示P的m个互异的因式分解。设S1=X1+Y1,…,Sm=Xm+Ym。如果Si中有且仅有一个在SArr中出现,这P先生可以唯一确定X和Y。

假如P先生知道的数字P=18,分析过程如下:

 

S1=11是在集合SArr中的,而S2=9是不在的,所以18是符合上面分析的数字,在集合PArr中,而X和Y分别是2和9。

假如P知道的数字是P=30,分析过程如下:

 

可以发现S1=11和S2=17都在SArr中,所以这个数字不在集合PArr中。

通过枚举4到9801之间的数字,进行上面的分析,就可以知道符合条件的数字,其构成的集合为PArr。

PArr={18,24,28,42,52,…}

第三句话的分析

S先生在听了P先生的话后,他也知道了集合PArr,那么他只要对SArr中的数字进行分解,然后将因子乘积与PArr中的做类似P先生做的检验,将唯一对应的因子输出就是符合条件的X,Y。

到此为止,S先生和P先生都知道这两个数X和Y。

实验结果

利用C进行编程得到最终结果为X=4和Y=13,S=17和P=52。在2<=X<=Y<=99范围内,居然只有唯一一组解!

抱歉!评论已关闭.