扔鸡蛋问题

mathe · 发表于 2018-3-30 17:31:59

发现一个例外，第一次选择第一层破裂时，还需要0次而不是1/2次
计算结果应该第一次在第14层抛下（使用sheng的模型而且假设均匀分布）
下面是计算的概率a[n]
[1, 5/3, 2, 23/10, 31/12, 39/14, 3, 19/6, 67/20, 7/2, 11/3, 99/26, 55/14, 61/15, 67/16, 147/34, 40/9, 173/38, 93/20, 100/21, 107/22, 229/46, 61/12, 259/50, 137/26, 289/54, 305/56, 321/58, 169/30, 355/62, 93/16, 389/66, 203/34, 423/70, 49/8, 459/74, 239/38, 497/78, 129/20, 535/82, 277/42, 573/86, 74/11, 34/5, 158/23, 653/94, 337/48, 695/98, 179/25, 737/102, 379/52, 779/106, 200/27, 411/55, 211/28, 289/38, 445/58, 913/118, 39/5, 959/122, 491/62, 335/42, 257/32, 1051/130, 1075/132, 1099/134, 281/34, 383/46, 587/70, 1199/142, 17/2, 1249/146, 637/74, 433/50, 331/38, 1349/154, 1375/156, 1401/158, 357/40, 485/54, 741/82, 1509/166, 64/7, 1563/170, 795/86, 539/58, 411/44, 1671/178, 283/30, 863/91, 877/92, 1783/186, 453/47, 1841/190, 935/96, 1899/194, 482/49, 1957/198, 993/100, 2015/202]
而对于k个有效楼层，我们第一次应该选择的楼层b(k)为
[1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13]
比如上面给出b(98)=13，所以对于100层（98个有效楼层），应该选择第14层

zeroieme · 发表于 2018-3-30 19:23:30

mathe 发表于 2018-3-30 17:11
首先我们需要考虑有多少个有效楼层，比如sheng的理解方案下就只有98个有效楼层，1楼和100楼均不需要检测。 ...

两个问题，100楼不能排除检测，还有如果使用先验知识，越高破碎的概率越大比等概率更合理。不妨设作跟高度成正比。

mathe · 发表于 2018-3-30 19:33:45

等概率是指正好在某个高度摔碎的概率相等

zeroieme · 发表于 2018-3-30 19:54:30

某个高度摔碎应当是固定的——用平行宇宙假设吧。有99个平行宇宙，每个宇宙里鸡蛋到$N_i$楼以上必然会摔碎。
我们进入一个未知的宇宙，用两鸡蛋测定到底是进了那个宇宙。
概率是进入不同宇宙的概率。

wayne · 发表于 2018-3-31 09:44:14

尝试构造一个数列$a{n}$，该数列就是最佳的选择尝试扔鸡蛋的楼层数序列。任选一个楼层，如果破了，就从该项的前一项开始往上逐一的选择楼层尝试。如果没破，没关系，该数列的特点就是保证代价相同【每判断一次，浪费掉一次尝试机会】，即$a_n-a_{n-1}= a_{n-1}-a_{n-2}-1 = a_1-(n-1)$。

现在来分析数列的特点。这是一个二阶等差数列，设总楼层是$m$, 容易得到，$a_n = n a_1 - 1/2 (n-1)n$, $1<=n<a_1$, 最后一项 $a_n$,满足关系：$a_n<m<a_{n+1}$, 于是 $1<=n<\frac{1}{2} \sqrt{8 m+1}-\frac{1}{2} $,即 $1<=n<=floor(\sqrt{2 m}-\frac{1}{2}} $
================
计算得知，该二阶等差数列的首项$a_1 = floor( \sqrt{2 m}-\frac{1}{2}) +1$

Table[{m,aa=First[Sort[{a,n}/.List@ToRules[Reduce[1<=n<=a&&1<a&&n a -n (n-1)/2<m&&(n+1)a -n (n+1)/2>=m,{n,a},Integers]]]],Table[k aa[[1]] -k (k-1)/2,{k,aa[[2]]}]},{m,3,100}]//Column

