N球2坏,记为坏A、坏B、正常C,那么M次能最多在几N中称出坏
分三情况考虑
1、A≠B,A+B≠2C
2、A=B,A+B≠2C
3、A≠B,A+B=2C
情况1,A≠B,A+B≠2C
将所有球按二进制编号,第几位是1就表示第几次称量,第几位是0表示第几次不称量,排除编号00..00(全部是0)和11..11(全部是),那么可以确定1、AB都至少各称量1次,2、AB中不可能有1个每次都称量
将每次称量结果记为T_1、T_2、...、T_X、...,当每次称量数量相同时,可能三结果
T_X中仅两结果,那么肯定是JC+A和JC+B两结果,带回二进码就是AB的编号,此时M次能最多在2^M-2个中称出坏
T_X中有三结果,那么可能是
JC+A和JC+B和JC+C
JC+A和JC+B和JC-C+A+B
JC+A和JC+C和JC-C+A+B
每种结果只可能计算出2坏,3结果是6坏,且这每个结果C的数值不可能一样,排除这6坏,任意称量1个,可以知道C,C反过来对应唯一一结果,于是此时M次能最多在2^(M-1)-2个中称出坏
T_X中有4结果,那么只可能是JC+A和JC+B和JC+C和JC-C+A+B,考虑到AB的对称性,4结果只能有以下几排列
JC+A<JC+B<JC-C+A+B<JC+C
JC+A<JC+C<JC-C+A+B<JC+B
JC+A<JC-C+A+B<JC+C<JC+B
JC+C<JC-C+A+B<JC+A<JC+B
同样这4结果只对应唯一的AB编号,以及C的数值,排除2*4=8个编号后就是C的数值,再称量一次就能知道AB编号,于是此时M次能最多在2^(M-1)-2个中称出坏
综合,情况1最多能在2^(M-1)-2个中称出坏
情况2,A=B,A+B≠2C
依然一样编号(但不用排除00..00和11..11),先将所有的称量一次(该次不记入编号)结果为T
当2*T_1=T时,可知AB中仅有1个被称量,此时两部分分别称量(M-2)/2次,并根据结果再称1个,由于只1坏,且知道总重,能找到坏AB,此时M次能最多在2^((M-2)/2+1)个中称出坏
(顺便说,该方法,总球数D,2坏有C(2,D)种可能,不考虑单独称1个的1次,M-1次最多能对应2^(M-1)个结果,有D*(D+1)/2≤2^(M-1),D≤2^(M/2)-1,带人M=7,最多能在10个中找到2坏)
当2*T_1≠T时,如果两坏在T_1中,可以得到ABC的值,两坏不在T_1中也能得到不同的ABC值,随机抽1个称量,即能知道两坏在哪个部分及ABC的值,那么再在坏中找出即可,最多可能保证最后一次称量2个时是两坏,N的上限是2*2^(M-2)
情况3,A≠B,A+B=2C
同情况2考虑,
当2*T_1≠T时,说明2坏分别两堆,然后参考情况2称量
当2*T_1=T时,继续按编号称量到2T_X≠T,再同情况2考虑
分三情况考虑
1、A≠B,A+B≠2C
2、A=B,A+B≠2C
3、A≠B,A+B=2C
情况1,A≠B,A+B≠2C
将所有球按二进制编号,第几位是1就表示第几次称量,第几位是0表示第几次不称量,排除编号00..00(全部是0)和11..11(全部是),那么可以确定1、AB都至少各称量1次,2、AB中不可能有1个每次都称量
将每次称量结果记为T_1、T_2、...、T_X、...,当每次称量数量相同时,可能三结果
T_X中仅两结果,那么肯定是JC+A和JC+B两结果,带回二进码就是AB的编号,此时M次能最多在2^M-2个中称出坏
T_X中有三结果,那么可能是
JC+A和JC+B和JC+C
JC+A和JC+B和JC-C+A+B
JC+A和JC+C和JC-C+A+B
每种结果只可能计算出2坏,3结果是6坏,且这每个结果C的数值不可能一样,排除这6坏,任意称量1个,可以知道C,C反过来对应唯一一结果,于是此时M次能最多在2^(M-1)-2个中称出坏
T_X中有4结果,那么只可能是JC+A和JC+B和JC+C和JC-C+A+B,考虑到AB的对称性,4结果只能有以下几排列
JC+A<JC+B<JC-C+A+B<JC+C
JC+A<JC+C<JC-C+A+B<JC+B
JC+A<JC-C+A+B<JC+C<JC+B
JC+C<JC-C+A+B<JC+A<JC+B
同样这4结果只对应唯一的AB编号,以及C的数值,排除2*4=8个编号后就是C的数值,再称量一次就能知道AB编号,于是此时M次能最多在2^(M-1)-2个中称出坏
综合,情况1最多能在2^(M-1)-2个中称出坏
情况2,A=B,A+B≠2C
依然一样编号(但不用排除00..00和11..11),先将所有的称量一次(该次不记入编号)结果为T
当2*T_1=T时,可知AB中仅有1个被称量,此时两部分分别称量(M-2)/2次,并根据结果再称1个,由于只1坏,且知道总重,能找到坏AB,此时M次能最多在2^((M-2)/2+1)个中称出坏
(顺便说,该方法,总球数D,2坏有C(2,D)种可能,不考虑单独称1个的1次,M-1次最多能对应2^(M-1)个结果,有D*(D+1)/2≤2^(M-1),D≤2^(M/2)-1,带人M=7,最多能在10个中找到2坏)
当2*T_1≠T时,如果两坏在T_1中,可以得到ABC的值,两坏不在T_1中也能得到不同的ABC值,随机抽1个称量,即能知道两坏在哪个部分及ABC的值,那么再在坏中找出即可,最多可能保证最后一次称量2个时是两坏,N的上限是2*2^(M-2)
情况3,A≠B,A+B=2C
同情况2考虑,
当2*T_1≠T时,说明2坏分别两堆,然后参考情况2称量
当2*T_1=T时,继续按编号称量到2T_X≠T,再同情况2考虑