魔方吧·中文魔方俱乐部

标题: 选中最大数的策略 [打印本页]

作者: lulijie 时间: 2009-2-28 23:35:19 标题: 选中最大数的策略

tiawing的那个关于策略的帖子，由于涉及到影响不好的东西，版主强烈要求修改，我就代tiawing修改成本贴，原著者仍归属tiawing。并把一些结论一并发表，有些虽然经电脑证实非常吻合事实，但未经证明。但因为结论非常出人意料，显示了数学的奇妙，所以公布出来，供大家分享。若有人能证明之，希望能不惜笔墨。则不胜欣喜。
---------------------------------------------------------------------------------------------------------------
有m个实数，两两不等，每次只显示一个数给你看，你可以选择获取它或放过它看下一个数。你的目标是得到最大的数。
那么如何安排策略，才能使得获取最大数的概率最高？
策略（N)  ：放过前面的N-1个数，从第N个数开始，若与前面的所有数相比是最大的，就选择该数，否则放过，看下一个数，一直到所看的数与前面的所有数相比是最大的为止，选择该数。若看到了最后一个数，就只能选择最后一个。

那么：
策略（N) 获取最大数的概率P(N) =(N-1)/m * ∑ 1/i （ ∑中的 i 从N-1到 m-1）    N>1
                                             P(N) =1/m                                                                   N=1
假设M1和M2是  最接近 (m+1)/e  的两个整数，M1<M2                   其中e为自然对数，=2.718281828……
那么结论1：使得概率P最大的N值必等于M1或M2。
         结论2：m趋向于无穷大时，P(M1+1) 或P(M2+1)的极限等于1/e 。
                     也就是说m很大时，最优策略获取最大数的概率等于1/e。
---------------------------------------------------------------------------------------------------
11#已经证明：假设M1和M2是  最接近 m/e  的两个整数，M1<M2 ，结论1成立。
  所以绿字部分 (m+1)/e 修改为m/e为妥当。若不改的话是否成立还有待证明。
                        M1或M2 应该为  M1+1或M2+1 即 int(m/e)+1 或 int(m/e)+2
         或者用n表示放过的数，即n=N-1，    结论1也可表示为：    使得概率P最大的n值必等于M1或M2。
------------------------------------------------------------------------------
最终结论应该是如下：
假设M2是  比 m/e  大的第一个整数，即M2 =int(m/e)  +1                其中e为自然对数，=2.718281828……
那么结论1：使得概率P最大的N值必等于M2或M2+1。
               或者表示为  使得概率P最大的n值必等于M2或M2-1。       n=N-1 表示放过的数
         结论2：m趋向于无穷大时，P(M2) 或P(M2+1)的极限等于1/e 。
                     也就是说m很大时，最优策略获取最大数的概率等于1/e。
----------------------------------------------------------------------------------------------
      上述有些乱，我把题目，求证的结论，以及证明的过程，全部一起集中发在14楼中。

[ 本帖最后由 lulijie 于 2009-3-2 20:57 编辑 ]

作者: R'cube 时间: 2009-3-1 00:04:06

沙发没人要我先拿下了~~~~~~~

作者: lulijie 时间: 2009-3-1 01:01:22

使得概率P最大的N值可以用公式计算：
N=int[(m+1)/e] +1 公式算出的结果与正确值大部分都一致，偶尔有少数比正确值大1。

