一道概率题

我思故我在

投票选举两个人甲和乙，已知甲共得m张，乙共得n张，（m>n）求在投票过程中，甲始终领先于乙的概率。

mathe

这个题过去有人在败毒数学吧问过。题目链接我找不到了，不过题目对应的图还在我的败毒空间里面:
http://hiphotos.baidu.com/quad%5 ... eea035d52af1ac.jpeg
现在把图给贴过来

kon3155

参考答案：(转自http://www.tianya.cn/techforum/Content/71/535787.shtml)

　　因为票都是无差别的，取票过程也是随机的，所以这个问题也就是甲得票一直领先的概率，但是一个一个列举出来确实会累出人命的。我们不妨来简化一下，假设有6个人投票，甲4票，丙2票。甲的票我们记做A，乙的票我们记做C，现在我们看其中的一种排列，AAAACC，按这个顺序出票的话，甲是一直领先的，那如果我们把这个直线顺序弯起来，做成一个环形顺时针走，1号是第一个A，那么从一号开始出票就是AAAACC，从2号开始到1号结束就是AAACCA，接下来还有AACCAA，ACCAAA，CCAAAA，CAAAAC，一共六种不同的出票顺序，这其中只有AAAACC，AAACCA两种情形，也就是从1号和2号票开始，甲才能一直保持领先。这个数据有没有通过计算得到呢，我们不妨在这个圈子中把相连的AC划掉，因为这其中第一个A不起作用，刚加上就被C又超过，对甲一直保持领先没有贡献，同样第二个C也是没意义的，因为如果在此之前甲领先，那么与他同时出现且在前面的A也抵消了C的作用，C对甲无法一直领先也没有贡献，所以同时消除不影响结果，于是这个圈子里（AAAACC）的4号和5号两张票消失了，圈子简化成AAAXXC，XX代表原来那个AC的空位，这时候3号票和6号票也相连了，于是再次消除3号，6号，于是圈子变成AAXXXX，那么从1号和2号开始的两种顺序就是甲的得票一直领先，也就是A的总数一直大于C的总数的情况，不难得知这个可能的情况总是A-C那么多。
　　　　
　　不过很可惜，AAAACC以及衍生出的另外5种情况并不是全部的可能情况，我们还可以排出AAACAC这样一个圈子，并且可以分别从2号，3号一直到6号票开始顺时针转，找到另外不同的五种排列情况：AACACA，ACACAA，CACAAA，ACAAAC，CAAACA，不过采用第一个圈子里的消除法，我们同样可以找到仍然是只有两种情况，也就是从1号和2号开始的两种情况能够保证A一直大于C，甲一直领先乙。这两个圈子里所有可能的情况都是6，也就是总的票数，所有甲领先的可能情形都是2种，也就是A-C的差。
　　　　
　　当然，也许会注意到另外一种情况，就是AACAAC，这样的圈子实际上只有三种不同情况，从1号开始和从4号开始是一样的，从2号和从5号也是，3号和6号也是，这个先放一边，我们还是用消除法，变成了AXXAXX，也就是说能够保证甲一直领先的开票方式是从1号票开始，或者从4号票，但是实际上1号票和4号票的顺序是一样的，是同一种情况AACAAC，所以这个圈子里保证A>C的情况只有一种，那么这个圈子里甲领先的概率就是1/3，其实跟2/6是一样的。现在实际上我们已经枚举了所有的情况，三种圈子，6+6+3种排列方式，其中有，2+2+1种甲领先的情况，不管这个圈子变得多么的大，也不管会出现多少不同的圈子，情况都和这6个人构成的三个圈子类似，可能的概率就是(A-C)/(A+C)。

mathe

上面计算结果是错误的。
还是参考我上面给的图，当然这个图中的m,n和本问题的正好反过来了。
我们考虑投票开始时将一只笔指向原点，每次甲得票，像右上方45度角做长度为sqrt(2)的线段（也就是从(x,y)到(x+1,y+1)），而每次乙得票，向右下方45度角做长度为sqrt(2)的线段（也就是从(x,y)到(x+1,y-1)）.
这样我们就得到一条从(0,0)到(n+m,m-n)的折线。
其中甲始终领先对应于那些不会同直线y=-1相交的折线（接触就认为相交）。
如果先不考虑甲始终领先的条件，那么这些折线的数目相当于m+n条折线选择任意m条向上的数目，就是$C_{m+n}^m$
我们现在查看哪些会同直线y=-1的折线的数目。将这些折线在它和y=-1的第一个交点后面部分关于直线y=-1翻转180度，也就是如图黑色虚线变成红色虚线，那么我们可以得到一个从(0,0)出发，到(n+m,n-m-2)结束的折线，而这样折线数目相当于m+n条折线选择m+1条向下,n-1条向上，所以总数为$C_{m+n}^{m+1}$.
而反过来，对于任何一条从(0,0)出发，到(n+m,n-m-2)结束的折线，必然同直线y=-1相交，将它第一个交点后面部分翻转必然对应唯一一个本题中甲不是始终领先情况的局面。
由此得到
总情况$C_{m+n}^m$,其中甲始终领先情况$C_{m+n}^m-C_{m+n}^{m+1}$,所以比例是
${C_{m+n}^m-C_{m+n}^{m+1}}/{C_{m+n}^m}=1-n/{m+1}={m-n+1}/{m+1}$
特别，比如m=2,n=1时，这个概率就是$2/3$,容易检查出来，这个时候这个结论是对的，而对应楼上的结论，对应$1/3$是错误的

没——问题

原帖
http://tieba.baidu.com/f?kz=467963534

我思故我在

能不能在讲的详细点？

meishigan

我觉得这道题和买票的题还不一样

这个投票的题要求甲的票数始终都比乙的票数多，不能够包括甲的票数和乙的票数相同的情况。而买票的题就允许票数相同的情况。
所以，任何时候，甲至少要比乙多一票。这样最后结果应该是(m-n)/(m+n).

LLJ_LLJ

4#mathe的计算结果很显然是错误的。按照他自己举的例子：m＝2，n＝1。
显然只有3个人投票，甲在投票过程中始终领先，投给乙的一票只能是第三个人投的。所以概率是1/3。
对于n＝1的情况：很显然概率＝(m－1)/(m+1)。    投给乙的一票只能是第3个人以后的人投的（包括第3个人）。
在这种特例，显然4＃的结果都是错误的，而3＃的结果是符合的。
但是不是对于n>1都成立，还要考虑。

kon3155

mathes? 这个名字？有点危险

LLJ_LLJ

用S(m,n) 表示甲始终领先乙的总排列数。P(m,n)表示甲始终领先乙的概率。            用C(N,M)表示N中取M的排列数。
那么    P(m,n)=S(m,n) / C(m+n,m)   

那么可以得出      S(m,0)=1 ,  S(m,k) =0   (k>=m)   
    以及递推公式    S(m,n)=  ∑  C(m-1-k,n-k) *  S(n,k)        k=0  to n
n=1  ,得出  S(m,1)=  (m-1)/(m+1)  *  C(m+1,m)      即   P(m,1))=  (m-1)/(m+1)
n=2  ,得出  S(m,2)=  (m-2)/(m+2)  *  C(m+2,m)      即   P(m,2))=  (m-2)/(m+2)
n=3  ,得出  S(m,3)=  (m-3)/(m+3)  *  C(m+3,m)      即   P(m,3))=  (m-3)/(m+3)

可以用数学归纳法证明。 n=k 时    S(m,n)=  (m-n)/(m+n)  *  C(m+n,m)    成立，
                  可推出    n=k+1 时    S(m,n)=  (m-n)/(m+n)  *  C(m+n,m)    也成立。
所以   P(m,n)=(m-n)/(m+n) 成立。
因此 3#  的答案是正确的。  而他的解法巧妙的  把众多的排列分成m+n个排列一组，每组中都只有m-n种符合情况。所以很简单就得出了同样的结论。