[今天我们思考10]

[silwile]

1.先来个warm-up的题吧：现在有8个球，我们已知其中有且仅有一个球的质量比其他球的质量稍微重一些。现在给你一架天平，问最少多少次就可以把那个球给辨别出来？

2.一个简单题： 有一个盒子，盒子里面有三种颜色的球，它们分别为红，黄，蓝。其中，我们可以拿出两个不同颜色的的球，去一家商店换取2个另外颜色的球。即1红+1黄可以换得2个蓝球，1红+1蓝可换得2个黄球，1黄+1蓝可换得2个红球。初始时，盒子里有171个红球，172个蓝球，173个黄球。问现在，你能不能经过若干次交换，把盒子里面的球全变成一种颜色的球？如果可以，请把最少的交换次数表示成盒子里球x,y,z的函数。x为红球的数量，y为黄球的数量，z为篮球的数量。

3.一个难题：有一幢300层的高楼，两颗玻璃球。现在你想知道这种玻璃球最高从第几层楼上掉下来仍然完好。已知，如果第x层玻璃球掉下来就破了，那么所有第y(y>=x)层的楼上掉下来玻璃球都会坏掉。请问，最少扔多少次玻璃球就可以保证知道这个问题的答案？

PS:如果你做个这个题了，那么试一试3颗玻璃球。

Good luck and Have fun! :)

[SlackCode]

第一题用62分，两次搞定
第三题我首先想到的是二分的方法……还在想想优化方案

[silwile]

你已经warm up了^-^

2008/4/26 SlackCode <slac...@gmail.com>:

[Wang Xin]

第三题：求最小的n，使得n * (n + 1)/2 >= 300，最后n = 24

在08-4-26，silwile <sil...@gmail.com> 写道：

--
Everything is possible and available if we trust ourselves!

[Wang Xin]

3颗不会，两颗的是一个google曾经的面试题(H)

在08-4-26，Wang Xin <cber.w...@gmail.com> 写道：

第三题：求最小的n，使得n * (n + 1)/2 >= 300，最后n = 24

[Wang Xin]

确切地说，3颗的问题就是另外一个级数求和的问题，不过我已经把级数求和给忘记得差不多了
呵呵，我还是比较喜欢"直觉"后的答案

[silwile]

数字是对的。关键是这个数字怎么来的。其实我们这个系列的最主要目的不是问题的答案，而是求解出问题的过程。希望，能把这个过程写出来，与别人一起分享，讨论。这，应该比仅仅一个答案更有意义的吧。

2008/4/26 Wang Xin <cber.w...@gmail.com>:

[silwile]

两颗的这个问题，也是去年M$的面试题。

如果你深理解了2颗这个问题的答案是怎么来的，那么其实3颗也是一样的。

2008/4/26 Wang Xin <cber.w...@gmail.com>:

[Wang Xin]

2颗这个很简单，3颗同理也可以比较简单
只是2颗的那个级数好求，3颗的级数涉及到平方，我不会

好吧，我就再把2颗的答案来源再稍微地说一下吧： n + (n-1) + (n-2) + ... + 1 >= 300
具体的细节留给别人吧，我相信你应该是知道我的思路是没有问题的（确切地说，我是看过答案的:$，虽然，这个答案来自google之外的某个人的blog）

在08-4-26，silwile <sil...@gmail.com> 写道：

[silwile]

对的。

2颗，3颗，是同样的道理，这点把玻璃球泛化成n可以看得很清楚。

BTW:这个问题的解与杨辉三角有密切的联系。刚开始发现这一点的时候还有点惊喜来着:)

2008/4/27 Wang Xin <cber.w...@gmail.com>:

[怀宇范]

不知道是不是想错了，我感觉第二题答案是不能。。。和我直觉相悖。。。

思路也说一下吧，错也知道是怎么错的。先就是观察球数量的变化，发现如果有任意两种球数目相等，则求解。为了达到两堆球数目相等，就要填平之间的差值，发现，无论如何，差值的变化是0或正负3，无法是1或2，所以觉得无解。。。

