田忌赛马问题加强版(排列组合）齐威王与田忌赛马输掉以后,很不服气,想赢回来.为此他仔细研究了孙膑的策略,准备了2n匹能力各不相同的马,而田忌不知各匹马的能力.齐威王让田忌可以从中

Question

田忌赛马问题加强版(排列组合）
齐威王与田忌赛马输掉以后,很不服气,想赢回来.为此他仔细研究了孙膑的策略,准备了2n匹能力各不相同的马,而田忌不知各匹马的能力.齐威王让田忌可以从中任选n匹马,自己得剩下的n匹.比赛的时候每人每次各拿一匹马参赛,一共赛n次.试问在策略选择恰当的情况下,齐威王有多大的几率能保证获得全胜,即n次比赛全部获得胜利.

Answer 1

将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)