复制代码

{3,{2,1},{2}}
{4,{3,1},{3}}
{5,{3,1},{3}}
{6,{3,2},{3,5}}
{7,{4,1},{4}}
{8,{4,2},{4,7}}
{9,{4,2},{4,7}}
{10,{4,3},{4,7,9}}
{11,{5,2},{5,9}}
{12,{5,2},{5,9}}
{13,{5,3},{5,9,12}}
{14,{5,3},{5,9,12}}
{15,{5,4},{5,9,12,14}}
{16,{6,3},{6,11,15}}
{17,{6,3},{6,11,15}}
{18,{6,3},{6,11,15}}
{19,{6,4},{6,11,15,18}}
{20,{6,4},{6,11,15,18}}
{21,{6,5},{6,11,15,18,20}}
{22,{7,3},{7,13,18}}
{23,{7,4},{7,13,18,22}}
{24,{7,4},{7,13,18,22}}
{25,{7,4},{7,13,18,22}}
{26,{7,5},{7,13,18,22,25}}
{27,{7,5},{7,13,18,22,25}}
{28,{7,6},{7,13,18,22,25,27}}
{29,{8,4},{8,15,21,26}}
{30,{8,4},{8,15,21,26}}
{31,{8,5},{8,15,21,26,30}}
{32,{8,5},{8,15,21,26,30}}
{33,{8,5},{8,15,21,26,30}}
{34,{8,6},{8,15,21,26,30,33}}
{35,{8,6},{8,15,21,26,30,33}}
{36,{8,7},{8,15,21,26,30,33,35}}
{37,{9,5},{9,17,24,30,35}}
{38,{9,5},{9,17,24,30,35}}
{39,{9,5},{9,17,24,30,35}}
{40,{9,6},{9,17,24,30,35,39}}
{41,{9,6},{9,17,24,30,35,39}}
{42,{9,6},{9,17,24,30,35,39}}
{43,{9,7},{9,17,24,30,35,39,42}}
{44,{9,7},{9,17,24,30,35,39,42}}
{45,{9,8},{9,17,24,30,35,39,42,44}}
{46,{10,6},{10,19,27,34,40,45}}
{47,{10,6},{10,19,27,34,40,45}}
{48,{10,6},{10,19,27,34,40,45}}
{49,{10,6},{10,19,27,34,40,45}}
{50,{10,7},{10,19,27,34,40,45,49}}
{51,{10,7},{10,19,27,34,40,45,49}}
{52,{10,7},{10,19,27,34,40,45,49}}
{53,{10,8},{10,19,27,34,40,45,49,52}}
{54,{10,8},{10,19,27,34,40,45,49,52}}
{55,{10,9},{10,19,27,34,40,45,49,52,54}}
{56,{11,6},{11,21,30,38,45,51}}
{57,{11,7},{11,21,30,38,45,51,56}}
{58,{11,7},{11,21,30,38,45,51,56}}
{59,{11,7},{11,21,30,38,45,51,56}}
{60,{11,7},{11,21,30,38,45,51,56}}
{61,{11,8},{11,21,30,38,45,51,56,60}}
{62,{11,8},{11,21,30,38,45,51,56,60}}
{63,{11,8},{11,21,30,38,45,51,56,60}}
{64,{11,9},{11,21,30,38,45,51,56,60,63}}
{65,{11,9},{11,21,30,38,45,51,56,60,63}}
{66,{11,10},{11,21,30,38,45,51,56,60,63,65}}
{67,{12,7},{12,23,33,42,50,57,63}}
{68,{12,7},{12,23,33,42,50,57,63}}
{69,{12,8},{12,23,33,42,50,57,63,68}}
{70,{12,8},{12,23,33,42,50,57,63,68}}
{71,{12,8},{12,23,33,42,50,57,63,68}}
{72,{12,8},{12,23,33,42,50,57,63,68}}
{73,{12,9},{12,23,33,42,50,57,63,68,72}}
{74,{12,9},{12,23,33,42,50,57,63,68,72}}
{75,{12,9},{12,23,33,42,50,57,63,68,72}}
{76,{12,10},{12,23,33,42,50,57,63,68,72,75}}
{77,{12,10},{12,23,33,42,50,57,63,68,72,75}}
{78,{12,11},{12,23,33,42,50,57,63,68,72,75,77}}
{79,{13,8},{13,25,36,46,55,63,70,76}}
{80,{13,8},{13,25,36,46,55,63,70,76}}
{81,{13,8},{13,25,36,46,55,63,70,76}}
{82,{13,9},{13,25,36,46,55,63,70,76,81}}
{83,{13,9},{13,25,36,46,55,63,70,76,81}}
{84,{13,9},{13,25,36,46,55,63,70,76,81}}
{85,{13,9},{13,25,36,46,55,63,70,76,81}}
{86,{13,10},{13,25,36,46,55,63,70,76,81,85}}
{87,{13,10},{13,25,36,46,55,63,70,76,81,85}}
{88,{13,10},{13,25,36,46,55,63,70,76,81,85}}
{89,{13,11},{13,25,36,46,55,63,70,76,81,85,88}}
{90,{13,11},{13,25,36,46,55,63,70,76,81,85,88}}
{91,{13,12},{13,25,36,46,55,63,70,76,81,85,88,90}}
{92,{14,9},{14,27,39,50,60,69,77,84,90}}
{93,{14,9},{14,27,39,50,60,69,77,84,90}}
{94,{14,9},{14,27,39,50,60,69,77,84,90}}
{95,{14,9},{14,27,39,50,60,69,77,84,90}}
{96,{14,10},{14,27,39,50,60,69,77,84,90,95}}
{97,{14,10},{14,27,39,50,60,69,77,84,90,95}}
{98,{14,10},{14,27,39,50,60,69,77,84,90,95}}
{99,{14,10},{14,27,39,50,60,69,77,84,90,95}}
{100,{14,11},{14,27,39,50,60,69,77,84,90,95,99}}