2008/4/26 silwile <sil...@gmail.com>:

--
bool ContactMe(person you)
{
if(you.GoTo("14#344, Tsinghua") && you.Find("Fan Huaiyu"))return true;
if(you.MailTo(" dugu...@gmail.com ") || you.MailTo(" fan...@mails.tsinghua.edu.cn "))return true;
if(you.PhoneTo("13488810330") || you.PhoneTo("01062778689"))return true;
if(you.QQTo("120628812") || you.MSNTo("dugu...@hotmail.com"))return true;
if(you.NetTo(" www.cnblogs.com/duguguiyu "))return true;
return false;
}

[windstorm]

第三题解与杨辉三角有密切的联系？silwile到时候解释一下哈。

我当时看这道题倒是自己猜出来的，我也不知道为啥，就是猜了几种方法，发现这种方法步骤最少，也想不出其他更少的，结果一看答案，还真是这种方法

要让我当时数学归纳出来，还觉得困难......当然后来也看了答案，就不困难了，呵呵。

第一题很简单，第二题想了一个小时了，还是没想出方法来，先睡觉了。

2008/4/27 silwile <sil...@gmail.com>:

[Hongzhang Liu]

对于171,172,173这样的三个数是不可能的，列个方程就可以判断出来了。
将三种变换的数目设为a，b，c，则经过变换后，
x' = x - a + 2b - c
y' = y - b + 2c - a
z' = z - b - c + 2a

不失一般性，设x' = y' = 0，则将上两式相减，得到：
y - x = 3(b - c)
这样y与x的差值必然为3的倍数。

从上面的式子可以解出：
b = (y - x)/3 + c
a = (x + 2y)/3 + c

a + b + c = y + 3c

c为0时取最小值y。y = min{ n | n - n' % 3 == 0 && n, n' in { x, y, z } }

2008/4/27 怀宇范 <dugu...@gmail.com>:

[怀宇范]

恩，我也是这么觉得，现在发现不是被自己的直觉骗了，而是被题目骗了，后续还有那么多问题，怎么感觉都是一个有解的题目。。。

2008/4/27 Hongzhang Liu <hongzh...@gmail.com>:

[kicool]

第三题我的思路是构造一个二叉树表达决策过程，这个树有如下特性：
1.内结点由且只由1-N这N个数构成；叶结点由且只由0-N这N+1个数构成；
2.结点的左子树小于结点，结点小于右子树；
3.树的根节点表示第一次做实验（扔球的楼层数），依次类推在树的第k层的内结点表示第k次做实验的楼层数；左侧分支表示球破损，右侧表示球完好；因此叶结点从左到右升序排列；
4.故由题目条件中的只有两个好球，表示，该树从根结点到任意一叶结点的路径，包含的左侧分支个数最大为2；
5.题目所求即为给出N构造出满足上述条件的树，求树最小高度。遗憾的是数学功力有限不知该如何在这个构造下计算出结果。

[kicool]

还有个条件，就是一旦出现了2次摔坏的，就不能继续试验了。

2008/4/27 kicool <kic...@gmail.com>:

[silwile]

 这是一些很好的有关算法书上典型的命题风格 :)
 不要被后面的问题所迷惑，其实很多题之所以出后面的问题就是想让你想想能够完成题目中的结果所需要的充要条件是什么。就这个问题来讲，就是初始条件需要满足什么样的特性，才能成功的将盒子里面的球全部换成清一色的球。最初一问不过是这个问题的一个子问题而已。

2008/4/27 怀宇范 <dugu...@gmail.com>:

[silwile]

2次摔坏？应该是2个球摔坏吧 :-)

2008/4/27 kicool <kic...@gmail.com>:

[silwile]

okay, i will :)

2008/4/27 windstorm <likunar...@gmail.com>:

[kicool]

