[讨论] 给Ross的《概率论基础教程》盖个楼

showcraft

相对于比较晦涩的微积分与线代，我想概率论应该更贴近生活，更为群众喜闻乐见。
最近开始看Ross的《概率论基础教程》，很好的教材，推荐看英文版，因为中文版有得地方翻得我觉得含混。
中文版
http://ishare.iask.sina.com.cn/f/23064043.html

英文版
A First Course in Probability
http://ishare.iask.sina.com.cn/f/33805215.html

英文版douban
http://book.douban.com/subject/3715244/

昨晚看完了第一章，其中打星号的1.6节，方程整数解的个数很精髓。
打算给这本书，或者说给老少咸宜，趣味盎然的概率论盖个楼，采用趣味题目，再加上作者优美总结（结合楼主自身理解），有感兴趣的童鞋可以冒个泡，你们的id有可能到时候我还得在题目中借用下，呵呵。
先来应景出个题目给助助兴，开个头：
众所周知，比如说，周末泽雄大牛签名售书，有10名激动的燕友相约排队去参加。楼主负责统计，然而这10位神秘的匿名燕友均不肯透露自己的id（也即认为这10人不可区分），只说了自己的个性，楼主发现其中有4名急性子，6名慢性子（比如楼主）。假设届时现场排队可以随意，因为泽雄老师均会为诸位花痴粉丝一一签名握手，大家不用着急哈。问题1，这4名急性子，6名慢性子的匿名不可区分燕友长队排列，共有多少种方式？
现在假设排列队伍中任意两位急性子不可相邻，因为怕急性子话赶话，或者你推我搡，发生不愉快哈（题目需要，不是要黑急性子燕友，呵呵）。那么请问，问题2，这4名急性子，6名慢性子的匿名不可区分燕友长队排列，任意两名急性子不可相邻，共有多少种方式？
假设情况又有变化，由于民间马路社社长旧苗兄人肉搜索功力实在强大，这10名燕友的身份被他一一探明（也即现在各人之间都可区分），那么这种情况下，依然对应上面两种情况，各有多少种排列方式？

showcraft

呵呵，y老那是杀鸡用牛刀了，除了1的第一种情况外，其他都没正确。
1的第一种情况，也即人员不可区分，确实是我没说清楚，身份上无法区分，但个性上还是可以区分的，所以答案应该是C（10，4）。
另外，排列的大写字母，似乎用P比较多，Permutation么，呵呵。

showcraft

再继续，题目都不算难。
现在假设这10名匿名燕友不可区分（这次个性也不知道，完全不可区分），泽雄老师说了，排成一队太挤也不美观（不好意思，让泽雄老师躺枪了，呵呵），大家分成4队来排吧，队与队之间可区分，比如A队是只签名，B队是签名加握手，C队是签名加合影，D是签名加握手加合影（由于10名成员不可区分，所以每队只有人数差别，队内顺序不用考虑，只牵涉到组合而非排列，或者说用集合或者圈子的概念代替这里的队更合适）。问题1，假设每队至少1人，那么有多少种分队方法？问题2，假设每队可以为空（比如大家都抢着到D队，前三队没人排了），那么有多少种分队方法？
这也就等价于不定方程，x1+x2+x3+x4=10的解向量（x1，x2，x3，x4）的个数。问题1中，x1，x2，x3，x4为正整数，问题2中，x1，x2，x3，x4为非负整数。而这也正是ross书中1.6节所讨论的内容。

showcraft

这个一是我个人水平有限，二是论坛盖楼，本就不宜过深。
大树兄可以推荐概率方面有哪些推崇的大师的经典啊？

showcraft

**

    再来出丑。
    可以设想，把十个人（元素）先排成一列，规定，排好后，相邻两个人之间要空出一个人的位置。然后，叫上三个小孩子出来玩儿。
    问题一、因为十个元素中间出现了九个空档。
    叫 ...
ys1937 发表于 2012-10-25 16:48

回ys老，第一种非空情况，确实就是C（9,3），也就是等价于10个小孩中的9个空当，有三个小孩去占领。
第二种可以为空的情况复杂点，按照ross的方法，他还是利用了第一种，做了变量代换：
x1+x2+x3+x4=10，x1到x4为正整数，为C（9,3）
那么在x1到x4为非负整数的情况下，设
y1=x1+1，y2=x2+1，y3=x3+1,y4=x4+1
现在有y1+y2+y3+y4=14，对y1到y4套用第一种情况，答案为C（13,3）

