一道纯概率题

回复 60# runyutong
A面不连续，B面可以连续

赞！应该是正解。只是有一点我还有疑虑，也是我走入歧途的原因。

n+1场可以看作先比1场，再比n场， ...
Howard 发表于 2010-12-4 00:01

    昨天去打扑克的时候就一直在想这个问题，突然发现我的“歧途“其实也不那么歧。

我当时是这么想的，假设n场没有两连输是K(n), 那么K（n+1）可以看作先比1场，再比n场。

I。若这n场中的第一场（总第二场）输，则先比的第一场必是胜，剩下的组合数就是K（n-2）。为什么不是K（n-1）呢？因为n场中第一场输，第二场必然是胜，从第三场开始才随便排列。

II。若这n场中第一场胜，则先比的第一场随便，可以胜也可以输，n场中从第二场开始也就是K（n-1），所以总共是2×K（n-1）

综合I和II，可得K（n+1）=2K（n-1）+ K（n-2）

然后我就郁闷了，因为这跟标准答案不一致。标准答案是菲薄拿起数列，也就是K（n+1）=K（n）+ K（n-1）。从我的答案怎么也推算不出标准的答案。

昨天又发现，虽然从我的推不出标准，但是从标准可以推出我的。因为菲薄拿起数列的定义，
K（n+1）=K（n）+ K（n-1）     （1）
K（n）=K（n-1）+ K（n-2）     （2）

（2）代入（1）即可得到: K（n+1）=2K（n-1）+ K（n-2），也就是我的答案！

然后我就想，菲薄拿起数列可以推导出我的，那我的也可以反推回去。但是经过3个小时的努力，我发现我完全找不到办法推回去！

总结一下我的疑问：如何证明K（n+1）=2K（n-1）+ K（n-2）其实就是菲薄拿起数列K（n+1）=K（n）+ K（n-1）???

不出现3连输的情况，假设n场是K（n）种组合，计算n+1场，可以看作先比1场，再比n场。

一。如果这一场输了，那么要求后面n场中的第一场：
    I。赢，可以，剩下n-1场，也就是K（n-1）
    II。输，分情况
         1. n场中前两场是输输，这就没得玩了，三连输出现。0
         2. n场中前两场是输赢，剩下的n-2场任意，就是K（n-2）

二。 如果这一场赢了，剩下n场任意，也就是K（n）

综上，K（n+1）= K（n）+ K（n-1）+ K（n-2），也就是3阶菲薄拿起数列。

不知道这题有没有被解开，简单想了下，推出了递推公式，但求出通项公式比较麻烦。先给出解法：

我们可以把双方的战绩简化成以下描述方式：巴萨连胜X场，然后皇马连胜X场，然后巴萨X场，然后皇马X场。。。（X在1-4之间，当然一开始也可能是皇马-巴萨-皇马-。。。）。然后我们可以来构造一种双方n场比赛的战绩排列可能：先把所有n场有序比赛任意分成若干个部分，每个部分的长度为1-4，然后，把奇数部分写成巴萨胜，偶数写成皇马胜，或者奇数写成皇马胜，偶数写成巴萨胜。可见，要罗列n场对战（小于5场连胜或连败）的所有可能性，即等价于求出把n个有序单位分成若干部分（每部分长度1-4）的所有可能性的2倍。

我们设Pn为n个单位能够分成若干部分（每部分长度1-4）的所有可能分法数。先分析n个单位的分法：分出1个单位，然后对n-1个单位进行分割；分出2个单位，然后对n-2个单位进行分割；分出3个单位，然后对n-3个单位进行分割；分出4个单位，然后对n-4个单位进行分割。

所以，我们得出递推公式：

Pn=P(n-1)+P(n-2)+P(n-3)+P(n-4)

所求概率为（2×Pn）/2^n

n=238带入即原题答案。

这个公式求解起来很麻烦，首先要凑出 Pn-aP(n-1)-bP(n-2)-cP(n-3)=s[P(n-1)-aP(n-2)-bP(n-3)-cP(n-4)] 的形式，累加得出Pn关于P(n-1),P(n-2),P(n-3)的递推公式，然后继续凑数累加消项得出Pn关于P(n-1),P(n-2)的递推公式，接着重复求出Pn关于P(n-1)的公式，最后求出Pn的通项公式。。。本人就不求了。期待达人求出结果。。。

再把公式改得完美一点：

两队n场比赛不出现m场连胜或连败的可能性为：2*p(n,m)/2^n

其中p(n,m)=p(n-1,m)+p(n-2,m)+...+p(n-m+1,m)

当m=3时，p(n,3)为斐波那契数列。

原题为m=5的情况，通项公式待求。。。

再把公式改得完美一点：

两队n场比赛不出现m场连胜或连败的可能性为：2*p(n,m)/2^n

其中p(n,m)=p(n-1,m)+ ...
damajer 发表于 2010-12-5 19:38

    赞一个先！思路独特，清晰简洁，我暂时没发现任何不对劲的地方。

帮忙看一下我62楼的问题如何？

再把公式改得完美一点：

两队n场比赛不出现m场连胜或连败的可能性为：2*p(n,m)/2^n