呵呵，对的，是2个球摔坏。
想出一个解，就是C(2,k)+C(1,k)+C(0,k)>=N+1,化解(k+2)(k+1)/2>=N+1,当N=300时，k最小取24。如果有j(j<=k)个球,C(j,k)+C(j-1,k)+...+C(1,k)+C(0,k)>=N+1。当j很大时，是不是直接可用二分法？

2008/4/27 silwile <sil...@gmail.com>:

[silwile]

对，对j很大时，就可以直接用二份法。

BTW: a nice progress :P

2008/4/27 kicool <kic...@gmail.com>:

[王小康]

第一题稍微简单一些,跟上面说的一样,分成6/2两堆.二分法.
第二题答案为没有.貌似要想找到一个可以弄成单色的分组只能是有两个颜色的球的数目是一样的,要不然好像是不可以的. 但是遗憾的是,不会证明......
第三题目应该是二分法.看了上面的答案还是看不明白.小弟愚钝,能不能给一个通俗的解现看看.先别给公式.........就拿两个球来说,先试哪一层,然后怎么办......

2008/4/27 silwile <sil...@gmail.com>:

--
http://egmkang.cnblogs.com/

[杨堃]

      初次发帖，请各位大牛指点，我来谈谈第三题，首先如果是2个球，那么我们可以推出，实际上我们只能有1个球在摔，另外1个球是用来返回场景的。我觉得，如果能够想清楚这一步，那后面的就好解决了。假设300层楼最少需要T次，那么我们知道这个球第一次应该放在T的位置上，这样才可以保证T以内的任何一层都能在T次解决，ok。那如果第一次在T的位置上没有坏，那第二次应该在哪里呢？很简单，因为已经试了一次，所以第二次的位置应该在T+T-1这个位置上，所以后面就可以以此类推。因此，我们可以得到T+T-1+T-2....+1>=300这可以得出T=24.

      我们已经知道了2个玻璃，那3个玻璃是一样的道理，3个玻璃那就是说我们可以用2个玻璃去实验，留1个玻璃返回场景。因此，同样道理，第一次的位置，第一个玻璃T，第二个玻璃T+T，第二次的时候，第一个玻璃T+T+T-1，第二个玻璃T+T+T-1+T-1。。因此我们可以得出结论，2*（T+T-1+T-2+T-3..+1）>=300 可以得出T=17.

      我的主要思路就是，若先假设T次的话，后面的结果是类似的。

 

在08-4-27，王小康 <egm...@gmail.com> 写道：

[Justin L]

对于这个话，结论的得出是不是过于笼统了点，怎么就得到T+T-1的位置上了呢？
『 “很简单，因为已经试了一次，所以第二次的位置应该在T+T-1这个位置上”』

On 4月27日, 下午11时37分, "杨堃" <yangkun0...@gmail.com> wrote:
> 初次发帖，请各位大牛指点，我来谈谈第三题，首先如果是2个球，那么我们可以推出，实际上我们只能有1个球在摔，另外1个球是用来返回场景的。我觉得，如果能够想清楚这一步，那后面的就好解决了。假设300层楼最少需要T次，那么我们知道这个球第一次应该放在T的位置上，这样才可以保证T以内的任何一层都能在T次解决，ok。那如果第一次在T的位置上没有坏，那第二次应该在哪里呢？很简单，因为已经试了一次，所以第二次的位置应该在T+T-1这个位置上，所以后面就可以以此类推。因此，我们可以得到T+T-1+T-2....+1>=300这可以得出T=24.
>
> 我们已经知道了2个玻璃，那3个玻璃是一样的道理，3个玻璃那就是说我们可以用2个玻璃去实验，留1个玻璃返回场景。因此，同样道理，第一次的位置，第一个玻璃T，第二个玻璃T+T，第二次的时候，第一个玻璃T+T+T-1，第二个玻璃T+T+T-1+T-1。。因此我们可以得出结论，2*（T+T-1+T-2+T-3..+1）>=300
> 可以得出T=17.
> 我的主要思路就是，若先假设T次的话，后面的结果是类似的。
>

