推理题

35868 · 发表于 2015-4-30 20:50:19

1.你有27个钱币，每个重量10克，除了一个重9克或者11克（重或轻1克）。用天平称量几次才可以辨认出那个不同重量的钱币？
2.有一个老实人（总是说真话），一个说谎者（总是撒谎），和一个有时说真话，有时说假话的人。你可以问三条答案是“是”还是“不是”的问题来分辨谁是谁。每一次你只能问一个人一条问题（你自己选）。你可以问同样一个问题多过一次，但是这是算在你问话的总和上的。
你会问什么和问谁？

22568 · 发表于 2015-5-1 00:39:29

本帖最后由天马行空于 2015-5-1 23:50 编辑
1.
首先,对于任何一次有意义的称量,两边的钱币数必然一样多.(否则,由于目标钱币重量的偏差小于一枚钱币的重量,必然是多的一边重.)
其次,任何时刻,我们可以将所有钱币分成四组:

(黑)已确认必为标准重量.
(红)有可能重了,不可能轻了.
(蓝)有可能轻了,不可能重了.
(无)对其一无所知.

(为方便表述,用上述四种颜色来表示.)
于是,一开始我们拥有27枚无色的钱币.每次称量,我们有可能给某些钱币染上新的颜色;具体地,无色的有可能被染成另外三种颜色,红蓝都有可能被染成黑色,剩下的不被允许.我们的目标是将26枚钱币染成黑色.
接下来我们注意到:
对一个局面的处理仅与四种颜色的钱币数有关,而与具体哪些钱币是哪种颜色无关,也与得出此时颜色分布结论的称量历史无关(换句话说,不管之前如何称量过,只要当前局面是如此的颜色分布,那么之后的处理是一样的).同时,当前局面的最优策略显然适用于一切得到此局面的历史.
显然,这是一个典型的动态规划问题.
记四种颜色的数量K,R,B,V,则此四个变量足以表述任意一个局面的一切信息.显然我们有K+R+B+V=27,故以下我们用[K,R,B]表示一个局面.
用f(K,R,B)表示对于局面[K,R,B],最优策略需要多少次称量.我们有
f(26,0,0)=f(26,1,0)=f(26,0,1)=0,f(27,0,0)=0,
f(K,R,B)=1+min{max{f(K+r1+r2+b1+b2+v1+v2,R-r1-r2,B-b1-b2),f(27-r1-b2-v1-v2,r1+v1,b2+v2),f(27-r2-b1-v1-v2,r2+v2,b1+v1)}} (K<26),
其中min有(k1,r1,r2,b1,b2,v1,v2)遍历[0,K]x[0,R]x[0,R]x[0,B]x[0,B]x[0,27-K-R-B]x[0,27-K-R-B],且r1+r2<=R,b1+b2<=B,v1+v2<=27-K-R-B,k1+r1+b1+v1=r2+b2+v2>0,(r2=b1=v1=v2=0,r1=R,b2=B,K+R+B=27)为假,(r1=b2=v1=v2=0,r2=R,b1=B,K+R+B=27)为假.
至此,足以得出所求为f(0,0,0)=4(不保证结果正确).
ps.附代码..(同样不保证正确)

> restart;
> f:=proc(K,R,B)
> option remember;
> local V,k1,r1,r2,b1,b2,v1,v2,aux,res;
> if K>=26 then return 0 fi;
> V:=27-K-R-B;
> res:=infinity;
> for k1 from 0 to K do
> for r1 from 0 to R do
> for r2 from 0 to R-r1 do
> for b1 from 0 to B do
> for b2 from 0 to B-b1 do
> for v1 from 0 to V do
> aux:=0;
> v2:=k1+r1+b1+v1-r2-b2;
> if v2>=0 and v1+v2<=V and r2+b2+v2>0 and not(r1=R and b2=B and V+r2+b1+v1+v2=0) and not(r2=R and b1=B and V+r1+b2+v1+v2=0) then
> if aux<f(K+r1+r2+b1+b2+v1+v2,R-r1-r2,B-b1-b2) then aux:=f(K+r1+r2+b1+b2+v1+v2,R-r1-r2,B-b1-b2) fi;
> if aux<f(27-r1-b2-v1-v2,r1+v1,b2+v2) then aux:=f(27-r1-b2-v1-v2,r1+v1,b2+v2) fi;
> if aux<f(27-r2-b1-v1-v2,r2+v2,b1+v1) then aux:=f(27-r2-b1-v1-v2,r2+v2,b1+v1) fi;
> if res>aux then res:=aux fi fi od od od od od od:
> return 1+res end:
> f(0,0,0);