showcraft

**

    ROSS的第二题的解题思路是比较巧妙的。
    他的答案是：13*12*11/（2*3） = 26*11 = 286
    我的办法比较笨，答案是：
    十个人排列后，出现11个空档。
    （1） 如果三个小孩子每人进一个空档， ...
ys1937 发表于 2012-10-26 10:47

回ys老，我读书的时候，大概十年前教材用的还是P，也许现在改成了A了。
Ross的方法，也可以等价如下：
10个小孩子排好队，再请来4位，因为均不可区分，然后再在队伍中的13个空档中插入3个小孩子，每队非空，然后每队再抽出1名小孩子，这样就可以了。

showcraft

14# psyzjs 多谢大树兄不吝赐教，等精力允许我会选择涉猎。不过目前精力有限，且Ross门槛相对较浅，我还是先专攻他的书吧。

showcraft

ys老说的第一种，是化抽象问题为具象问题，有利于思考。第二种，正是数学归纳法的本质，如果是我，会从
x1+x2=10开始，呵呵。

showcraft

继续：
假设排队的10名不可区分（除个性可区分外）燕友中，现已知其中6人慢性子，而另外4人急性子，现在不仅是要求这4名急性子在排队中不可相邻，还得考虑到如果有一位慢性子被两位急性子夹在中间，和左右都插不上话，因而附加一要求，即任意两位最近的急性子中间，至少被两位慢性子隔开，现求此种排队方法数。

showcraft

**

    把元素缩得太少，有时也不是好事。把问题的典型性改变了，就成“SARS”了。
    比方说这个问题吧，解决这个二元问题最好的解决办法是掰手指（手指不够用脚指也行）。
    （0，10）、（10，0）；（ ...
ys1937 发表于 2012-10-27 09:44

哈哈，想不到ys老也犯了个低级错误，漏了（10,0）了。另外，我觉得没改变典型性，按照ross的公式，答案就是C（10+2-1,2-1）=C(11,1)。

showcraft

哈哈，那是我看漏了，抱歉。
“SARS”方法是啥子方法呦？

showcraft

这次ys老，您真的搞错了。n个元素划分为r个可空集合，为C（n+r-1,r-1）,如果用数学归纳法证明，那么初始情况，r就是取2，所以还在典型内，如果r取1，则就是您说的sars了。

showcraft

佩服ys老，讲解的精到。
按照变量代换的方法
令y1=x1-1，y2=x2-1，y3=x3-1，y4=x4-1
则有y1+y2+y3+y4=6
从此中求出的（y1，y2，y3，y4），y1到y4大于等于1，所对应的（x1，x2，x3，x4），x1到x4大于等于2，所以为C（5，3）。

showcraft

ys老的题目有点意思，我将它推广到x1 + x2 + x3 +...+ xr = m的正整数解的组数，要求：x1〈x2〈x3〈...xr。
还是变量代换：
设y2=x2-x1，y3=x3-x2，...，yr=xr-x（r-1）（下标），y2到yr均为正整数，于是式子化为
y2+y3+...+yr=xr-x1，而xr-x1的取值范围是关键
上限情况，x1=1，x2=2，...，x（r-1）=r-1，xr=m-r（r-1）/2，此时xr-x1=m-1-r（r-1）/2
下限情况，设x1=a，x2=a+1，...，xr=a+r-1，全部相加有ra+r（r-1）/2=m，a=m/r-(r-1)/2（若a非正整数，应就近取整），此时对应了，若a为整数，则下限为r-1，否则为r
确定了xr-x1的取值范围，令下限为正整数p，上限为正整数q，则对y2+y3+...+yr=xr-x1套用ross的方法即可，答案为C（p-1，r-2）+C（p，r-2）+...+C（q-1，r-2）
在本题中，如m取10，则p=q=3，答案为C（2,2）=1
如m取15，则p为4，q为8，答案为C（3,2）+C（4,2）+...+C(8,2)，具体数字我就不算了。
以上是x1〈x2〈x3〈x4的情况，若无此要求，而仅需x1、 x2、x3、 x4 都不相等，则仅需在x1〈x2〈x3〈x4的情况下得出的组数再乘以Pr，即r的全排列即可。

showcraft