从m=3至10000中，公式与正确值不一致的总数有519个：只占5%左右。
以下为公式与正确值不一致的m值
10，29，48，67，86，97，116，135，154，173，192，203，222，241，260，279，309，328，347，366，
385，396，415，434，453，472，502，521，540，559，578，589，608，627，646，665，695，714，733，
752，771，782，801，820，839，858，888，907，926，945，964，975，994，1013，1032，1051，1081，
1100，1119，1138，1157，1168，1187，1206，1225，1244，1274，1293，1312，1331，1350，1361，1380，
1399，1418，1437，1456，1467，1486，1505，1524，1543，1573，1592，1611，1630，1649，1660，1679，
1698，1717，1736，1766，1785，1804，1823，1842，1853，1872，1891，1910，1929，1959，1978，1997，
2016，2035，2046，2065，2084，2103，2122，2152，2171，2190，2209，2228，2239，2258，2277，2296，
2315，2345，2364，2383，2402，2421，2432，2451，2470，2489，2508，2538，2557，2576，2595，2614，
2625，2644，2663，2682，2701，2731，2750，2769，2788，2807，2837，2856，2875，2894，2913，2924，
2943，2962，2981，3000，3030，3049，3068，3087，3106，3117，3136，3155，3174，3193，3223，3242，
3261，3280，3299，3310，3329，3348，3367，3386，3416，3435，3454，3473，3492，3503，3522，3541，
3560，3579，3609，3628，3647，3666，3685，3696，3715，3734，3753，3772，3802，3821，3840，3859，
3878，3889，3908，3927，3946，3965，3995，4014，4033，4052，4071，4082，4101，4120，4139，4158，
4177，4188，4207，4226，4245，4264，4294，4313，4332，4351，4370，4381，4400，4419，4438，4457，
4487，4506，4525，4544，4563，4574，4593，4612，4631，4650，4680，4699，4718，4737，4756，4767，
4786，4805，4824，4843，4873，4892，4911，4930，4949，4960，4979，4998，5017，5036，5066，5085，
5104，5123，5142，5153，5172，5191，5210，5229，5259，5278，5297，5316，5335，5346，5365，5384，
5403，5422，5452，5471，5490，5509，5528，5558，5577，5596，5615，5634，5645，5664，5683，5702，
5721，5751，5770，5789，5808，5827，5838，5857，5876，5895，5914，5944，5963，5982，6001，6020，
6031，6050，6069，6088，6107，6137，6156，6175，6194，6213，6224，6243，6262，6281，6300，6330，
6349，6368，6387，6406，6417，6436，6455，6474，6493，6523，6542，6561，6580，6599，6610，6629，
6648，6667，6686，6716，6735，6754，6773，6792，6803，6822，6841，6860，6879，6898，6909，6928，
6947，6966，6985，7015，7034，7053，7072，7091，7102，7121，7140，7159，7178，7208，7227，7246，
7265，7284，7295，7314，7333，7352，7371，7401，7420，7439，7458，7477，7488，7507，7526，7545，
7564，7594，7613，7632，7651，7670，7681，7700，7719，7738，7757，7787，7806，7825，7844，7863，
7874，7893，7912，7931，7950，7980，7999，8018，8037，8056，8067，8086，8105，8124，8143，8173，
8192，8211，8230，8249，8279，8298，8317，8336，8355，8366，8385，8404，8423，8442，8472，8491，
8510，8529，8548，8559，8578，8597，8616，8635，8665，8684，8703，8722，8741，8752，8771，8790，
8809，8828，8858，8877，8896，8915，8934，8945，8964，8983，9002，9021，9051，9070，9089，9108，
9127，9138，9157，9176，9195，9214，9244，9263，9282，9301，9320，9331，9350，9369，9388，9407，
9437，9456，9475，9494，9513，9524，9543，9562，9581，9600，9619，9630，9649，9668，9687，9706，
9736，9755，9774，9793，9812，9823，9842，9861，9880，9899，9929，9948，9967，9986，
---------------------------------------------
对于上述不一致的m值，将公式算出的N值减去1就可得到正确值。

作者: lulijie 时间: 2009-3-1 14:28:52

策略（N) 获取最大数的概率P(N) =(N-1)/m * ∑ 1/i （ ∑中的 i 从N-1到 m-1）
金眼睛在http://bbs.mf8-china.com/viewthread.php?tid=22652&extra=page%3D1&page=9 的83楼中：
提出但m和N较大时，             ∑ 1/i （ ∑中的 i 从N-1到 m-1）
                        可以用       ln  m/(N-1) 近似代替。
   P(N) =(N-1)/m * ∑ 1/i    就相当于  P(N) =(N-1)/m *  ln  m/(N-1)
