一道奥林匹克数学竞赛难度的概率题(368楼接龙另一概率题（尚无解答贴出！））

qinxialin1979

linyeliu 发表于 2013-1-23 12:37
厉害，我昨晚也试图从公式上推导至一致，但总有几项没消去，可能公式一开始有些弄错了。
好在你的 ...

那也得有你的式子才行了，
不然我都不知道往哪里推

蓝咖啡豆

楼上的两位不要谦虚来来去去的了。一天很轻松的忙工作啦。

楼主要不写个总结完美一下？如果说还等时间求更保险，建议哪位热心的程序同学做个穷举运行吧。

认真读了一下lin的公式思路，是很清晰，这回看出了奥数风采，再次赞一个！liu的几次推算预见的强大也不用多说了。

linyeliu

我只是觉得如果是奥数题的话，是不是应该还有其他不需要通过编程的解法，否则如何求出答案哪？

vale

SoftSome 发表于 2013-1-21 23:28
我的方法非常非常烦，所以暂时不贴也罢。

另外回其他几位TX的帖子：

在表同盒同的情况下，也就是最难计算的一种情况下，答案是37%，就是前面有人贴出的。

把5块表打包，算16块表的可能分法除以20块表的可能分法。

建议google “integer partition"，就知道这个分表问题本质上就是integer partition，我这2天仔细研究了integer partition，有好几种算法，也有公式算N的，很受启发，老外研究数论的确比中国深入多了。

vale

蓝咖啡豆 发表于 2013-1-23 18:29
楼上的两位不要谦虚来来去去的了。一天很轻松的忙工作啦。

楼主要不写个总结完美一下？如果说还等 ...

穷举结果如下： ，当然是google的，不是我算的。

所以概率=231/627=37%

第一列，表的数目，第二列，分法数量

  1                1        1
    2                2        2, 1-1
    3                3        3, 2-1, 1-1-1
    4                5        4, 3-1, 2-2, 2-1-1, 1-1-1-1
    5                7        5, 4-1, 3-2, 3-1-1, 2-2-1, 2-1-1-1, 1-1-1-1-1
    6               11        
    7               15        
  8               22
    9               30
   10               42
   11               56
   12               77
   13              101
   14              135
   15              176
   16              231
   17              297
   18              385
   19              490
   20              627
   21              792
   22            1,002
   23            1,255
   24            1,575
   25            1,958
   26            2,436
   27            3,010
   28            3,718
   29            4,565
   30            5,604
   31            6,842
   32            8,349
   33           10,143
   34           12,310
   35           14,883
   36           17,977
   37           21,637
   38           26,015
   39           31,185
   40           37,338
   41           44,583
   42           53,174
   43           63,261
   44           75,175
   45           89,134
   46          105,558
   47          124,754
   48          147,273
   49          173,525
   50          204,226
   51          239,943
   52          281,589
   53          329,931
   54          386,155
   55          451,276
   56          526,823
   57          614,154
   58          715,220
   59          831,820
   60          966,467
   61        1,121,505
   62        1,300,156
   63        1,505,499
   64        1,741,630
   65        2,012,558
   66        2,323,520
   67        2,679,689
   68        3,087,735
   69        3,554,345
   70        4,087,968
   71        4,697,205
   72        5,392,783
   73        6,185,689
   74        7,089,500
   75        8,118,264
   76        9,289,091
   77       10,619,863
   78       12,132,164
   79       13,848,650
   80       15,796,476
   81       18,004,327
   82       20,506,255
   83       23,338,469
   84       26,543,660
   85       30,167,357
   86       34,262,962
   87       38,887,673
   88       44,108,109
   89       49,995,925
   90       56,634,173
   91       64,112,359
   92       72,533,807
   93       82,010,177
   94       92,669,720
   95      104,651,419
   96      118,114,304
   97      133,230,930
   98      150,198,136
   99      169,229,875
  100      190,569,292

qinxialin1979

我的感觉是不管有没有顺序，盒子，表是不是一样的，最后结果算下来的结果都应该是一样的。
有顺序的就多了顺序，那么数目自然就多了，但是相对的总数也会增加的。所以概率算下来应该是一样的。
算概率的时候，如何避免重复计算是关键。
就象我最先开始用的方法那样，尽管避免了一些重复，还是被linyeliuTX的火眼金星发现有重复的

怎样知道有没有重复呢？分开来算，如果总和跟分母是一样的，那就对了。如果总和超过分母，那么就有重复计算了。

大脚印

kennyxue 发表于 2012-12-26 19:54
计算方法：
1.  问题简化为 ：  20个坏表放24个盒子里，其中至少一个盒子里有5个或者5个以上坏表的概率。
...

没学过数学？ 这么离谱的思维

vale

qinxialin1979 发表于 2013-1-23 19:50
我的感觉是不管有没有顺序，盒子，表是不是一样的，最后结果算下来的结果都应该是一样的。
有顺序的就多了 ...

盒子是否相同，表是否相同，结果完全不同。

这个就是国内讲的球盒模型，按球是否相同，盒是否相同，是否有空盒算有8种情况。

你可以算至少有一个盒子至少有2个坏表的概率，就知道对不对了。。实际上就是算20个盒子各放一个的概率。

表同盒同情况下的概率就是1/627。。。其他情况呢？

SoftSome

蓝咖啡豆 发表于 2013-1-23 18:29
楼上的两位不要谦虚来来去去的了。一天很轻松的忙工作啦。

楼主要不写个总结完美一下？如果说还等 ...

我认同qinxialin1979的结果。我以前的解法是有问题的。
我很高兴我发了这一贴，让大家包括我自己学到了一些东西。
有不认同qinxialin1979的结果的可继续讨论。
认同的也可以继续讨论更好的解法。非常感谢大家的努力奉献。

linyeliu

vale 发表于 2013-1-23 19:13
在表同盒同的情况下，也就是最难计算的一种情况下，答案是37%，就是前面有人贴出的。

把5块表打包，算16 ...

Integer partition 是排列组合的问题，用来求多少种解，大学教科书上有公式，而证明方法就有用你的隔板法。但这不能用来求我们通常意义的概率。你能求出的只是某种情况占所有可能性的几分之几，就像我举的2坏表，2盒的例子，按这种方式，将得到2\3，而不管多少好表，显然不是概率的涵义。概率的一种定义是指重复试验n次，某种事件发生的次数与ｎ之比，ｎ趋向无穷大。

vale

linyeliu 发表于 2013-1-23 20:19
Integer partition 是排列组合的问题，用来求多少种解，大学教科书上有公式，而证明方法就有用你的隔板法 ...

我早就说隔板方法解决的是表同盒不同这种情况下的概率。我早就抛在一边了，现在说的是表同盒同的情况。

仔细看看，我现在说的是表同盒同的情况，2个表2个盒就是2种情况，上面列得清清楚楚啊。

你说的n趋向无穷大的时候得出的就是可能性。就像投硬币一样，做无限次，最终正面的可能性就是50%。。。

你说的这种叫频率，取样无限次的时候趋向等于概率。

另外隔板法不能证明integer partition的问题。

linyeliu

vale 发表于 2013-1-23 20:36
我早就说隔板方法解决的是表同盒不同这种情况下的概率。我早就抛在一边了，现在说的是表同盒同的情况。

...

对不起，我可能对你要表达的意思理解错了，那用你的方式求4个好表，2个坏表，2盒，2个坏表同盒的概率是多少哪？

vale

linyeliu 发表于 2013-1-23 20:48
对不起，我可能对你要表达的意思理解错了，那用你的方式求4个好表，2个坏表，2盒，2个坏表同盒的概率是多 ...

在表同盒同的情况下显然是1/2。。。

看看我上面列出的一排数字，就是所有的排列可能数。按P这种排列来算，表同盒同情况下各种分法的重复次数是不同的，已经没办法剔除了。

linyeliu

vale 发表于 2013-1-23 20:36
我早就说隔板方法解决的是表同盒不同这种情况下的概率。我早就抛在一边了，现在说的是表同盒同的情况。

...

我把整数分拆理解成a1+a2+a3+.•••ak=ｎ了，不知道它还有其它限定，sorry。但不知这分拆于我们的题有何联系？

linyeliu

vale 发表于 2013-1-23 20:53
在表同盒同的情况下显然是1/2。。。

看看我上面列出的一排数字，就是所有的排列可能数。按P这种排列来算 ...

你的意思是与盒子数无关吗？

qinxialin1979

vale 发表于 2013-1-23 19:39
穷举结果如下： ，当然是google的，不是我算的。

所以概率=231/627=37%

不知道这种方法对不对，但是你的231／627肯定是不对的。

<＝4坏表的有108种，
例如
1,.....1
2，1，1,....,1
2，2，1,....,1
...
2,2,2,,...2

也就是说>=5的有519种，如果这种方法可以的话，概率就是0.8278。

qinxialin1979

楼上两位都是专家，我都没有听过这些术语

vale

linyeliu 发表于 2013-1-23 21:07
你的意思是与盒子数无关吗？

表同盒同情况下，24个盒子和20个盒子没任何区别，至少4个盒子永远是空的，没有坏表，这个是本帖第一页就讨论过的呀！

vale

linyeliu 发表于 2013-1-23 21:02
我把整数分拆理解成a1+a2+a3+.•••ak=ｎ了，不知道它还有其它限定，sorry。但不知这分拆于我们的题有何 ...

这些数就是每个盒子的坏表数啊，20有多少种分拆方法就有多少种坏表分配方法，因为0是没有意义的。

linyeliu

vale 发表于 2013-1-23 21:17
表同盒同情况下，24个盒子和20个盒子没任何区别，至少4个盒子永远是空的，没有坏表，这个是本帖第一页就 ...

那你假设2个坏表放入100盒，两个同盒的概率也是50%？

vale

linyeliu 发表于 2013-1-23 21:23
那你假设2个坏表放入100盒，两个同盒的概率也是50%？

也是50%，无论怎么放，都只能放2个盒子里，而盒子是没区别的。你只有2种可能，无论怎么放都归到其中一种

linyeliu

vale 发表于 2013-1-23 21:17
表同盒同情况下，24个盒子和20个盒子没任何区别，至少4个盒子永远是空的，没有坏表，这个是本帖第一页就 ...

我没想到你认同这种空箱理论，这是不对的。

qinxialin1979

将5个表打包，变成16个，这样求出来的，肯定是>=5。
但是其他的也可能是>=5的坏表的。
例如10个表里面就可以有很多>=5 的情况的。

linyeliu

vale 发表于 2013-1-23 21:39
也是50%，无论怎么放，都只能放2个盒子里，而盒子是没区别的。你只有2种可能，无论怎么放都归到其中一种 ...

如果你认为这是概率的话，我是无法说服你了。

vale

就像投硬币，你翻着跟头投，转着圈投，正面就是正面。
分配看的是结果，而不是过程。

vale

qinxialin1979 发表于 2013-1-23 21:10
不知道这种方法对不对，但是你的231／627肯定是不对的。

=5的有519种，如果这种方法可以的话，概率就是0 ...

108这个数是怎么得出来的？

linyeliu

qinxialin1979 发表于 2013-1-23 21:11
楼上两位都是专家，我都没有听过这些术语

千万不要把我说成什么专家，只是业余爱好，以防老年痴呆。

vale

linyeliu 发表于 2013-1-23 21:41
如果你认为这是概率的话，我是无法说服你了。

无所谓说服不说服，我们算一下4个球放4个盒里面，和放5个盒里面，每个盒不多于一个球的概率是多少。球和盒都没区别。

qinxialin1979

vale 发表于 2013-1-23 22:08
108这个数是怎么得出来的？

就是将我的公式里面的式子换成常数1就可以了，当然我是用计算机算的。用同样的方法，我也算了所有的情况，得到的是627。
这就是计算了有多少种可能性了
例如
4个，3个，2个，1个
0 0 0 20
0 0 1 18
0 0 2 16
...

1 0 0 16
1 0 1 14

...

5 0 0 0

linyeliu

vale 发表于 2013-1-23 22:15
无所谓说服不说服，我们算一下4个球放4个盒里面，和放5个盒里面，每个盒不多于一个球的概率是多少。球和 ...

这不是算的问题，而是你应该去做个实验，拿2个表随机放入100个盒子，做10次，看看有没有5次2个表在一盒里。