其中p(n,m)=p(n-1,m)+p(n-2,m)+...+p(n-m+1,m)

当m=3时，p(n,3)为斐波那契数列。

原题为m=5的情况，通项公式待求。。。
damajer 发表于 2010-12-5 19:38

从最初始的几场算了一下，确定了一下初始条件。

n场巴萨不出现3连输概率是 F3(n+2)/2^n, 其中F3(n+2)表示3阶斐波那契数列的第n+2个数；
n场任一队均不出现3连输概率是2×F2(n+1)/2^n，其中F2(n+1）表示 2阶斐波那契数列（也就是普通斐波那契数列）的第n+1个数；

n场巴萨不出现4连输概率是 F4(n+2)/2^n, 其中F4(n+2)表示4阶斐波那契数列的第n+2个数；
n场任一队均不出现4连输概率是2×F3(n+1)/2^n，其中F3(n+1）表示 3阶斐波那契数列的第n+1个数；

n场巴萨不出现5连输概率是 F5(n+2)/2^n, 其中F5(n+2)表示5阶斐波那契数列的第n+2个数；
n场任一队均不出现5连输概率是2×F4(n+1)/2^n，其中F4(n+1）表示 4阶斐波那契数列的第n+1个数；

n场巴萨不出现m连输概率是 Fm(n+2)/2^n, 其中Fm(n+2)表示m阶斐波那契数列的第n+2个数；
n场任一队均不出现m连输概率是2×F[m-1](n+1)/2^n，其中F[m-1](n+1）表示 m-1阶斐波那契数列的第n+1个数；

回到墙的问题，238场任意一队不出现5连输：
n=238时，F4（n+1）= F4(239) = 3.84651E+67
2×F4(n+1)/2^n = 2*3.84651E+67 / 4.41712E+71 = 0.0174%

终于算出来了！

---附：m阶斐波那契数列的第k个数定义如下-------

1） 当k<=0时，Fm(k)=0;

2) 当k=1, k=2时，Fm(1)=Fm(2)=1;

3） 当k>2时，Fm(k)=Fm(k-1) + Fm(k-2) + ... + Fm(k-m)

本帖最后由 Howard 于 2010-12-5 05:38 编辑

总结一下我的疑问：如何证明K（n+1）=2K（n-1）+ K（n-2）其实就是菲薄拿起数列K（n+1）=K（n）+ K（n-1）???
Howard 发表于 2010-12-5 05:37

被一个笑话引了过来，一早上都在看这个了。

要证明Howard的公式就是斐波那契数列其实可以用个简单的方法-枚举法：
因为根据题意得知：K（2）= 3 ，K（3） = 5，K（4） = 8，带入公式可枚举出的数列就是斐波那契数列，不知howard认可否？

被一个笑话引了过来，一早上都在看这个了。

要证明Howard的公式就是斐波那契数列其实可以用个简单的方法 ...
taoljj 发表于 2010-12-6 11:11

    枚举可以证伪，只要有一个不符合就足够了；但无法证实，因为就算枚举到100000时都没问题，难保下一个就有问题。有点像哥德巴赫猜想，算到10^10000000了都吻合，但是仍然无法证明，呵呵。我那个公式推到斐波那契数列可能很简单一步就能过去，但是我卡壳了就是想不到。

赞一个先！思路独特，清晰简洁，我暂时没发现任何不对劲的地方。

帮忙看一下我62楼的问题如何？ ...
Howard 发表于 2010-12-6 10:30

对于K（n+1）=2K（n-1）+ K（n-2）就是斐波那契数列的证法，其一可以用数学归纳法，也是最简单的方法，证法略；另外也可以纯用数学方法推导，证法如下：


我们先把原公式写成K(n+1)-aK(n)-bK(n-1)=s[K(n)-aK(n-1)-bK(n-2)]的形式，然后列出所有项：

K(n+1)-aK(n)-bK(n-1)=s[K(n)-aK(n-1)-bK(n-2)]
K(n)-aK(n-1)-bK(n-2)=s[K(n-1)-aK(n-2)-bK(n-3)]
K(n-1)-aK(n-2)-bK(n-3)=s[K(n-2)-aK(n-3)-bK(n-4)]
...
K(4)-aK(3)-bK(2)=s[K(3)-aK(2)-bK(1)]

以上各项左右相乘消项，得：

K(n+1)-aK(n)-bK(n-1)=s^(n-2)[K(3)-aK(2)-bK(1)]

由K(3)=2,K(2)=1,K(1)=1,代入得：

K(n+1)-aK(n)-bK(n-1)=s^(n-2)(2-a-b)

然后我们要解出s、a、b的值。由原式我们可列出一个方程组：

a+s=0
b-as=2
-bs=1

注意这里可能会有多个解，但我们只需要其中一个解就够了。我们可以用投机取巧的方法：假设a=1，b=1是原式的解（因为如果a=b=1是该式解的话对于我们来说将更方便地得出结论），代入解出原式的一个解为：s=-1，a=1，b=1。代入我们刚刚解出的方程，即得到斐波那契的递推公式：

K(n+1)=K(n)+bK(n-1)