> 在08-4-27，王小康 <egmk...@gmail.com> 写道：
>
>
>
> > 第一题稍微简单一些,跟上面说的一样,分成6/2两堆.二分法.
> > 第二题答案为没有.貌似要想找到一个可以弄成单色的分组只能是有两个颜色的球的数目是一样的,要不然好像是不可以的. 但是遗憾的是,不会证明......
>
> > 第三题目应该是二分法.看了上面的答案还是看不明白.小弟愚钝,能不能给一个通俗的解现看看.先别给公式.........就拿两个球来说,先试哪一层,然后怎么办......
>
> > 2008/4/27 silwile <silw...@gmail.com>:

>
> > > 对，对j很大时，就可以直接用二份法。
>
> > > BTW: a nice progress :P
>
> > > 2008/4/27 kicool <kic...@gmail.com>:
>
> > > > 呵呵，对的，是2个球摔坏。
>
> > > > 想出一个解，就是C(2,k)+C(1,k)+C(0,k)>=N+1,化解(k+2)(k+1)/2>=N+1,当N=300时，k最小取24。如果有j(j<=k)个球,C(j,k)+C(j-1,k)+...+C(1,k)+C(0,k)>=N+1。当j很大时，是不是直接可用二分法？
>

> > > > 2008/4/27 silwile <silw...@gmail.com>:

[杨堃]

     呵呵，可能我解释的不是很清楚，很多小细节没有说。

     因为，假设我们能得到最少的次数是T，因此，我们所希望的结果就是，对于每一层来说，如果是玻璃摔破的层的话，我们应该能在T次之内完成。ok，那如果是这样的话，先看一个简单的例子，如果我前一次放到X1上，玻璃没破，这之前检查了T1次，这一次我放到X2上，玻璃破了，我需要检查的最大次数是多少，那检查到的最大层次应该是X2-1，因为我们还剩1个球，所以只能从X1+1层，一直到X2-1层，因此，检查的次数应该是T1+1+X2-1-X1=T1+X2-X1<=T.

    有了这个常规公式，那么我们就可以往下做了。对于N层来说，最少次数是T，因此第一次放的地方最大是多少，带入公式T1=0,X1=0,X2=T,因此放在第T层，这就可以保证T层之内如果存在玻璃摔破的地方我们一定能在T次内找到，ok。接下来考虑的是T+1到N层，可以看到，这个场景是不是和第一次我们需要放的地方非常相似，只不过现在已经放过一次了，所以T1=1，因此，T1+X2-X1=1+X2-T<=T，X2=2T-1，因此，我们可以看到，对于2T-1层来说，我们能保证2T-1层内如果有玻璃摔破，能在T次内解决。后面推论的结果应该是一样的，我们可以看到，其实就是X2-X1<=T-T1，而对于T1来说，每次增加1次，能检查到的最大层次差从T到T-1到T-2。。最多可以到1.

   ok.如果能推导到了这个地方，我想答案应该就很了然了。最小的T次那就是满足T+T-1+T-2。。。+1（加到1 是表示最多能到1）>=N这个方程的最小T值。

    好了，如果2个玻璃的是这样解决的话，3个玻璃也是一样，只不过我们可以那2个玻璃去测试，那也就是每次可以检查的层次比放1个玻璃的大一倍，因此满足最小的T应该是2*(T+T-1+T-2...+1)>=N 这个方程的最小T值。

 

在08-4-28，Justin L <ice...@gmail.com> 写道：

[TeEmo]

因为我们假设的是最少需要T次，如果在T的位置上没有坏，那么就算是已经扔过一次，所以接下来，我们就只能给再扔T-1次玻璃球了。那么第二次扔球的位
置就应该是在第一次扔球的楼层上增加T-1层，这样才能够保证在T~T+T-1层以内的任何一层都能够在剩下的T-1次扔球中解决。
依此类推，我们得到下式：
T + (T-1) + (T-2) + ... + 1 >= 300 ===> T = 24

[Kicool]

