求概率(大家讨论讨论)

lulijie

具体取数过程如下：   逗号前面的数表示奇数次取的数（所有可能数值第几小的数，或第几大的数）      
                             逗号后面的数表示偶数次取的数（所有可能数值第几小的数，或第几大的数）
       C()，D()
N=2：1，1
N=3：1，2
N=4：1，1
N=5：1，1
N=6：1，2
N=7：1，1
N=8：1，1
N=9：1，2
N=10：1，1
..........
N=2000：4，2
N=2001：1，2
N=2002：1，2
N=2003：1，2
N=2004：1，2
N=2005：1，2
N=2006：1，2
N=2007：1，2
N=2008：1，2
N=2009：4，2
---------------
所有数据    取数奇数次胜.rar (2.93 KB, 下载次数: 4)

2009-7-7 01:03:42 上传

下载次数: 4
所有数据

这样最优方案就是第一次取 4，
    若大了，那么剩3个数可选，因为是偶数次，查上表，第二次选2
    若小了，还剩2005个数可选，因为是偶数次，查上表得2，即第二次选第2小的数，即4+2=6。
  。。。。。。
最大概率  A(2009)=0.666500746640127  = 1339/2009
当然最优方案不只一种，但最大概率不会超过上面的值。

[ 本帖最后由 lulijie 于 2009-7-7 18:17 编辑 ]

superacid

看上去挺有道理的，方法就应该是这样的。

我各方面就组合比较差，所以请大家多多指教。

Osullivan

我来晚啦~~~~~~~~~
大家都解决的差不多了~~~~~~~~~
我也只想到二分法哦~~~~~~~~
lulijie做法很严密正确~~~~~~~

Osullivan

原帖由 lulijie 于 2009-7-7 01:03 发表
具体取数过程如下：   逗号前面的数表示奇数次取的数（所有可能数值第几小的数，或第几大的数）      
                             逗号后面的数表示偶数次取的数（所有可能数值第几小的数，或第几大的数）
    ...

其实可以证明当N无限大时，概率为2/3的~~~~~~~~~~~~~

lulijie

详细计算：关于第一次取数到底可以取那些数，其实很多很多数都可以取。
对于达到 奇数次胜最大概率的第一次取数C(N)：
     N除以3的余数为1，  可以取形如3k+1的所有数。
     N除以3的余数为2，  可以取任何数。
     N是3的倍数，可以取形如3k或3k+1的所有数。
对于达到偶数次胜最大概率的第一次取数D(N)：
     N除以3的余数为1，  可以取任何数。
     N除以3的余数为2，  可以取形如3k+1或3k+2的所有数。
     N是3的倍数，可以取形如3k+2的所有数。
------------------------------------------------------
对于N=2009，奇数次胜。
     因为2009 mod 3=2，所以第一次取任何数都可以，那么取1，
    剩下2008个数，因为2008 mod 3=1，因为是偶数次，也可以取任意数，不妨取1，即1+1=2
    剩下2007个数，因为2007 mod 3=0，因为是奇数次，可以取形如3k或3k+1的所有数。不妨也取1，即2+1=3
    剩下2006个数，因为2006 mod 3=2，因为是偶数次，可以取形如3k+1或3k+2的所有数。不妨也取1，即3+1=4
    剩下2005个数，因为2005 mod 3=1，因为是奇数次， 可以取形如3k+1的所有数。不妨也取1，即4+1=5
     剩下2004个数，因为2004 mod 3=0，因为是偶数次，可以取形如3k+2的所有数。可取2，即5+2=7。
   这样开始分两条路，若大了，只能取6，若小了，还剩2002个数，2002 mod 3 =1，可取1，即7+1=8.
    .......
----------------------------------------
N=2009，当然，第一次可以选1005（因为可选任意数），这样因为两侧对称，数字又减小得快，工作量明显下降。