8球中有2个轻球

litaoye

同事想出了一个3,3,2的分法，状态也是划分为10,9,9，也是可行的方法

hujunhua

3次是不可能达到的。因为$C_8^2>3^3$. 但是估计如果题目改成13个球中两个轻球，4次应该是达不大的mathe 发表于 2010-7-7 08:45

把问题改变一下：

实际的天平，横臂并非只是一根扁担，而是一个十字架，下垂还比较长，起平衡补偿作用（如图）。不平衡没这种机构补偿的话，天平就一倾到底了，既影响称量操作，又容易损坏刀刃。

为了天平的灵敏度，这个补偿矩是不能太大的。假定咱们天平的补偿矩专门设计的，1个轻球的亏欠刚好可以使平倾斜10度，2个倾斜20度，这个角差从补偿杆的摆幅是足以识别的。 那么，8球和13球各需要多少次呢？

hujunhua

机械式分析天平一般是阻尼电光天平，既要补偿差重，又要提高灵敏度，微小的倾斜通过光路放大了很多倍，比楼说的更易识读。

qianyb

22# hujunhua
根据信息论$C_8^2=28<3^4$,$C_13^2=78<3^4$
8和13只要三次吧

hujunhua

用对称编码，8个球标为-4，-3，-2，-1，1，2，3，4号，并将编号转译为对称三进制的两位数（-1用i代替）：
1=01，-1=0i
2=1i，-2=i1
3=10，-3=i0
4=11, -4=ii
对于28种组合，直接取其两个球的编码按对称9进制编码，如ID(1,2)=12或者21，再译成对称三进制的4位数，也就是将两个号码的对称三进数拼接。例如ID(1,2)=12或者21=011i或者1i01.组合编码的位从左到右记为$b_1,b_2,b_3,b_4$
由于组合需要4位编码，所以我们按4次来称，为了使每次称量容纳最多的组合，从而使4次称量能包含全部组合，每次都称全部球，左右各4个球。球的分组记为$(L_1,R_1)$, $(L_2,R_2)$, $(L_3,R_3)$, $(L_4,R_4)$,L--左边，R--右边。分组规则如下：对于组合A，

当$b_n=1$，则A∈$L_n$
当$b_n=i$，则A∈$R_n$
当$b_n=0$，则A分属$L_n$和$R_n$

称量的结果，左边轻记为1，右边轻记为i,平衡则记为0。四次称完得到记录$b_1b_2b_3b_4$，当作4位的对称三进数转译成2位的对称9进数，按位就是两个轻球的编号。

问题是：这样的分组办得到吗，会不会有冲突？如果每种组合都是唯一编码，那是要冲突的。好在每种组合有两种排列，对应两种编码可供选择，使得分组的存在成为可能。但在4次称量分组中应该一致地按一种编码作安排。谁来试安排一下？共是2^28种选择，有点多，需要电脑编程吧

hujunhua

试了一下，不用电脑排，手工就可了。结果发现排不出来，冲突。

每个组合恰好两个4位三进数编码，变换关系是b1--b3互换，b2--b4互换。如果一个组合的b1=b3=1（or i)，那么不论按哪个编码，它都必须出现L1和L3(or R1和R3)。同样，若b2=b4=1(or i), 那么它都必须出现L2和L4(or R2和R4)。这就可以在选择编码之前确定很多球的部分组位。结果就发现与余下的编码有冲突。

litaoye

恩，这类信息论相关的问题，确实都可以转化为编码问题。
多想了一下大概10个球，2个轻的也可以4次搞定。一直希望能够用程序来解决这类天平称球的问题，不过试过2次都没有成功，需要手工介入，设定不少条件才能求解，适用范围很小，不知有谁对这方面研究的比较深，讲解一下。

wayne

22# hujunhua


这个补偿杆跟 平杆秤的秤砣的作用是一致的，也就是说这个跟精确测量没什么差别。
===================
最多能用到三进制

hujunhua

我试过k次可以区分n个球(2轻)，n的范围：
1次：3球
2次：4球
3次：5~7球
4次：8~11球（也就是说，主题帖给的8球是下界，所以显得比较宽松，不成问题）
5次：12球~？

关于这个问题，需要解决一个过渡问题：两筐球，每筐n个各有一轻球，此外一旁还有很多标准球（实际情况往往如此），问需要称几次可以找出两个轻球。

hujunhua

这个问题，且称为“n球2轻”问题，既不是单纯的三进制，也不是单纯的二进制,究竟如何编码还没摸清楚。
设第k次可以将未知球缩减为$n_k$个（并记$n_0=n$)，三进制是基于$n_{k+1}=ceiling(n_k/3)$，二进制是基于$n_{k+1}=ceiling(n_k/2)$。但在“n球2轻”问题中，这两式都不能一贯地成立。