wayne · 发表于 2018-3-31 10:10:18

同理，对于$n$个鸡蛋，猜测应该是$n$阶等差数列。这个题目前天在咱们论坛的QQ群讨论过，受到 @qianyb 徒手构造数列的启发

二个鸡蛋的情况，楼层数列的通项是 $a_n = C_n^1 a_1- C_n^2$
三个鸡蛋的情况，楼层数列的通项是 $a_n = C_n^1 a_1 + d C_n^2  - C_n^3 $
四个鸡蛋的情况，楼层数列的通项是 $a_n = C_n^1 a_1 + d_1 C_n^2  +d_2 C_n^3 -C_n^4$
...

对于100层，三个鸡蛋。楼层数列通项是$a_n = 5C_n^1 + 4 C_n^2  - C_n^3 $，即 ${5, 14, 26, 40, 55, 70, 84, 96}$

王守恩 · 发表于 2018-3-31 14:49:41

本帖最后由王守恩于 2018-3-31 20:24 编辑

wayne 发表于 2018-3-31 09:44
尝试构造一个数列$a{n}$，该数列就是最佳的选择尝试扔鸡蛋的楼层数序列。任选一个楼层，如果破了，就从该项 ...

1——100层的大楼，对每层来说：鸡蛋都有破碎与完整两种可能。
我们对每层都作一个独立的试验，共需要作100个独立的试验。
第1列：执行的是4#的试验方案，100个独立的试验共作了1881次试验。
第2列：执行的是15#的试验方案，100个独立的试验共作了1035次试验。
很明显，15#的试验方案要优于4#的试验方案。
                  第1列  第2列
