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



这样的问题我们可以利用信息学原理估算出一个答案的下界。天平有重，轻，平三个状态，那么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)}]。这个就留做习题吧

负责的老师

墒的概念

应该是你记错了，嘿嘿

？

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

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

注意到(n,n-1)=1后面讨论更简单

谢谢蛋加大难度啦，现在15个硬币里有1个轻的一个重的。请用最小的称量次数把它们找出来

如果a≥c≥b,a^2+c^2>5c^2,a>2c≥b+c就矛盾啦

是啊。而且要知道哪个轻哪个重

这个关系是未知的（不能拿来做比较的依据)

想一想呀么想一想

就是三种可能性都有（且未知）

对的。试试看5次行不行 *_^

容后再细看谢谢小仙，以后不要熬太晚咯