回ys老，第一种非空情况，确实就是C（9,3），也就是等价于10个小孩中的9个空当，有三个小孩去占领。
第二种可以为空的情况复杂点，按照ross的方法，他还是利用了第一种，做了变量代换：
x1+x2+x3+x4=10，x1到x4各 ...
showcraft 发表于 2012-10-26 10:17

忽然发现，我这里出了个大bug，ross的方法中x1到x4并无各不相同的要求，我写错了。

showcraft

再作下总结吧，算是给第一章做个小结：

问题1：
对于正整数x1，x2，x3，x4，有x1+x2+x3+x4=10，求解向量（x1，x2，x3，x4）的个数。
这个比较好理解，可以认为等价于10个不可区分的球排成队列，中间空出9个空当，用3块
隔板去划分，答案为C（9,3）。
推广开来，x1+x2+x3+...+xr=n，解向量个数为C（n-1，r-1）。

问题2：
对于非负整数x1，x2，x3，x4，有x1+x2+x3+x4=10，求解向量（x1，x2，x3，x4）的个数
。
可以在一的基础上用变量代换的方法解决。
设y1=x1+1，y2=x2+1，...，yr=xr+1，则
y1+y2+y3...+yr=n+r，解向量个数为C（n+r-1，r-1）
其中的y1到yr大于等于1，等价于相应的x1到xr大于等于0。也可以这样考虑，即在n个不可
区分球的队列中任意再添加r个球，然后再划分r组，划好后每组至少有1个球，每组再拿去
1个球，即为所求答案。

问题3（前两问为Ross原书所载，此问为笔者扩充）：
对于正整数x1〈x2〈x3〈x4，有x1+x2+x3+x4=15，求解向量（x1，x2，x3，x4）的个数。
这次不展开了，直接推广到x1 + x2 + x3 +...+ xr = n的正整数解的组数，要求：x1〈x
2〈x3〈...<xr。
还是变量代换：
设y2=x2-x1，y3=x3-x2，...，yr=xr-x（r-1）（下标），y2到yr均为正整数，于是式子化
为
y2+y3+...+yr=xr-x1，而xr-x1的取值范围是关键
上限情况，x1=1，x2=2，...，x（r-1）=r-1，xr=m-r（r-1）/2，
此时xr-x1=m-1-r（r-1）/2
下限情况，设x1=a，x2=a+1，...，xr=a+r-1，全部相加有ra+r（r-1）/2=m，a=m/r-(r-1
)/2（若a非正整数，应就近取整），此时对应了，若a为整数，则下限为r-1，否则为r
确定了xr-x1的取值范围，令下限为正整数p，上限为正整数q，则对y2+y3+...+yr=xr-x1在
区间[p,q]上套用Ross的方法即可，答案为C（p-1，r-2）+C（p，r-2）+...+C（q-1，r-2
）
在本题中，m取15，则p为4，q为8，答案为C（3,2）+C（4,2）+...+C(8,2)，具体数字我就
不算了。

问题4：
对于各不相同的正整数x1，x2，x3，x4，有x1+x2+x3+x4=15，求解向量（x1，x2，x3，x4
）的个数。
所谓磨刀不误砍柴工，前人种树后人乘凉。推广到n，r的情况下，此问只需在第3问得出的
结果再乘以Pr，即r的全排列即可。

showcraft

sorry，问题3，问题4我完全想错了，某种划分情况下，不定方程是求不出正整数解的。
这个问题，我再考虑下，不好意思。

showcraft

多谢ys老指点。
下面继续：
假设那10名燕友是可互相区别的，将他们划分到4个不可区分的队伍中去，每队非空，求划分方案数。如果能推广位n名可互相区别的燕友划分到m个不可区分的非空队伍中去的方案数，则更佳。
比如说，就以3人划为2队为例，老程，菜农，大树三位互相之间当然可以区分，如果队伍之间也可区分，则老程菜农到A队，大树到B队，与老程菜农到B队，大树到A队是两种方案。但现在队伍不可区分，只需要知道老程菜农一队，大树一队，即可。

showcraft

回ys老，这其实就是第二类斯特灵数。偷懒了，就wiki直接转一段
http://zh.wikipedia.org/wiki/%E6%96%AF%E7%89%B9%E7%81%B5%E6%95%B0
第二类Stirling数是个元素的集定义k个等价类的方法数目。常用的表示方法有。
换个较生活化的说法，就是有个人分成组的分组方法的数目。例如有甲、乙、丙、丁四人，若所有人分成1组，只有所有人在同一组这个方法，因此；若所有人分成4组，只可以人人独立一组，因此；若分成2组，可以是甲乙一组、丙丁一组，或甲丙一组、乙丁一组，或甲丁一组、乙丙一组，或其中三人同一组另一人独立一组，即是：

