五千年(敝帚自珍)

主题:【原创】从两个经典智力趣题谈起(一) -- 丁坎

共:💬102 🌺203
全看分页树展 · 主题 跟帖
家园 【原创】称球问题的另外证明。(四)【主定理】

【描述】有 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 :-)

全看分页树展 · 主题 跟帖


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河