一道老智商题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>DataSciences - 数据科学

一道老智商题

一道老智商题# DataSciences - 数据科学

l*k2015-07-28 07:07

1 楼

100层的一个楼，有一个固定的楼层，在这个高度之上往下扔一个牌子的杯子，杯子会
碎，这个楼层之下，扔无数次杯子也会毫发无伤。prior是阈值楼层等概率分布在这100
层中的任意一层。
现在给两个这样的杯子，要求“找到这个阈值楼层”的最佳策略。这个策略要求在摔碎
两个杯子之后确定阈值楼层，只给楼层范围算失败。所谓最佳，是指照次策略，确定楼
层的平均次数最小。同求这个策略下，最差的情况，几次能够确定阈值楼层。
我想到的解法用到了拉格朗日乘子。有不用乘子的解法么？

d*e2015-07-28 07:07

2 楼

这个是dynamic programming的题。
策略应该是第一个杯子按搜索范围的proportion来找，如果成功，这个层数之下的范围
就不再需要搜索了，继续向楼上搜索。一旦第一个杯子碎了，第二个杯子就是在第一个
杯子的最后两次测试的楼层之间从小到大逐个测试。
最后求expectation，然后找一个极小值。
如果近似认为是连续优化的话，就是个求根问题。如果是离散优化，需要有四舍五入的
问题。但是都不应该用到Lagrangian Multiplier，哪里来的等式约束？

100

【在 l********k 的大作中提到】

: 100层的一个楼，有一个固定的楼层，在这个高度之上往下扔一个牌子的杯子，杯子会
: 碎，这个楼层之下，扔无数次杯子也会毫发无伤。prior是阈值楼层等概率分布在这100
: 层中的任意一层。
: 现在给两个这样的杯子，要求“找到这个阈值楼层”的最佳策略。这个策略要求在摔碎
: 两个杯子之后确定阈值楼层，只给楼层范围算失败。所谓最佳，是指照次策略，确定楼
: 层的平均次数最小。同求这个策略下，最差的情况，几次能够确定阈值楼层。
: 我想到的解法用到了拉格朗日乘子。有不用乘子的解法么？

l*k2015-07-28 07:07

3 楼

你说的策略大方向是对的，第二个杯子的策略很简单，从上一次没摔碎的地方开始逐层
试验。关键是第一个杯子大范围搜索的区间怎么优化。

【在 d******e 的大作中提到】

: 这个是dynamic programming的题。
: 策略应该是第一个杯子按搜索范围的proportion来找，如果成功，这个层数之下的范围
: 就不再需要搜索了，继续向楼上搜索。一旦第一个杯子碎了，第二个杯子就是在第一个
: 杯子的最后两次测试的楼层之间从小到大逐个测试。
: 最后求expectation，然后找一个极小值。
: 如果近似认为是连续优化的话，就是个求根问题。如果是离散优化，需要有四舍五入的
: 问题。但是都不应该用到Lagrangian Multiplier，哪里来的等式约束？
:
: 100

z*e2015-07-28 07:07

4 楼

最差情况下careercup里面的解是
Goal: Create a system for dropping Egg1 so that the most drops required is
consistent, whether Egg1 breaks on the first drop or the last drop 1 A
perfectly load balanced system would be one in which Drops of Egg1 + Drops
of Egg2 is always the same, regardless of where Egg1 broke 2 For that to be
the case, since each drop of Egg1 takes one more step, Egg2 is allowed one
fewer step 3 We must, therefore, reduce the number of steps potentially
required by Egg2 by one drop each time For example, if Egg1 is dropped on
Floor 20 and then Floor 30, Egg2 is potentially required to take 9 steps
When we drop Egg1 again, we must reduce potential Egg2 steps to only 8 eg,
we must drop Egg1 at floor 39 4 We know, therefore, Egg1 must start at
Floor X, then go up by X-1 floors, then X-2, …, until it gets to 100 5
Solve for X+(X-1)+(X-2)+…+1 = 100 X(X+1)/2 = 100 -> X = 14 We go to Floor
14, then 27, then 39, … This takes 14 steps maximum

b*m2015-07-28 07:07

5 楼

这结论应该是对的。分析的不对。次数是期望，不见得是整数。
假设楼有N层，从N=3,4,5...开始算几个就发现规律。x(x+1)/2=N

be
one
,

【在 z*********e 的大作中提到】