先修正之前我化解的一个错误 ：C(2,k)+C(1,k)+C(0,k)>=N+1,化解(k+1)k/2>=N，过程不同，但最后的结果应该和大家
一样的。
分析杨堃同学的思路，他取的每次的位置，对应我树中根结点和最左边的叶结点的一条路径上的结点：T，T+T-1, T+T-1+T-2,...。应该注
意到，取树中的左分支，意味着上次实验成功，即可实验的球的个数没有变。但是，我们能实验的次数又变少了一次。这样取值，保证了，如果该次试验失败，用
剩下的最后一个球，可从这个区间的最底层，一次加一层的实验。举例来说，假如第一次在T的位置上实验成功，我们还有2个球，但可实验的次数变成T-1；
然后我们到T+T-1层做第2次实验，如果失败了，我们只有最后1个球，和T-2次可用的实验次数。最坏条件下（就是刚好在T+T-1层失败），我们必
须从T+1，T+2,...,到T+T-1-1一直实验上来（显然，在最后一个球的时候我们只能从低到高一层层实验），这样正好实验了T-2次。加上之
前的2次试验，总共T次。

杨堃同学的思路比我的思路直接多了。我的比较绕，但响应组内号召，还是把我的思维过程讲一下：

1）刚拿到这个题目，第一反应其实也是做二分法，可能是知识结构决定了，一想到这种条件下的优化，就是这个办法。如果不球最小，我们从第一层逐层实验，
总有解，其实，这应该是球数=1时，最小次数为N的结论。

2）当时也没想到，如果球数足够大（其实是只要大于等于Log（2，N）向上圆整）就可以放心的用二分法了，这是后来写出公式才想到的（见帖子回复‘轨
迹’）。

3）但是二分法在2球下显然是不行的，于是没招了，只好从N=1，N=2，N=3挨个想该怎么扔，想到N=6的时候，觉得和二分树有关，因为每个后续的
实验该选的策略，和本次试验成功与否有关，成功失败只有二个状态。
之后就是根据题目，想出一个扔的严格策略步骤，然后构造出这样二分树。

4）树是构造出来了，但怎么求之呢？想不出，觉得需要用到高深的数学知识~~~去吃饭先

5）在吃饭的时候，想到可以反过来求给出k层的一个“满”树能满足最大的N是多少，于是豁然开朗，用排列组合方法，得出:
C(2,k)+C(1,k)+C(0,k)>=N+1 有点小激动，把化解算错了，恰好结果也满足，BS自己一下～～

On 4月28日, 上午8时31分, Justin L <icer...@gmail.com> wrote:

[TeEmo]

考虑三个球，可以在两个球的基础上进行。
假设300层楼最少需要T次，那么我们知道第一次应该放在n<T>=T*(T+1)/2的位置上，这样才可以保证n<T>以内的任何一层都能在T次解
决-，ok。那么第一次扔球的位置，应该是从n<T>的楼层开始。那如果第一次在n<T>的位置上没有坏，那第二次应该在哪里呢？很简单，因为已经试了
一次，那么就必须保证位置能够在T-1次解决，即n<T>+n<T-1> = T*(T+1)/2 + T*(T-1)/2的楼层开始，其中
n<T-1> = (T-1)*T/2。这样就可以保证在n<T>到n<T>+n<T-1>之间的楼层都可以在剩下的T-1次解决。
依此类推，我们可以得到下式：
n<T> + n<T-1> + ... + n<1> = T*(T+1)/2 + (T-1)*T/2 + ... + 1*2/2 = T*(T
+1)*(T+2) / 6 >= 300 ====> T = 12。
所以考虑三个球的话，结果应该是12次。

观察这两个结果：
两个球：T*(T+1) / 2 = C(2, T+1)
三个球：T*(T+1)*(T+2) / 6 = C(3, T+2)
... ... ... ... ... ...
猜测：n个球的话，结果应该是 C(n, T+n-1)

这个结果就可以类比杨辉三角。