然后求导，获得 m/(N-1)=e  时P(N)  最大。
得到  N=int(m/e) +1 或附近得到最大值。
--------------------------------------------------------------
妙妙妙，确实妙。给理论上的证明，给出了很好的方向，对于m，N较大时基本上能证明。
但是我1#的结论1却是与m的大小无关，就算m很小，也成立，金眼睛的上述证明方法就不成立了。m很小又如何证明结论1成立呢？
------------------------------------------------------------------------------------
还有金眼睛给出的N计算公式 N=int(m/e) +1  与本人的计算公式 N=int[(m+1)/e] +1 有所区别：
m从3到10000，用公式计算N，金兄算出的N值与正确值相比，有3159个不相符；正确率69%。
                     本人的公式算出的N值与正确值相比，只有519个不相符；正确率95%。
所以本人的公式远远优于金兄的。

作者: lulijie 时间: 2009-3-1 15:56:05

假设策略（N) 获取最大数的概率最高：
那么N的计算公式  N=int[(m+△)/e] +1       int为取整函数。
金眼睛的计算公式  △=0，正确率68.4%
我的计算公式 △=1 ，正确率94.8%
经过计算，当 △=0.8591时算出的结果，正确率最高：
   N=int[(m+△)/e] +1             △=0.8591
m<=30000，仅m=97时，有偏差，其余均正确，正确率9999.6%。
----------------------------------------------------------------------
红字部分出错了，应该为99.996%，谢谢骰迷和 tonylmd批评指出。

[ 本帖最后由 lulijie 于 2009-3-1 23:43 编辑 ]

作者: juventus66 时间: 2009-3-1 16:41:52

学习了

作者: lulijie 时间: 2009-3-1 17:33:43

最新的正确率最高的N值计算公式：
N=int[(m+△)/e] +1 int为取整函数。 △为修正值，e为自然对数。e=2.71828182845905
△=0.859135， 10万以内的m值，只有m=97是有偏差。
-----------------------------------------------------------------------------
以下计算公式，对于m<=100000结果均正确。
m=97， N=int[(m+△)/e]
其他的m，N=int[(m+△)/e] +1

作者: kexin_xiao 时间: 2009-3-1 20:36:51

太深奥了,来学习一下,加分鼓励!

作者: 骰迷 时间: 2009-3-1 22:04:13

正确率9999.6%?比率怎可能比100%大？

作者: tonylmd 时间: 2009-3-1 22:43:31

哈哈~笔误了

作者: lulijie 时间: 2009-3-1 23:22:42

策略（N) 获取最大数的概率 P(N) =(N-1)/m * ∑ 1/i （ ∑中的 i 从N-1到 m-1）
那么  P(N+1) =N/m * ∑ 1/i （ ∑中的 i 从N到 m-1）
所以 △P= P(N+1)- P(N) =1/m * [ ∑ 1/i -1]    （ ∑中的 i 从N到 m-1）    概率增值公式
N=1时， ∑ 1/i  大于1， N=m-1时  ∑ 1/i  =1/（m-1），小于1
因为  ∑ 1/i 是个递减数列  从大于1 递减至 1/（m-1）    （  i从1至m-1）
所以  △P也是递减数列，从大于0  递减至  小于0，
所以概率P(N)  先是递增数列，后变为递减数列，
所以P(N) 有个最大值，当△P第一次变为负值时的N就是所求的最大值的自变量。
那么N等于多少， △P 第一次小于0呢？
------------------------------------------------------------------------------------
第一：设 C(k)=∑ 1/i -ln(k+1)    （ ∑中的 i 从1到k ）          C(k)是个递增数列
                     K趋向无穷大时， C(k)的极限  就是欧拉常数C=0.57721566490153286060651209