: 最差情况下careercup里面的解是
: Goal: Create a system for dropping Egg1 so that the most drops required is
: consistent, whether Egg1 breaks on the first drop or the last drop 1 A
: perfectly load balanced system would be one in which Drops of Egg1 + Drops
: of Egg2 is always the same, regardless of where Egg1 broke 2 For that to be
: the case, since each drop of Egg1 takes one more step, Egg2 is allowed one
: fewer step 3 We must, therefore, reduce the number of steps potentially
: required by Egg2 by one drop each time For example, if Egg1 is dropped on
: Floor 20 and then Floor 30, Egg2 is potentially required to take 9 steps
: When we drop Egg1 again, we must reduce potential Egg2 steps to only 8 eg,

l*k2015-07-28 07:07

6 楼

这个解释很直观。比乘子法出结论要快。
设最佳策略下，第一个杯子跨越的楼层数为N1, N2, .... Nn，n待定。约束条件为
N1+N2+... +Nn = 100. 先假定Ni可以不是整数。杯子在第i个区间碎的概率为Ni/100，
用第一个杯子确定是这个区间碎之前，需要爬楼i次，之后用第二个杯子逐层试验，又
需要平均爬楼Ni/2次。所以平均下来总的爬楼次数为：
F1 = N1/100*(1+N1/2) + N2/100*(1+N2/2) + ... + Nn/100*(1+Nn/2)
约束条件
sum_i^n Ni = 100
改写成
F2 = N1+N2+...+Nn-100
定义 G = F1 - lambda*F2
拉格郎日乘子法：
partial G / partial Ni = 0
partial G / partial lambda = 0
能推出来Ni = 100lambda - i
也就是说，最佳策略下，每个区间层数递减1，和直观解释结论一样。

be
one
,

【在 z*********e 的大作中提到】

b*m2015-07-28 07:07

7 楼

这个期望不太对，拉掉了一些东西。还应该有一项是和n相关的。
F1 = N1/100*(1+N1/2) + N2/100*(1+N2/2) + ... + Nn/100*(1+Nn/2)
不然最小化F1等价于最小化N1^2+N2^2+...+Nn^2，显然在N1=N2=...Nn=1时候有最小解。

【在 l********k 的大作中提到】

: 这个解释很直观。比乘子法出结论要快。
: 设最佳策略下，第一个杯子跨越的楼层数为N1, N2, .... Nn，n待定。约束条件为
: N1+N2+... +Nn = 100. 先假定Ni可以不是整数。杯子在第i个区间碎的概率为Ni/100，
: 用第一个杯子确定是这个区间碎之前，需要爬楼i次，之后用第二个杯子逐层试验，又
: 需要平均爬楼Ni/2次。所以平均下来总的爬楼次数为：
: F1 = N1/100*(1+N1/2) + N2/100*(1+N2/2) + ... + Nn/100*(1+Nn/2)
: 约束条件
: sum_i^n Ni = 100
: 改写成
: F2 = N1+N2+...+Nn-100

l*k2015-07-28 07:07

8 楼

不好意思，copy paste的时候搞错了，F1的表达式应该是
F1 = N1/100*(1+N1/2) + N2/100*(2+N2/2) + ... + Nn/100*(n+Nn/2)
而且当n过大的时候，Ni会是负的，这也限制了n的范围。

解。

【在 b******m 的大作中提到】

: 这个期望不太对，拉掉了一些东西。还应该有一项是和n相关的。
: F1 = N1/100*(1+N1/2) + N2/100*(1+N2/2) + ... + Nn/100*(1+Nn/2)
: 不然最小化F1等价于最小化N1^2+N2^2+...+Nn^2，显然在N1=N2=...Nn=1时候有最小解。

d*e2015-07-28 07:07

9 楼

因为知道楼层是均匀分布，每次选的比例一定是固定的。
换句话说，如果确定这个楼层在［a,b］之间，那么选择的测试楼层就是a＋比例＊(b-a
)。
因为given楼层在[a,b]之间，楼层的conditional distribution是一个[a,b]上的均匀
分布。
这就是dynamic programming的题。
BTW：dynamic programming都可以有等价的优化问题形式，但这些优化并没有gain
insight。

【在 l********k 的大作中提到】

: 不好意思，copy paste的时候搞错了，F1的表达式应该是
: F1 = N1/100*(1+N1/2) + N2/100*(2+N2/2) + ... + Nn/100*(n+Nn/2)
: 而且当n过大的时候，Ni会是负的，这也限制了n的范围。
:
: 解。