×

Loading...
Ad by
  • 最优利率和cashback可以申请特批,好信用好收入offer更好。请点链接扫码加微信咨询,Scotiabank -- Nick Zhang 6478812600。
Ad by
  • 最优利率和cashback可以申请特批,好信用好收入offer更好。请点链接扫码加微信咨询,Scotiabank -- Nick Zhang 6478812600。

对于N(m)=(3^m-1)/2个小球,现在我们来寻求m次的解法。。。

本文发表在 rolia.net 枫下论坛首先,对于m=2的情况,相当于四个小球来称两次的情况,这个已经讨论过多次了,也很
简单,在此略去?nbsp;
其次,若m?lt;=k-1时,假定对于N(k-1)=(3^(k-1)-1)/2个球的情况我们都有解法。
现在来考虑m=k的情况。
第一次称取[3^(k-1)-1]个球放在天平天平两端,则:
如果平衡,获得[3^(k-1)-1]个标准球,坏球在剩下的[3^(k-1)+1]/2个中。由于
[3^(k-1)-1]>=[3^(k-1)+1]/2,(k>=2),即已知的标准球数不小于未知球数?nbsp;
所以在以后的测量中就相当于任意给定标准球的情况,由前面的引理二可知
对于[3^(k-1)+1]/2的情况(k-1)次可解。
如果不平衡,大的那方记做A,小的那方记作B。标准球记做C.
则现在我们有[3^(k-1)-1]/2个A球和B球,有[3^(k-1)+1]/2个C球。
第二次用3^(k-2)个A球加[3^(k-2)-1]/2个B球放左边?nbsp;
3^(k-2)个C球加[3^(k-2)-1]/2个A球放右边。
如果左边大于右边,则说明是在左边的3^(k-2)个A球中质量大的为坏球;
如果左边等于右边,则说明是在第二次称时没用的3^(k-2)个B球中质量轻
的为坏球。以上两种情况都可以再用三分法(k-2)次解决,加上前两
次共k次解决。
如果左边小于右边,则坏球在左边的[3^(k-2)-1]/2个B球中或在右边的同样
数目的A球中。此时的情况和第二次开始时类似(只不过是k-1变成k-2).
用相同的办法一直往下追溯到一个A球和一个B球一次区分的情况,这时
只需拿A球和标准球比较以下就行了。
因此在这种情况下也是可以最终用k次解决的。
由以上两步加上数学归纳法知,对于N(m)=(3^m-1)/2的情况,称m次是可以称出来的。

由这个解法加上前面所给出的上界Nmax(m)<=(3^m-1)/2,知称m次能解决的最大的小球数
Nmax(m)=(3^m-1)/2。更多精彩文章及讨论,请光临枫下论坛 rolia.net
Report

Replies, comments and Discussions:

  • 枫下沙龙 / 休闲娱乐 / 13个球,其中1个和其它球重量不同,如何用天平在3次内把它找出来?
    • 对于N(m)=(3^m-1)/2个小球,现在我们来寻求m次的解法。。。
      本文发表在 rolia.net 枫下论坛首先,对于m=2的情况,相当于四个小球来称两次的情况,这个已经讨论过多次了,也很
      简单,在此略去?nbsp;
      其次,若m?lt;=k-1时,假定对于N(k-1)=(3^(k-1)-1)/2个球的情况我们都有解法。
      现在来考虑m=k的情况。
      第一次称取[3^(k-1)-1]个球放在天平天平两端,则:
      如果平衡,获得[3^(k-1)-1]个标准球,坏球在剩下的[3^(k-1)+1]/2个中。由于
      [3^(k-1)-1]>=[3^(k-1)+1]/2,(k>=2),即已知的标准球数不小于未知球数?nbsp;
      所以在以后的测量中就相当于任意给定标准球的情况,由前面的引理二可知
      对于[3^(k-1)+1]/2的情况(k-1)次可解。
      如果不平衡,大的那方记做A,小的那方记作B。标准球记做C.
      则现在我们有[3^(k-1)-1]/2个A球和B球,有[3^(k-1)+1]/2个C球。
      第二次用3^(k-2)个A球加[3^(k-2)-1]/2个B球放左边?nbsp;
      3^(k-2)个C球加[3^(k-2)-1]/2个A球放右边。
      如果左边大于右边,则说明是在左边的3^(k-2)个A球中质量大的为坏球;
      如果左边等于右边,则说明是在第二次称时没用的3^(k-2)个B球中质量轻
      的为坏球。以上两种情况都可以再用三分法(k-2)次解决,加上前两
      次共k次解决。
      如果左边小于右边,则坏球在左边的[3^(k-2)-1]/2个B球中或在右边的同样
      数目的A球中。此时的情况和第二次开始时类似(只不过是k-1变成k-2).
      用相同的办法一直往下追溯到一个A球和一个B球一次区分的情况,这时
      只需拿A球和标准球比较以下就行了。
      因此在这种情况下也是可以最终用k次解决的。
      由以上两步加上数学归纳法知,对于N(m)=(3^m-1)/2的情况,称m次是可以称出来的。

      由这个解法加上前面所给出的上界Nmax(m)<=(3^m-1)/2,知称m次能解决的最大的小球数
      Nmax(m)=(3^m-1)/2。更多精彩文章及讨论,请光临枫下论坛 rolia.net
      • 实在看不懂,你还是以13个球(即M=3)举例子吧
        • 数学归纳法
    • (1) 6,7 if(6) then 3,3, then 1,1 and 1; if(7) then 3,3, then 1,1, and 1
      • But you don't know the special ball is heavy or light than other balls! So your answer is not right.
    • 1, 2/2 以后就可以了,自己想吧
    • 哎,这老套的题不知道还能出多久?
    • 别用GUEST了,这种问题准是金字塔提出的。