On 4月28日, 上午9时56分, "杨堃" <yangkun0...@gmail.com> wrote:

> 好了，如果2个玻璃的是这样解决的话，3个玻璃也是一样，只不过我们可以那2个玻璃去测试，那也就是每次可以检查的层次比放1个玻璃的大一倍，因此满足最小的T-应该是2*(T+T-1+T-2...+1)>=N
> 这个方程的最小T值。

[Justin L]

怎么又搞得那么复杂呢？ ：）

这样，说简单点：如果我们保证K次就可以查出来问题，那么第一次就可以在K层扔，破了，就需要扔第二个球，从1到K-1层，扔K-1次。如果没破，则需
要往K层以上测试。由于K层已经扔过一次了，则还剩下K-1次扔球机会。
自然，第一个不破，则重新扔第一个球（从K层往上数），为了保证最大只扔K次，只能扔到2K-1层上。

所以，此题重在归纳题意。就是确定一个扔球次数，最高能测试到多少层。

On 4月28日, 上午9时56分, "杨堃" <yangkun0...@gmail.com> wrote:

> 呵呵，可能我解释的不是很清楚，很多小细节没有说。
>
> 因为，假设我们能得到最少的次数是T，因此，我们所希望的结果就是，对于每一层来说，如果是玻璃摔破的层的话，我们应该能在T次之内完成。ok，那如果是这样的话，先看一个简单的例子，如果我前一次放到X1上，玻璃没破，这之前检查了T1次，这一次我放到X2上，玻璃破了，我需要检查的最大次数是多少，那检查到的最大层次应该是X2-1，因为我们还剩1个球，所以只能从X1+1层，一直到X2-1层，因此，检查的次数应该是T1+1+X2-1-X1=T1+X2-X1<=T.
>
> 有了这个常规公式，那么我们就可以往下做了。对于N层来说，最少次数是T，因此第一次放的地方最大是多少，带入公式T1=0,X1=0,X2=T,因此放在第T层，这就可以保证T层之内如果存在玻璃摔破的地方我们一定能在T次内找到，ok。接下来考虑的是T+1到N层，可以看到，这个场景是不是和第一次我们需要放的地方非常相似，只不过现在已经放过一次了，所以T1=1，因此，T1+X2-X1=1+X2-T<=T，X2=2T-1，因此，我们可以看到，对于2T-1层来说，我们能保证2T-1层内如果有玻璃摔破，能在T次内解决。后面推论的结果应该是一样的，我们可以看到，其实就是X2-X1<=T-T1，而对于T1来说，每次增加1次，能检查到的最大层次差从T到T-1到T-2。。最多可以到1.
> ok.如果能推导到了这个地方，我想答案应该就很了然了。最小的T次那就是满足T+T-1+T-2。。。+1（加到1
> 是表示最多能到1）>=N这个方程的最小T值。
>
> 好了，如果2个玻璃的是这样解决的话，3个玻璃也是一样，只不过我们可以那2个玻璃去测试，那也就是每次可以检查的层次比放1个玻璃的大一倍，因此满足最小的T应该是2*(T+T-1+T-2...+1)>=N
> 这个方程的最小T值。
>

> 在08-4-28，Justin L <icer...@gmail.com> 写道：

[Justin L]

从两个球到三个球，没有多大跨度，如果两个球的求解方案想清楚了，往上推一步，就是：