那么  C(N-1)=∑ 1/i -ln(N)    （ ∑中的 i 从1到N-1）
      C(m-1)=∑ 1/i -ln(m)    （ ∑中的 i 从1到m-1）
因为 m* △P=(∑ 1/i  -1)       （ ∑中的 i 从N到m-1）
   所以 m* △P=C(m-1)+ln(m) -C(N-1)-ln(N)-1  =ln(m/N)-1 + C(m-1)-C(N-1)
   m* △P=ln(m/Ne)  + C(m-1)-C(N-1)

为C(k)是个递增数列，C(m-1)-C(N-1)大于0，
假设M是不大于m/e的最大整数，那么M<=m/e<M+1,
   那么  m/Ne>=M/N
当N取M值时，m/Ne>= M/N=1
   m* △P=ln(m/ne)  + C(m-1)-C(N-1) >=ln1 + C(m-1)-C(N-1) >0
所以N<=M 时，△P都大于0，所以P(N)取最大值时，N 必定>=M+1 。
-----------------------------------------------------------------------------
第二：同样：
设 C'(k)=∑ 1/i -ln(k)    （ ∑中的 i 从1到k ）             C'(k)是个递减数列
                     K趋向无穷大时， C’(k)的极限  就是欧拉常数C=0.57721566490153286060651209
那么  C'(N-1)=∑ 1/i -ln(N-1)    （ ∑中的 i 从1到N-1）
      C’(m-1)=∑ 1/i -ln(m-1)    （ ∑中的 i 从1到m-1）
因为 m* △P=(∑ 1/i  -1)       （ ∑中的 i 从N到m-1）
   所以 m* △P=C’(m-1)+ln(m-1) -C'(N-1)-ln(N-1)-1  =ln[(m-1)/(N-1)]-1 + C'(m-1)-C'(N-1)
   m* △P=ln[(m-1/(N-1)e] + C'(m-1)-C'(N)

因为C‘(k)是个递减数列，C'(m-1)-C'(N)小于0，
假设M是不大于m/e的最大整数，那么M<=m/e<M+1,
   (m-1)/(N-1)e<(m-1)/m * (M+1)/(N-1)
当N取M+2值时， (m-1)/(N-1)e<(m-1)/m * (M+1)/(N-1)=(m-1)/m  <1
            m* △P=ln[(m-1)/ (N-1)e]  + C'(m-1)-C'(N) <ln1 + C'(m-1)-C'(N)<0
所以N>=M+2 时，△P都小于0，所以P(N)取最大值时，N 必定<=M+2 。
-------------------------------------------------------------
综合第一和第二，得出，
假设M是不大于m/e的最大整数，那么M<=m/e<M+1,
那么，P(N)取最大值时，M+1<=N<=M+2
所以结论1得证。

[ 本帖最后由 lulijie 于 2009-3-2 01:43 编辑 ]

作者: lulijie 时间: 2009-3-1 23:38:17

△=0.858时，计算公式可以在m<1000时，正确率达到100%，但是m再增大时，计算公式的正确率却远远不如其他修正值△。
比如m<30000时，△=0.858时，计算公式 m=2818，5539，8260，10981，13702，16423，19144，21865，23322，26043，28764，出现偏差，
所以才认为修正值0.858不如8591好。

[ 本帖最后由 lulijie 于 2009-3-1 23:44 编辑 ]

作者: lulijie 时间: 2009-3-2 00:37:27

结论1证明了，结论2就好证明了。
            P(M1) =(M1-1)/m * ∑ 1/i （ ∑中的 i 从M1-1到 m-1）
   因为 ∑ 1/i   =ln(m/(M1-1))  + C(m-1)-C(M1-1)
因为m趋向于无穷大，所以 m/e  趋向于无穷大，所以M1-1也趋向于无穷大
所以C(m-1)-C(M1-1)  趋向于C-C=0                C欧拉常数。
m/(M1-1)趋向于e，ln(m/(M1-1))  趋向于1，
P(M1)的极限就=1/e  *1=1/e。

作者: lulijie 时间: 2009-3-2 20:54:19

题目：有m个实数，两两不等，每次只显示一个数给你看，你可以选择获取它或放过它看下一个数。你的目标是得到最大的数。
   那么如何安排策略，才能使得获取最大数的概率最高？
策略（n)  ：放过前面的n个数，从第N=n+1个数开始，若与前面的所有数相比是最大的，就选择该数，否则放过，看下一个数，一直到所看的数与前面的所有数相比是最大为止，选择该数。若看到了最后一个数，就只能选择最后一个。

