主题：【原创】由一个简单的面试题想起的 -- 东方射日

摔包裹更有意义。。。

楼下有了论文链结，那个论文又是定理又是引理的，似乎太长了点。来一个短的。。。

前提，或者说，假设，那个论文给的够详细了，不再重复。这里只是指出一点：

设M1<M2,那么，事件｛包裹在M1摔坏｝包含了事件｛包裹在M2摔坏｝。或者，事件｛包裹在M2不摔坏｝包含了事件｛包裹在M1不摔坏｝。记P(M1)为事件｛包裹在M1摔坏｝的概率，P(M2)为事件｛包裹在M2摔坏｝的概率，那么事件｛包裹在M2摔坏|包裹在M1不摔坏｝的概率是P(M2)－P(M1)。

设包裹1的实验序列是｛M(1),M(2),...M<(K)｝，不失一般性，可假设M(K)=N。因如果M(K)<N，总可以将包裹2的最后一次实验转移到包裹1，从而M(K+1)=N。

设包裹在1,2,...,N层摔坏的概率分别是P(1),P(2),...,P(N)。为记号简单，补充M(0)=0,P(0)=0.

１。极大极小解

包裹1的实验序列是｛M(1),M(2),...M<(K)｝，

f(M)=MIN(包裹1的最大次数＋包裹2的最大次数)

=MIN(K+MAX(M(j)-M(j-1)-1){j从1到K})

对于固定K，当序列｛M(1),M(2),...M<(K)｝步长不均时，MAX(M(j)-M(j-1)-1){j从1到K})将变大，所以极小解只在那些等步长序列中达到（忽略取整因素）。

序列｛M(1),M(2),...M<(K)｝等步长时，

f(M)=MIN(K+N/K-1)

上式在K=N/K，或K=sqrt(N)时，有极小值，

f(M)=2*sqrt(N)-1。

可做推广，3个包裹时，极值函数是

f()=MIN(K+J+N/(K*J)-2),对K、J求极值。

在K＝J＝N/(K*J)，或K＝J＝N^(1/3)时，

f()=3*N^(1/3)-2

再推广，Ｌ个包裹时，f()=Ｌ*N^(1/Ｌ)-Ｌ＋１。

打字困难，概率极小的情形待续。。。。。