两个球的情况：两个球扔T次，可以测试完K层。（目前大家都有最终答案了）
第三个球，按照上面的方案，就直接从K+1层开始扔，只不过三个球扔的次数是T+1次(设置一个变量T ' = T + 1)。破了，就扔剩下的两个
球，扔T次就可以扔遍K层了。如果没破。就要从K+2层往上数了。就相当于K+2往上的L个层，要保证扔T次可以扔遍T层。至于这个L是多少呢，其实就
是根据两个球扔的次数来决定的。

设最后所求的次数为T次。那么第三个球第一次扔的高度，是通过2个球扔T次所能扔遍的高度。第三个球扔第二次的高度（应该是在第一次扔的高度上加上这个
高度），是通过2个球扔T-1此所能扔遍的高度。以此类推。

[Justin L]

[Justin L]

工作后没太多时间接触算法当中和数学关系紧密这些东西，进入到电信行业，项目当中用得多的还是hash。
第一次看到这个扔球的题，是在程序员杂志上。说实话，那篇文章写得是相当的不负责，搞得像在宣扬神秘主义。
杂志编辑怎么会把那篇文章选进去呢，说得不好听点，扯淡啊。
或多或少我也受到文章误导。第一次我的想法是用求概率，然后确定第一个球在第几层扔比较好。

直到后来发现，其实受误导得肯定不在少数。
说到搞理论，其实工作中实际运用理论的机会不多。但是研究理论也就是练内力，工作中就会少犯错误，高质量。

[部洪波]

第3个题目，我首先就在想应该从第1楼开始测试，如果没有破碎就到第2楼，如果还没有破碎就到第3楼，依次进行。但是肯定在到达某层的时候会破碎。然后我又想如果我从最顶层开始，即第300层，向第299层扔玻璃珠，如果没有碎，那么就可以从299层向297层扔玻璃珠，如果还是没有破碎，那么就从297层向294层扔玻璃珠，依次进行。这样的方法，每扔依次，楼层间距就加1 ，这样当某一次玻璃珠落到地面时（假设玻璃珠没有破），这一次的楼层间距是多少呢？
1+2+3+...+n>=300  
即：n(n+1)/2 >=300

[alai]

服了你了，这种答案也能写出来。

2008/4/30 部洪波 <buho...@gmail.com>:

[hayate]

转载一个分析

 

发信人: einstain (单身汉：）), 信区: IQDoor
标  题: 仍鸡蛋（未明动脑筋乐园版斑竹给的解答）
发信站: BBS 水木清华站 (Wed Dec  3 13:46:10 2003), 转信

网址：http://tryyourbest.bdwm.net/

问题

某种蛋，从某高度扔下会碎，而从低于该高度扔都不会碎（不管扔多少次），从高于该高
度扔都会碎。现有4个这种蛋，要在1000层高的楼上做试验，测出第几层高度会碎，而低
于该层则不会碎。问：最少需扔多少次，保证能测出？（最后蛋碎不碎没关系）
【补充：题目并不假设一定在某个小于等于1000层的楼往下仍鸡蛋会碎】

解答
发信人: fireblbl (fireblbl), 信区: TryYourBest
标  题: 扔鸡蛋问题的严格答案
发信站: 北大未名站 (2003年12月03日13:08:41 星期三), 转信

 有k个鸡蛋，扔n次,如果楼数最大为m记为F(n,k)
我们一定可以判断从1、2……m楼扔下去是否碎裂。
而不能判断从1、2……(m+1)楼扔下去是否碎裂。
则显然有：
F(n+1,k+1)=F(n,k)+F(n-1,k)+……+F(1,k)+F(0,k)+n+1;
关键是这个式子的理由。 你的在这儿有问题。
理由：
 第一次扔鸡蛋最多在F(n,k)+1层，如果比这个还高，如果鸡蛋碎了，就无法确切判断
鸡蛋在那一层碎了。
挨下来考虑如果没有弄碎的话，我们要考虑第二次鸡蛋最多在那一层扔。用上面这个办法
…………一直下去得到上面递退式。最后我想问问最后n+1这项是怎么来的。
这个理由就是证明。

sq你的结论比我这个小。
你可以计算一下(用你、我的办法)F(5,3)

这个问题有一些实际背试验的次数就是时间代价，鸡蛋个数就是金钱代价。目标是要尽可
能的精确。
这个东西我本来希望大家自己去理解，来补齐上面那段说明。

有F(0, 任意)=0;可得

F(n,1)=n;
其它的就 不好求确切的表达式
利用F(n,n)=F(n,n+1)=……=F(n,无穷 )=(2^n)-1
但我们用数归易证：F(n,k)>=C(n,k)

 

【 在 SQ (12月のこんな夜 予期せぬ愛がうまれる……) 的大作中提到: 】
: 呵呵
: 我的更全面，注意当m<=n时
: f(m,n)=c(m,1)+...+c(m,m)=2^m-1

 

根据那个递归式，其实可以算出一个通项，虽然不是closed form

 

[alai]

F(n+1,k+1)=F(n,k)+F(n-1,k)+……+F(1,k)+F(0,k)+n+1
应该写成这样就更清楚了：
F(n+1,k+1)=[F(n,k)+1]+[F(n-1,k)+1]+……+[F(1,k)+1]+1
原式中的n+1项，其实应该分解为n+1个1，分别加到前面n+1个F(...)上，而且F(0,k)明显等于0，可以去掉。这样解释LS应该明白了吧。

2008/5/1 hayate <haya...@gmail.com>:

[alai]

另一个更简单的递推式是：
F(n+1,k+1) = F(n,k+1) + F(n,k) + 1
其意义也很简单，k+1个球，可以扔n+1次，在适当的楼层扔了一次后，可能破了，也可能没破，如果破了，就可以在这个楼层以下继续尝试，这时还有k个球n次机会，所以可以完成尝试的楼层数为F(n,k)；如果第一次扔球破了，则可以从这个楼层以上继续尝试，这时还有k+1个球n次机会，所以可以完成浓度的楼层数为F(n,k+1)，再加上第一次扔球的那一层楼，总楼层数为
F(n,k+1) + F(n,k) + 1
如果n<k，则显然F(n,k)=F(n,n)=F(n-1,n)+F(n-1,n-1)+1=2*F(n-1,n-1)+1，容易推得2^n-1，这时其实就是二分法了。

2008/5/1 alai <ala...@gmail.com>:

[silwile]

2008/5/1 alai <ala...@gmail.com>:

另一个更简单的递推式是：
F(n+1,k+1) = F(n,k+1) + F(n,k) + 1
其意义也很简单，k+1个球，可以扔n+1次，在适当的楼层扔了一次后，可能破了，也可能没破，如果破了，就可以在这个楼层以下继续尝试，这时还有k个球n次机会，所以可以完成尝试的楼层数为F(n,k)；如果第一次扔球破了，则可以从这个楼层以上继续尝试，这时还有k+1

                                                                                                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                                                                                                    应该是"如果没有扔破"吧，笔误 -_-

[silwile]

关于第二题讨论不是很多嘛，看来大家都在讨论扔鸡蛋的问题了:)

