15个硬币中有两个略轻的次品。用一架无砝码的天平，问你至少需要几次称量可以找出次品？
原帖见 https://tieba.baidu.com/p/1161581263



usrbin哥哥。。。。昨晚教我学习的帖子怎么没啦。。。

这样的问题我们可以利用信息学原理估算出一个答案的下界。天平有重，轻，平三个状态，那么n次称量后能标识的信息量是3^n。而15个硬币俩次品蕴含的信息量是(15,2)=105。因此答案一个下界就是[log_3{105}]=5。[]是向上取整

这个下界能否取到？答案是肯定的

将15枚硬币分成A,B,C三组，每组5个。令A1表A组第一个硬币，下同。f(S1,S2)表将硬币集盒S1,S2放于天平两边称量。>表左重,<右重。=表平，下同。设两个次品={x,y}.
1.f(A,B)
①A=B。{x,y}⊆C 或 x∈A且y∈B。f(A1+A2,A3+A4):
1)A1+A2=A3+A4,f(A5,C1):
1.A5<C1.x=A5,y∈B.2次可从B中找到y;
2.A5>C1.x=C1,y∈C-C1.2次可以从C-C1中找到y;
3.A5=C1.{x,y}⊆{C1,C2,C3,C4}.f(C1+C2,C3+A1):
I.C1+C2=C3+A1.f(C1,C2).C1>C2=>{x,y}={C2,C3},C1<C2=>{x,y}={C1,C3}.C1=C2=>不可能
II.C1+C2<C3+A1.f(C1,C2).C1>C2=>{x,y}={C2,C4},C1<C2={x,y}={C1,C4},C1=C2=>{x,y}={C1,C2}
III.C1+C2>C3+A1,{x,y}={C3,C4}
2)A1+A2>A3+A4.x∈A3+A4,y∈B.三次称量足够;
3)A1+A2<A3+A4.x∈A1+A2.y∈B.同2)
②A>B.{x,y}∈B 或 x∈B且y∈C.同①
③A<B.{x,y}∈A 或 x∈A且y∈C.同①
如此这个问题就解决了


归纳可证两个轻硬币所需最小称量次数是[log_3{(n,2)}]。这个就留做习题吧

负责的老师

信息学原理？

墒的概念

。。。。。。完全看不懂。。。。

没想到，哥居然知道这个，很不错啊

信息量是3^n？ 我记得好像是2^n，难道是我记错了？

应该是你记错了，嘿嘿

我看一下百度百科，貌似是2^n

？

我自己有点糊涂了，去翻一下教材吧

嘿嘿再水个：球所有n,m∈N使得(n,2)=3^m（这个简单）

(1)3^v=2*3^u+1
(2)3^v+1=2*3^u
(1)
3^v>1,so v!=0,if u!=0
0=0+1(mod3)
so u=0
so n=3 ok
(2)
for u!=0,if v!=0
1=0(mod3)
so v=0
1+1=2*3^u
so u=0
n=2 ok.

不太明白你的解法。这里(n,2)是组合数=n(n-1)/2