第01层开始碎 02    02
第02层开始碎 03    03
第03层开始碎 04    04
第04层开始碎 05    05
第05层开始碎 06    06
第06层开始碎 07    07
第07层开始碎 08    08
第08层开始碎 09    09
第09层开始碎 10    10
第10层开始碎 11    11
第11层开始碎 12    12
第12层开始碎 13    13
第13层开始碎 14    14
第14层开始碎 15    14=1
第15层开始碎 16    03
第16层开始碎 17    04
第17层开始碎 18    05
第18层开始碎 19    06
第19层开始碎 20    07
第20层开始碎 21    08
第21层开始碎 22    09
第22层开始碎 23    10
第23层开始碎 24    11
第24层开始碎 25    12
第25层开始碎 26    13
第26层开始碎 27    14
第27层开始碎 28    14=2
第28层开始碎 29    04
第29层开始碎 30    05
第30层开始碎 31    06
第31层开始碎 32    07
第32层开始碎 33    08
第33层开始碎 34    09
第34层开始碎 35    10
第35层开始碎 36    11
第36层开始碎 37    12
第37层开始碎 38    13
第38层开始碎 39    14
第39层开始碎 40    14=3
第40层开始碎 41    05
第41层开始碎 42    06
第42层开始碎 43    07
第43层开始碎 44    08
第44层开始碎 45    09
第45层开始碎 46    10
第46层开始碎 47    11
第47层开始碎 48    12
第48层开始碎 49    13
第49层开始碎 50    14
第50层开始碎 50=1  14=4
第51层开始碎 03    06
第52层开始碎 04    07
第53层开始碎 05    08
第54层开始碎 06    09
第55层开始碎 07    10
第56层开始碎 08    11
第57层开始碎 09    12
第58层开始碎 10    13
第59层开始碎 11    14
第60层开始碎 12    14=5
第61层开始碎 13    07
第62层开始碎 14    08
第63层开始碎 15    09
第64层开始碎 16    10
第65层开始碎 17    11
第66层开始碎 18    12
第67层开始碎 19    13
第68层开始碎 20    14
第69层开始碎 21    14=6
第70层开始碎 22    08
第71层开始碎 23    09
第72层开始碎 24    10
第73层开始碎 25    11
第74层开始碎 26    12
第75层开始碎 26=2  13
第76层开始碎 04    14
第77层开始碎 05    14=7
第78层开始碎 06    09
第79层开始碎 07    10
第80层开始碎 08    11
第81层开始碎 09    12
第82层开始碎 10    13
第83层开始碎 11    14
第84层开始碎 12    14=8
第85层开始碎 13    10
第86层开始碎 14    11
第87层开始碎 14=3  12
第88层开始碎 05    13
第89层开始碎 06    14
第90层开始碎 07    14=9
第91层开始碎 08    11
第92层开始碎 09    12
第93层开始碎 10    13
第94层开始碎 10=4  14
第95层开始碎 06    14=10
第96层开始碎 07    12
第97层开始碎 07=5  13
第98层开始碎 07    14
第99层开始碎 07=6 14=11
第100层开始碎 07=7 12=12

kastin · 发表于 2018-3-31 18:35:40

开始理解错了，以为最多丢鸡蛋个数次，实际上是最少那么多次。
这样的话，对于任意一个鸡蛋从`k`楼丢下，如果没有破碎，那么意味着可以将底部的 `k` 层砍掉，变成 `100-k` 层楼的丢鸡蛋问题；如果破碎，意味着变成 `k` 层楼丢鸡蛋问题。

zeroieme · 发表于 2018-4-1 22:15:11

本帖最后由 zeroieme 于 2018-4-1 22:23 编辑

建立一个期望值公式
$\sum _{i=1}^{100} p_i*G(F,i)$
F为制定的测定计划。G为用F计划，并且临界楼层在$i$楼时的测定次数。
$p_i$为临界楼层在$i$楼的几率，作为先验知识。
@mathe ，你认为： $p_1 =0$与$p_{100}=0$，其他$p_2=p_3=p_4=p_5=p_6$……么
我觉得$p_i=s-(i-1)d$，d是递减系数。

mathe · 发表于 2018-4-1 22:45:49

p_1是否为0并不影响解题，只是层数相当于改变了1.其余楼层是线性还是均匀，这个你应该理解一下密度函数和分布函数的区别。
你这思路有点类似重物会比轻物落得更快的想法

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 扔鸡蛋问题

点评

点评

点评