主题:【原创】从两个经典智力趣题谈起(一) -- 丁坎
【描述】有 N =(3^n - 3)/2 个球,其中可能有一个坏球。(坏球可能比好球轻、也可能比好球重。)
有一台只能给出{“左重”、“平衡”、“左轻”}指示的天平。
【称球定理】称量n次,便可确定:有没有坏球,若有,坏球在哪儿,它比好球轻还是重?
【证明】
分析:这与“称球引理2”的差别在于,现在我们手头没有好球了,致使N比上确界少1。
我们这样来划分这N个球:
留着 N0 = (3^(n-1) - 1)/2 个球不选,选中的是 N - N0 = (3^n - 3)/2 - (3^(n-1) - 1)/2 = (3^n - 3^(n-1) -2)/2 = 3^(n-1) - 1. 这是个偶数,因此可以分成两份,放在天平左右端。进行称量。
假设结果是“平衡”,那么那个可能的坏球只能在那留下的 N0=(3^(n-1) - 1)/2 个球中。而且,我们手头有了好球(天平上的就是),于是便可运用“称球引理2”(“称球引理2”给出的是上确界)。于是,剩下的n-1次称量,保证可以完成任务。
假设结果是“左重”,那么依照在“称球引理2”的证明中的方法,给天平上的球贴标签。于是,我们有3^(n-1)-1 个贴有标签的球,还能称量n-1次,由“称球引理1”,这是可以完成的。(实际要求比“称球引理1”所给出的上确界还宽松。)
假设结果是“左轻”,推理类前。
定理证毕。
Q.E.D. (Quite Easily Done :-)
- 相关回复 上下关系8
🙂【原创】称球问题的另外证明。(一)【二色划分引理】 2 衲子 字905 2008-08-06 12:35:59
🙂【原创】称球问题的另外证明。(二)【称球引理1】 1 衲子 字2225 2008-08-06 13:53:50
🙂【原创】称球问题的另外证明。(三)【称球引理2】 2 衲子 字1463 2008-08-06 14:34:47
🙂【原创】称球问题的另外证明。(四)【主定理】
🙂说的明白,送花! 王树 字0 2008-08-07 06:03:45
🙂【原创】从两个经典智力趣题谈起(四)(上) 11 丁坎 字4166 2008-08-06 08:35:18
🙂沙发花! 1 王树 字112 2008-08-06 09:47:24
🙂从两个经典智力趣题谈起(三) 22 丁坎 字3669 2008-08-05 01:13:47