主题:【原创】从两个经典智力趣题谈起(一) -- 丁坎
【描述】有 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”,这是可以完成的。
假设结果是“左轻”,推理类前。
引理证毕。
- 相关回复 上下关系8
😂“切分次数越少越好” 衲子 字0 2008-08-06 19:18:03
🙂【原创】称球问题的另外证明。(一)【二色划分引理】 2 衲子 字905 2008-08-06 12:35:59
🙂【原创】称球问题的另外证明。(二)【称球引理1】 1 衲子 字2225 2008-08-06 13:53:50
🙂【原创】称球问题的另外证明。(三)【称球引理2】
🙂【原创】称球问题的另外证明。(四)【主定理】 4 衲子 字1070 2008-08-06 14:54:22
🙂说的明白,送花! 王树 字0 2008-08-07 06:03:45
🙂【原创】从两个经典智力趣题谈起(四)(上) 11 丁坎 字4166 2008-08-06 08:35:18
🙂沙发花! 1 王树 字112 2008-08-06 09:47:24