假设：  q是  不比 m/e  大的最大整数，即q=int(m/e) 或q<=m/e<q+1    int是取整函数， e为自然对数，=2.718281828……
那么：
   结论1：策略（n) 获取最大数的概率
            P(n) =n/m * ∑ 1/i （ ∑中的 i 从n到 m-1）    n>0
            P(n) =1/m                                              n=0
   结论2：使得概率P最大的n值必等于q或q+1。
   结论3：m趋向于无穷大时，P(q) 或P(q+1)的极限等于1/e 。
         也就是说m很大时，最优策略获取最大数的概率等于1/e。
证明：结论1：最大数出现在被看的轮次是随机的，所以出现在任何轮次的概率都是1/m。
         最大数若出现在前n轮次，由于策略(n)的缘故，已被放弃，所以不可能被选中了。最大数出现在n+1次以后，比如第i轮次（i>n），根据策略，被选中的条件是i-1轮次之前出现的所有i-1个数中最大的数出现在第n轮次之前（包括第n轮次），因为若出现在n轮次之后，根据策略，它必备选中，从而不可能获得最大数。所以最大数出现第i轮次且被选中的概率=1/m  *  n/(i-1)=n/m * 1/(i-1),所以策略（n) 获取最大数的概率
      P(n)=n/m * ∑1/(i-1),  (∑中的i=n+1 to m)
   即 P(n)=n/m * ∑ 1/i ，（ ∑中的i从n到 m-1）
所以结论1得证。
   结论2 ：思路：
            1.首先证明  数列P(n) 是个先递增后递减的数列。头尾的数列值相等，都等于1/m，所以中间有最大值。
                        前后两个数列的差值△P= P(n+1)- P(n) =1/m * [ ∑ 1/i -1]    （ ∑中的 i 从n+1 到 m-1）
                                                即  m*△P= [ ∑ 1/i -1]    （ ∑中的 i 从n+1 到 m-1）
                        从上面式子可看出△P是个递减数列，从大于0，逐渐减至小于0. 当第一次变为负值时的n就是所求的最大值的自变量。
            2.构造两个新的数列：C(k)=∑ 1/i -ln(k+1)    （ ∑中的 i 从1到k ）          C(k)是个递增数列
                                             C'(k)=∑ 1/i -ln(k)       （ ∑中的 i 从1到k ）          C'(k)是个递减数列
                  这两个数列的极限值都相等，都等于欧拉常数C=0.57721566490153286060651209
            3.将概率△P用C(k)或C'(k)来表示：m* △P=ln(m/(n+1)) + C(m-1)-C(n) -1             式子1
                                                                  m* △P=ln[(m-1)/n] +  C'(m-1)-C'(n+1) -1          式子2
                     当n=q-1时，用式子1判断△P>0,所以P(n)取最大值时，n 必定>=q
                     当n=q+1时，用式子2判断△P<0,所以P(n)取最大值时，n 必定<=q+1
               所以就得出P(n)取最大值，q<=n<=q+1,结论2得证。
结论3：P(q) =q/m * ∑ 1/i （ ∑中的 i 从q到 m-1）
            因为 ∑ 1/i =ln(m/q)  + C(m-1)-C(q-1)
            所以 P(q) =q/m * [ln(m/q)+ C(m-1)-C(q-1)]
            因为m趋向无穷大，所以q=int(m/e)也趋向无穷大，m/q趋向e, q/m 趋向1/e, C(m-1)-C(q-1)]趋向C-C=0，
            所以 P(q) 趋向1/e * (lne+0)=1/e.
            所以结论3得证。