• {A,B},{C,D}
• {A,C},{B,D}
• {A,D},{B,C}
• {A},{B,C,D}
• {B},{A,C,D}
• {C},{A,B,D}
• {D},{A,B,C}

因此。

• 给定，有递归关系
• 
• 
• 
• 

是二项式系数，B_n是贝尔数。

showcraft

也可以看看这里
http://hi.baidu.com/greenwicher/item/078845c5dbbcfd54bdef69c8
p1210 盒子与球 斯特灵数
stirling数　　将n个有区别的球的球放入k个无标号的盒子中( n>=k>=1，且盒子不允许为空)的方案数就是stirling数.(即含 n 个元素的集合划分为 k 个集合的情况数)
　　递推公式:
　　S(n,0) = 0
　　S(n,1) = 1 (k = 1)
　　S(n,n) = 1
　　S(n,k) = 0 (k > n)
　　S(n,k) = S(n-1,k-1)+k*S(n-1,k) (n >= k >= 2)
　　分析：设有n个不同的球，分别用b1,b2,...,bn表示。从中取出一个球bn，bn的放法有以下两种：
　　1.bn独占一个盒子，那么剩下的球只能放在k-1个盒子里，方案数为S（n-1,k-1);
　　2.bn与别的球共占一个盒子，那么可以将b1,b2,...,bn-1这n-1个球放入k个盒子里，然后将bn放入其中一个盒子中，方案数为k*S(n-1,k).

showcraft

继续：
12位高矮不同的燕友排成两排，每排6人且必须是从矮到高排列，而且第二排比对应的第一排的人高。问排列方式有多少种？

showcraft

首先，欢迎晓梦兄，分析的都对，只是结合起来肯定要复杂些。
其次，ys老提醒的对，我已经改了，您等价的也没问题。
再考虑考虑吧，确实不容易的题目，谁让ys老先动用了大规模杀伤性武器呢？
咱只好进口点飞毛腿反击了，呵呵，晚点我再公布答案。

showcraft

晓梦兄的答案是正确的，不知道你用的什么语言，方便的话，你可以贴下代码。
再等等ys老，呵呵。或者你有啥概率方面的趣题也可以拿出来，大家一块看看。

showcraft

这道题和卡特兰数相关。依然偷懒，转现成的。

http://topic.csdn.net/u/20091017 ... 9-d8d0b9fcaada.html
作者:baihacker
来源:http://hi.baidu.com/feixue http://hi.csdn.net/baihacker

问题描述:
12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?
这个笔试题,很YD,因为把某个递归关系隐藏得很深.

问题分析:
我们先把这12个人从低到高排列,然后,选择6个人排在第一排,那么剩下的6个肯定是在第二排.
用0表示对应的人在第一排,用1表示对应的人在第二排,那么含有6个0,6个1的序列,就对应一种方案.
比如000000111111就对应着
第一排:0 1 2 3 4 5
第二排:6 7 8 9 10 11
010101010101就对应着
第一排:0 2 4 6 8 10
第二排:1 3 5 7 9 11
问题转换为,这样的满足条件的01序列有多少个.
观察1的出现,我们考虑这一个出现能不能放在第二排,显然,在这个1之前出现的那些0,1对应的人
要么是在这个1左边,要么是在这个1前面.而肯定要有一个0的,在这个1前面,统计在这个1之前的0和1的个数.
也就是要求,0的个数大于1的个数.
OK,问题已经解决.
如果把0看成入栈操作,1看成出栈操作,就是说给定6个元素,合法的入栈出栈序列有多少个.
这就是catalan数,这里只是用于栈,等价地描述还有,二叉树的枚举,多边形分成三角形的个数,圆括弧插入公式中的
方法数,其通项是c(2n, n)/(n+1).

