五千年(敝帚自珍)

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

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

【描述】有 N =(3^n - 1)/2 个球,其中可能有一个坏球。(坏球可能比好球轻、也可能比好球重。)我们手头还有一个已知的好球。

有一台只能给出{“左重”、“平衡”、“左轻”}指示的天平。

【称球引理2】称量n次,便可确定:有没有坏球,若有,坏球在哪儿,它比好球轻还是重?

【证明】

分析:这N个球可能的状况共有 1 + 2×N = 3^n 个。(‘1’:没有坏球;‘2×N’:坏球在1……N个位置上,每个位置上还有轻或重两种可能。) 称量n次能给出的信息就是 3^n 个(不取log2())。所以,这个N是n次称量所能确定结果的球数上确界。 同样地,“称球引理1”也是上确界。

(A)当n=1,那么N=1,将它和手头的好球用天平作比较,就知道结果了。

(B)设n=K,命题成立。

(C)当n=K+1,我们如此来划分那N个球:

留着 N0 = (3^K - 1)/2 个球不选,选中的是 N - N0 = (3^(K+1) - 1)/2 - (3^K - 1)/2 = (3^(K+1) - 3^K)/2 = (3× 3^K - 3^K)/2 = 3^K. 这是奇数,无法分成相等个数的两份,放在天平的左右边。不用急,这时那个好球正好可以派上用场了。将那 3^K 个球,连同一个好球,划分成两份(每份有(3^K+1)/2个球),放在天平的两端。进行称量。

假设结果是“平衡”,那么那个可能的坏球只能在那留下的N0个球中。我们还剩K次称量,由(B),保证可以完成任务。

假设结果是“左重”,那么那个必然的坏球就在天平上的 N - N0 个球中,我们就可以给这些球贴上标签,凡是在左端的球,都贴上“可能重”的标签;凡是在右端的球,都贴上“可能轻”的标签。(好球不用贴标签了。) 那么我们手头的问题是: 3^K 个有标签的球,需要称量K次,将坏球(及其轻重)找出来。由“称球引理1”,这是可以完成的。

假设结果是“左轻”,推理类前。

引理证毕。

全看分页树展 · 主题 跟帖


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

Copyright © cchere 西西河