复制代码

ps2.只须对以上程序略加输出,我们可以看到满足条件的称量方法极多.下面即随意给出一种合适的方法:
(初始局面:27个无色钱币.)
第一次称量:左右各放置7枚无色钱币.

平衡.
将此14枚钱币染成黑色.
现有14枚黑色钱币和13枚无色钱币.
第二次称量:左右各放置4枚无色钱币.
- 平衡.
  将此8枚钱币染成黑色.
  现有22枚黑色钱币和5枚无色钱币.
  第三次称量:左边放置3枚黑色钱币,右边放置3枚无色钱币.
  - 平衡.
    将此3枚钱币染成黑色.
    现有25枚黑色钱币和2枚无色钱币
    第四次称量:左边放置1枚黑色钱币,右边放置1枚无色钱币.
    - 平衡.
      余下那枚未称量无色钱币即为所求.
    - 不平衡.
      右边的无色钱币即为所求.
  - 不平衡.
    右边3枚钱币重(轻).
    第四次称量:在此3枚钱币取两枚分别放置在左右两边.
    - 平衡.
      此3枚中未参与此次称量的那枚即为所求.
    - 不平衡.
      此时左右两边中重(轻)的一边那枚钱币即为所求.
- 不平衡.
  将重的一边的4枚钱币染成红色,将轻的一边的4枚钱币染成蓝色,将余下5枚无色钱币染成黑色.
  现有19枚黑色钱币和4枚红色钱币和4枚蓝色钱币.
  第三次称量:左右各放置1枚红色钱币和2枚蓝色钱币.
  - 平衡.
    将此6枚钱币染成黑色.
    现有25枚黑色钱币和1枚红色钱币和1枚蓝色钱币.
    第四次称量:左边放置2枚黑色钱币,右边放置1枚红色钱币和1枚蓝色钱币.
    若右边重(轻),则此红(蓝)色钱币即为所求.
  - 不平衡.
    将重的一边的2枚蓝色钱币染成黑色,将轻的一边的1枚红色钱币染成黑色,将余下的未参与此次称量的1枚红色钱币和1枚蓝色钱币染成黑色.
    现有24枚黑色钱币和2枚红色钱币和1枚蓝色钱币.
    第四次称量:左边放置2枚黑色钱币,右边放置1枚红色钱币和1枚蓝色钱币.
    - 平衡.
      未参与此次称量的那枚红色钱币即为所求.
    - 不平衡.
      若右边重(轻),则右边的红(蓝)色钱币即为所求.
不平衡.
将重的一边的7枚钱币染成红色,将轻的一边的7枚钱币染成蓝色,将余下13枚无色钱币染成黑色.
现有13枚黑色钱币和7枚红色钱币和7枚蓝色钱币.
第二次称量:左右各放置3枚红色钱币.
- 不平衡.
  将轻的一边的3枚钱币染成黑色,将余下的未参与此次称量的1枚红色钱币和7枚蓝色钱币染成黑色.
  现有24枚黑色钱币和3枚红色钱币.
  第三次称量:左右各放置1枚红色钱币.
  若平衡则未参与此次称量的那枚红色钱币即为所求,否则重的一边那枚红色钱币即为所求.

2.
记三人位A,B,C.
I.问A:"((A只说真话且B只说假话)或(A只说假话且C只说真话))吗?"
i.若A答"是":若A只说真话,则B只说假话;若A只说假话,则C不是只说真话,即B只说真话;若A真假话都说,则B只说真话或B只说假话.综上,B只说真话或B只说假话.
ii.若A答"否":同理,C只说真话或C只说假话.
无论如何,找到一个不是真假话都说的X(i中X=B,ii中X=C).
II.问X一个恒真命题,即知X只说真话还是只说假话.
III.问X"A真假话都说吗".下略.
ps.此题我在此论坛已码过若干次答案,包括如何得到这种答案的完整思路.当然,比这次说的详细很多.非知道不可的话自己尝试利用论坛搜索功能..

[逻辑推理] 推理题