在<<计算机程序设计艺术>>,第三版,Donald E.Knuth著,苏运霖译,第一卷,508页,给出了证明:
问题大意是用S表示入栈,X表示出栈,那么合法的序列有多少个(S的个数为n)
显然有c(2n, n)个含S,X各n个的序列,剩下的是计算不允许的序列数(它包含正确个数的S和X,但是违背其它条件).
在任何不允许的序列中,定出使得X的个数超过S的个数的第一个X的位置.然后在导致并包括这个X的部分序列中,以
S代替所有的X并以X代表所有的S.结果是一个有(n+1)个S和(n-1)个X的序列.反过来,对一垢一种类型的每个序列,我们都能
逆转这个过程,而且找出导致它的前一种类型的不允许序列.例如XXSXSSSXXSSS必然来自SSXSXXXXXSSS.这个对应说明,不允许
的序列的个数是c(2n, n-1),因此an = c(2n, n) - c(2n, n-1).[Comptes Rendus Acad.Sci.105(Paris, 1887), 436~437]

验证:
其中F表示前排,B表示后排,在枚举出前排的人之后,对应的就是后排的人了,然后再验证是不是满足后面的比前面对应的人高的要求.
C/C++ code
#include <iostream>
using namespace std;

int bit_cnt(int n)
{
    int result = 0;
    for (; n; n &= n-1, ++result);
    return result;
}

int main()
{
    int F[6], B[6];
    int ans = 0;
    for (int state = 0; state < (1 << 12); ++state) if (bit_cnt(state) == 6)
    {
        int i = 0, j = 0;
        for (int k = 0; k < 12; ++k) if (state&(1<<k)) F[i++] = k; else B[j++] = k;
        int ok = 1;
        for (int k = 0; k < 6; ++k) if (B[k] < F[k]) {ok = 0; break;}
        ans += ok;
    }
    cout << ans << endl;
    return 0;
}

结果:132
而c(12, 6)/7 = 12*11*10*9*8*7/(7*6*5*4*3*2) = 132
注意:c(2n, n)/(n+1) = c(2n, n) - c(2n, n-1)

估计出题的人也读过<<计算机程序艺术>>吧.

PS:
另一个很YD的问题:
有编号为1到n(n可以很大,不妨在这里假定可以达到10亿)的若干个格子,从左到右排列.
在某些格子中有一个棋子,不妨设第xi格有棋子(1<=i<=k, 1<=k<=n)
每次一个人可以把一个棋子往左移若干步,
但是不能跨越其它棋子,也要保证每个格子至多只有一个棋子.
两个人轮流移动,移动不了的为输,问先手是不是有必胜策略.

showcraft

我在53楼的转帖已经很好的揭示了此问题的本质，答案为c(2n, n)/(n+1) = c(2n, n) - c(2n, n-1)。不知道晓梦兄有没有看到，或者对其中什么地方有不明白？当然我也只是看了答案思路后才恍然大悟，从白纸开始推导，没这个能力，呵呵。
我去翻阅了Knuth该书中所载，不允许的序列的个数是c(2n, n-1)，这个推导过程正是运用了D.Andre的反射原理，当然我没有搜到这个原理的具体内容。ys老的枚举，包括晓梦兄的思考，应该费了不少力气，枚举，或者说暴力法，当然有助于思考和发现规律，不过更重要的是探寻本质。比如本题的本质，便是卡特兰数以一种排列的形式的应用，明乎此，当可迎刃而解。
这个帖子当然是以Ross的《概率论基础教程》为主，但不会仅限于该书，事实上牵涉到该书内容的，我都会提到在书中何处找到，如果不提就代表其他出处，实际上我同时也在参阅布鲁迪的《组合数学》，Knuth的《具体数学》等。另外，我觉得关注本质内容即可，出处何方，其实殊途同归，意义不大，呵呵。

showcraft

http://zh.wikipedia.org/wiki/%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0
卡塔兰数维基百科，自由的百科全书


卡塔兰数是组合数学中一个常在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)命名。
卡塔兰数的一般项公式为
前几项为 （OEIS中的数列A000108）: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ...
[编辑]性质Cn的另一个表达形式为 所以，Cn是一个自然数；这一点在先前的通项公式中并不显而易见。这个表达形式也是André对前一公式证明的基础。(见下文的第二个证明。)
递推关系
它也满足
这提供了一个更快速的方法来计算卡塔兰数。
卡塔兰数的渐近增长为
它的含义是左式除以右式的商趋向于1当n → ∞。（这可以用n!的斯特灵公式来证明。）
所有的奇卡塔兰数Cn都满足。所有其他的卡塔兰数都是偶数。
[编辑]应用组合数学中有非常多.的组合结构可以用卡塔兰数来计数。在Richard P. Stanley的Enumerative Combinatorics: Volume 2一书的习题中包括了66个相异的可由卡塔兰数表达的组合结构。以下用Cn=3和Cn=4举若干例：