-------------------------------------------------------------------
下面证明结论2：
         C(n)=∑ 1/i -ln(n+1)    （ ∑中的 i 从1到n）                式子a
         C(m-1)=∑ 1/i -ln(m)    （ ∑中的 i 从1到m-1）          式子b
         因为m*△P=[ ∑ 1/i -1]    （ ∑中的 i 从n+1 到 m-1）
         所以  式子b-式子a 得到 ∑ 1/i =ln m/(n+1) +  C(m-1)- C(n)    （ ∑中的 i 从n+1 到 m-1）
         所以  m*△P=ln m/(n+1) +  C(m-1)- C(n)-1
         n取q-1值时，m*△P=ln m/q +  C(m-1)- C(q)-1
         因为q<=m/e<q+1,所以m/q>=e,  因为C(k)是个递增数列，所以C(m-1)- C(q)>0.
         所以m*△P >lne+0-1>0.
         因此 n取q-1值时，△P>0
         -----------------------------
         C'(n)=∑ 1/i -ln(n)    （ ∑中的 i 从1到n）
         C’(m-1)=∑ 1/i -ln(m-1)    （ ∑中的 i 从1到m-1）
         因为 m* △P=(∑ 1/i  -1)       （ ∑中的 i 从n+1到m-1）
         所以 m* △P=C’(m-1)+ln(m-1) -C'(n)-ln(n)-1  =ln[(m-1)/n] + C'(m-1)-C'(n)-1
         n取q+1值时，m*△P=ln (m-1)/(q+1) +  C'(m-1)- C'(q+1)-1
         因为q<=m/e<q+1,所以(m-1)/(q+1)< m/(q+1)<e,  因为C'(k)是个递减数列，所以C'(m-1)- C'(q+1)<0.
         所以m*△P <lne+0-1<0,
         因此n取q+1值时，△P<0。
      所以结论2得证。

[ 本帖最后由 lulijie 于 2009-3-2 21:01 编辑 ]

作者: lulijie 时间: 2009-3-2 21:36:20

模拟计算公式
N=int[(m+△)/e] +1       int为取整函数。 △为修正值，e为自然对数。e=2.71828182845905
因为放过的个数n=N-1，
所以概率取最大值时，n=int( m/e+△')    模拟计算公式 (△'=△/e)
用  △'来修正n是很有道理的。
因为 int( m/e)=q ,n不是等于q，就是等于q+1
当 0<△'<1时  q=  int( m/e)<= int( m/e+△') <= int( m/e)+1=q+1
   所以  int( m/e+△')  不是等于q，就是等于q+1。只要△'选的适当，完全可以用来代替n值。正确率可以很高。
若△' 等于0时，nt( m/e+△') 只能等于q，不可能等于q+1，所以等于q+1的这部分n就不能正确求出，所以用△' 等于0，错误率很高。
△' 等于1时，nt( m/e+△') 只能等于q+1，不可能等于q，所以等于q的这部分n就不能正确求出，所以用△' 等于1，错误率也很高。
  所以，修正值△' 应该在0和1之间。

作者: ggglgq 时间: 2009-3-6 08:29:16

　　


嗯，楼主的题目很好，楼主和金眼睛对问题的分析研究很透彻！

自然对数 e 的科学应用很广呀！这使我想起 N 为底的对数的概率应用：

在 N 进制中，首位数为 m 的自然数的概率 （ N 为大于 1 的自然数）

http://bbs.mf8-china.com/viewthread.php?tid=2153　　
　　　　
　　可惜无暇去证明，不知各位高手能否抽空去证明一下呢？谢谢了！　　
　　　　
　　　　
　　　　
　　　　

欢迎光临魔方吧·中文魔方俱乐部 (http://www.mf8-china.com/)