IQrace 版 (精华区)

发信人: ciel (二分之根号五减一℃·冬天来啦), 信区: IQrace
标  题: 称小球问题终结----如果要求小球轻重必须判决
发信站: 哈工大紫丁香 (2003年10月25日14:26:29 星期六), 站内信件

与前面的不需判轻重的情况类似的定义和推导，可得：
Nmax(k)=(3^k-3)/2.
N1max(k)=(3^k-1)/2.
意外的发现只比前面不分轻重的情况分别小一！！！
证明过程由于有太多类似，故在此略去，仅举一个例子来说明。
k=3,Nmax=12
共12个球
第一次：  4A ? 4B  剩下4C
  如果相等，则A和B都是标准球。
     第二次 C1+A ? C2+C3
         如果相等，则坏球为C3，再用C3与标准球比较一次即可。
         如果不等，再比较C2和C3，可以这两次结果判断C1,C2,C3中哪个是坏球和轻重。

  如果不等，不妨设4A>4B.此时C球都是标准球。
     第二次  A1+B2+B3+B4 ? B1+C1+C2+C3
         如果相等，则坏球在A2,A3,A4中，且重。再比较A2和A3即知。
         如果左边小于右边，则在B2,B3,B4中且轻。再比较B2和B3即可。
         如果左边大于右边，则是A1且重或是B1且轻 ，再拿A1和标准球即可。

意外的发现只比前面不分轻重的情况分别小一！！！
证明过程由于有太多类似，故在此略去，仅举一个例子来说明。
k=3,Nmax=12
共12个球
第一次：  4A ? 4B  剩下4C
  如果相等，则A和B都是标准球。
     第二次 C1+A ? C2+C3
         如果相等，则坏球为C3，再用C3与标准球比较一次即可。
         如果不等，再比较C2和C3，可以这两次结果判断C1,C2,C3中哪个是坏球和轻重。

  如果不等，不妨设4A>4B.此时C球都是标准球。
     第二次  A1+B2+B3+B4 ? B1+C1+C2+C3
         如果相等，则坏球在A2,A3,A4中，且重。再比较A2和A3即知。
         如果左边小于右边，则在B2,B3,B4中且轻。再比较B2和B3即可。
         如果左边大于右边，则是A1且重或是B1且轻 ，再拿A1和标准球即可。

--
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.228.216]