• Cn表示长度2n的dyck word的个数。Dyck word是一个有n个X和n个Y组成的字串，且所有的前缀字串皆满足X的个数大于等于Y的个数。以下为长度为6的dyck words:

XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY

• 将上例的X换成左括号，Y换成右括号，Cn表示所有包含n组括号的合法运算式的个数:

((())) ()(()) ()()() (())() (()())

• Cn表示有n个节点组成不同构二叉树的方案数。下图中，n等于3。

证明：
令1表示进栈，0表示出栈，则可转化为求一个2n位、含n个1、n个0的二进制数，满足从左往右扫描到任意一位时，经过的0数不多于1数。显然含n个1、n个0的2n位二进制数共有个，下面考虑不满足要求的数目。
考虑一个含n个1、n个0的2n位二进制数，扫描到第2m+1位上时有m+1个0和m个1（容易证明一定存在这样的情况），则后面的0-1排列中必有n-m个1和n-m-1个0。将2m+2及其以后的部分0变成1、1变成0，则对应一个n+1个0和n-1个1的二进制数。反之亦然（相似的思路证明两者一一对应）。
从而。证毕。

• Cn表示所有在n × n格点中不越过对角线的单调路径的个数。一个单调路径从格点左下角出发，在格点右上角结束，每一步均为向上或向右。计算这种路径的个数等价于计算Dyck word的个数： X代表“向右”，Y代表“向上”。下图为n = 4的情况：

• Cn表示通过连结顶点而将n + 2边的凸多边形分成三角形的方法个数。下图中为n = 4的情况：

• Cn表示对{1, ..., n}依序进出栈的置换个数。一个置换w是依序进出栈的当S(w) = (1, ..., n), 其中S(w)递归定义如下：令w = unv，其中n为w的最大元素，u和v为更短的数列；再令S(w) = S(u)S(v)n，其中S为所有含一个元素的数列的单位元。

• Cn表示集合{1, ..., n}的不交叉划分的个数. 那么, Cn 永远不大于第n项贝尔数. Cn也表示集合{1, ..., 2n}的不交叉划分的个数，其中每个段落的长度为2。综合这两个结论，可以用数学归纳法证明 that all of the free cumulants of degree more than 2 of the Wigner semicircle law are zero. This law is important in free probability theory and the theory of random matrices.

• Cn表示用n个长方形填充一个高度为n的阶梯状图形的方法个数。下图为 n = 4的情况:

showcraft

不用客气。晓梦兄应该没受到飓风的影响吧？
不过你说不太概率，我觉得不妥。该题显然还是在组合数学的范畴内，当然用到了精妙的trick，而组合数学是概率的基础，我觉得还是挺概率的。
这段时间同时又在看Strang的linear algebra，所以ross的概率，我暂时搁浅在了第二章，等发现啥精彩的再说，呵呵。

showcraft

出道趣味题：
问题1.一个桶里各有黑白球100个，按照如下规则取球：
每次从桶中取出两个球，若这两个球同色，则再放入一个黑球，若异色，再放入一个白球。若干次后，最终桶里只剩下一个球，请问这个球是黑球的概率是多少？
问题2.如果是99个黑球，101个白球呢？

showcraft

晓梦兄的分析完全正确，送上一朵小红花！
我再补充几句吧。正如晓梦兄所言，每次拿两球退一球操作后，白球数目或者不变或者减2，也就是说每次操作后白球数目的奇偶性与初始状态保持一致，那么最后一轮过后只剩下一个球，该种状况下白球数目的奇偶性与初始状态相等。所以在第一种情况下，留下0个白球（与初始100个白球的奇偶性一致），第二种情况下留下1个白球（与初始101个白球的奇偶性一致）
既然是趣味题，大树兄就不用想的太复杂了，呵呵。

showcraft

200个球，每轮拿两球退一球操作后球的总数目减1，所以总共要经过199轮，剩下1个球，第198轮过后，剩下两个球。在第一种情况下，这两个球或者全黑或者全白，下一轮操作过后，留下的始终是黑球。第二种情况下，这两个球只能是一黑一白，下一轮操作后，留下的最后一个球是白球。