国家集训队2003论文集 何林

《国家集训队2003论文集 何林》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一类称球问题的解法问题的提出给定N个球有个比标准球重的次品混入其中你有一架天平，用最少的次数找出这个次品。N=312312①是次品12②是次品12③是次品N=3时称1次就可以找出次品N=9123456789ABCAB次品在A中次品在B中AB通过一次称量，可以把次品可能存在的范围从9个，缩小到3个N=3的时候一次就能称出次品N=9时称2次次品在C中AB更一般的情况N=3k12k……12k……12k……ABC更一般的情况ABABAB次品在A中次品在B中次品在C中范围缩小到原来的1/3更一般的情况n=3k+1,n=3k+2和n=3k类似，也是均分成三堆每次称量把范围大

2、致缩小到原来的1/3因此：从n个球中找次品至多要称[log3n]次。（[]统一表示取上整）判定树[log3n]无疑是可行解。最优性为什么三分？因为天平只有三种可能：左偏、右偏、平衡判定树称(1,2)>=<132叶子代表结果非叶子代表一次称量每个非叶子节点都有三个孩子，表示天平左偏、右偏、平衡判定树比较(1,2,3)与(4,5,6)>=<比较(1)与(2)>13=<2比较(7)与(8)>79=<8比较(4)与(5)>46=<5判定树的深度就是称量次数一个有意义的判定树至少n个叶子节点判定树N个叶子的三叉树的深度h>=[log3n][log3n]是最优解小结引进了有

3、力工具：判定树。将主观的直觉严谨化。三分法是解决这类问题的根本着眼点。三分时必须充分的均匀分配的均匀性123……9称(1,2)><1次品2次品=3…9都可能是次品N个叶子的三叉树的深度h>=[log3n]深度很大，远超过其兄弟问题2的提出N个球，混入了一个轻重不详的次品手中有一架天平和一个标准球用最少的次数称出次品并求出次品的轻重问题2的基本分析12可得如下信息：次品若在①中，则它偏重。次品若在②中，则它偏轻。引理的提出已知两堆球，第一堆有a个、第二堆有b个。若次品在第一堆，必是重球若次品在第二堆，必是轻球分析总共a+b个球每个球都有可能是次品判定树至少a+b个

4、叶子树的深度h>=[log3(a+b)]只要称[log3(a+b)]次就能找到次品引理的分析a=3p……p个……p个……p个A1A2A3b=3q……p个B1B2B3……p个……p个引理的分析A1B1A2B2A3B3次品在A1或者B2范围被缩小到p+q个球里面引理的分析A1B1A2B2A3B3次品在B1或者A2范围被缩小到p+q个球里面引理的分析A3B3次品在A3或者B3范围被缩小到p+q个球里面A1B1A2B2子问题的分析总共a+b=3(p+q)个球无论天平怎么偏，都可以把范围缩小到p+q个球中，即原来的1/3根据a,bmod3的余数分类，上面讨论的是amod3

5、=bmod3=0的情况。其他情况可类似进行。关键要“均”分。引理中问题称[log3(a+b)]次即可。问题2的分析n个球，每个球都有可能是轻球或者重球，有2n种不同的可能结果判定树至少要2n个叶子节点判定树的深度h>=[log3(2n)]问题2的分析比较S与1>=<1L比较S与2>2L/=<2H1HN=2接着对n归纳问题2的分析n=3p……p个……p个……p个A1A2A3假设小于n的球都能在[log3(2n)]次内称出次品问题2的分析A1A2A1中的球只可能重A2中的球只可能轻。A1A2A2中的球只可能重A1中的球只可能轻。天平不平衡，次品必在A1或者A2中归结

6、到引理，只要称[log3(p+p)]次问题2的分析A1A2次品在A3中，根据归纳假设，还要称[log3(2p)]次无论天平怎么偏，称完一次后都还要称[log3(2p)]次共称[log3(2p)]+1=[log3(6p)]=[log3(2n)]次问题2的分析称(A1,A2)><=A1重或A2轻2p个叶子节点A1轻或A2重2p个叶子节点A3轻重都有可能2p个叶子节点

7、A1

8、=

9、A2

10、=

11、A3

12、=p总共有6p个叶子节点问题2的分析n=3k+2分法

13、A1

14、=k+1

15、A2

16、=k+1

17、A3

18、=k6k+4个叶子节点分摊到每个孩子是：2k+22k+22k是均匀的问题2的分析N=

19、3k+1分法一：k，k，k+1分摊的叶子节点：2k，2k，2k+2分法二：k+标准球，k+1，k分摊的叶子节点：2k+1，2k+1，2k问题2的小结[log3(2n)]即是问题2的解。最优性和可行性均已证明判定树是一种估界和证明最优性的有力工具。通过对判定树的研究，衍生了一条重要的原则：均匀。均分的对象不是球，而是叶子节点（即不同的结果）。其他形式只要求次品，不求轻重。结论是[log3(2n-1)]问题2去掉标准球。第一次称的时候就不能保证一定均匀。结论是[log3(2n+2)]万变不离其宗，解决此问题的精髓在四个字：均匀三分总结1、从简单入手2、求同存异3、严

20、谨细心