八硬币问题
在120枚外观相同的硬币中,有一枚是假币,并且已知假币和真币的重量不同,但不知道假币与真币相比较轻还是重,可以通过一架天平来任意比较两组硬币,最坏情况下,能不能之比较5次就检测出这枚硬币
[解决办法]
可以
先给个定理1:给定3^n个球,已知其中一部分可能偏轻,另一部分可能偏重,那么n次必然可以分出结果
120,两边各40,如不平,由定理1,80个4次可以分出
如平,在剩余40个取13个放左边,同时左边加一个好球(从80个里面随便取一个),右边14个,如不平,由定理1,27个3次分出
如果还是平,剩余13个取4个加一个好球放左边,5个放右边,不平由定理1,2次分9个
如果还是平,剩余4个取1个加一个好球放左边,2个放右边,不平由定理1,1次分3个
平的话必然剩下最后一个是坏球,和一个好球称一下,结束
至于定理1,证明应不难,懒得写了