其实，第二题也是蛮好玩的。简单地说几点我做这个题时候的一些过程吧。先试了几个特例，x,y,z数字较小的情况下。虽然没有一下子发现什么好玩的insights。但至少对问题本身的理解加深了。过了一会儿，转机来个，在观察这些例子的时候，我发现了一个关键的不变量：即无论x,y,z三者怎么变化，他们mod 3 的余数的变化始终是同步的。即先考虑最小粒度的变化，即两个不同颜色的球转换成了两个另外颜色的球。这是x,y的减少了1,而z的值则增加了2，而在mod3的运算下（当时，我也不知道是怎样想到mod3的运算的，反正i see it ~_~），减少了1与增加了2其实是一样的。注意到了这一点之后，是倒着想这个问题，如果最后盒子里面所有的球都是一种颜色的话，那么最后一步变化前肯定是有两种颜色球的数量相同（其实，最后只有一种颜色的时候出现的也是这种情况，只不过它们两者都是0而已）。而这个配置的Mod3肯定也会出现两个数相同。也就是说，mod3后出现两个数相同是完成题目要求的清一色的球的必要条件。而171，172，173不满足这样的必要条件，所以肯定不存在要出现题目所要求的清一色的转换算法。

BTW:稍微在讨论一下，我们还可以知道这个条件也是充分的。

[kicool]

在变中找不变......

2008/5/1 silwile <sil...@gmail.com>: