田忌赛马问题加强版(排列组合）

来源：百度知道 编辑：UC知道 时间：2024/05/17 08:56:16
齐威王与田忌赛马输掉以后，很不服气，想赢回来。为此他仔细研究了孙膑的策略，准备了2n匹能力各不相同的马，而田忌不知各匹马的能力。齐威王让田忌可以从中任选n匹马，自己得剩下的n匹。比赛的时候每人每次各拿一匹马参赛，一共赛n次。试问在策略选择恰当的情况下，齐威王有多大的几率能保证获得全胜，即n次比赛全部获得胜利。

将2n匹马按能力排序为：
A1>A2>A3>....>A2n
定义数列{ai}为：
当Ai归齐威王，ai=1
当Ai归田忌时，ai=-1
令Si=a1+a2+a3+…+ai

显然a1+a2+a3+…+a2n=0(每人各得n匹马)
若齐威王想保证全胜，则必须使Si≥0，i=1,2,3…2n
问题转化为当ai=1或-1时，
a1+a2+a3+…+a2n=0
Si=a1+a2+a3+…+ai≥0
一共有多少组解。
这个问题可以用方格法求解，写下来比较困难，这里只写结果为C(n,2n)-C(n-1,2n) 其中C(n,2n)表示2n选n的方法数。

而总共的选择方法有C(n,2n)种
因此全胜的几率为[C(n,2n)-C(n-1,2n)]/ C(n,2n)=1/(n+1)

要分情况讨论，N=1时；N=2时；N为奇数时；N为偶数时。
好久没有弄排列组合了，翻翻书再回答你