[组合] 田忌赛马推广-n匹马

realnumber

【LV1】江苏苏州孙四周:
伙计们，别忙着庆祝啦．帮老夫一个忙：请教一个问题．田忌赛马的问题中，如果双方各有n匹马，且实力对比同前．则田忌有多少种获胜策略？
换个提法，正项递增数列{$a_n$},{$b_n$},$n\ge3$,满足$a_i<b_i,i=1,2,....,n$和$a_{i+1}>b_i,i=1,2,....,n-1$即$a_1<b_1<a_2<b_2<a_3<b_3<...<a_n<b_n$.
下列n个坐标
\[(a_{k_1},b_1),(a_{k_2},b_2),....,(a_{k_n},b_n)．\]
其中$k_1,k_2,...k_n是1,2,3...,n的某一个排列$．若这n个点在直线y=x上方的数目大于在下方的数目，则称是一个＂获胜策略＂．
问有几种不同的＂获胜策略＂．
－－－－我们的做法当然是先试试特殊到一般，有哪位先来n=3,4,5....
发在初等数学研究上的

下载 (88.98 KB)

2014-5-21 10:28

realnumber

同事王的描述：
A的下标大于B的下标，该局获胜；相当于N个自然数排列跟原来的顺序对照．
－－－这样描述问题就更简练了．就此修改下１楼．

realnumber

这里国王一定出(1,2,3,4,....,n)
n=3，田忌出(2,3,1)就一种
n=4,(2,3,4,1)一种
n=5,(2,3,4,5,1),(2,1,4,5,3),(2,3,1,5,4),(2,3,4,1,5),(2,4,5,1,3),(2,4,5,3,1),(3,4,5,1,2),(3,4,5,2,1),(3,5,4,1,2),(3,5,4,2,1),(3,4,1,5,2),(3,4,2,5,1),(3,1,4,5,2),(3,2,4,5,1),(3,1,5,4,2),(3,2,5,4,1)，还有很多，下次继续，休息下～～

tommywong

可愚弄马子，不可愚弄读者

这群劣质马获胜的期望值真的是$sgn(a_2-b_1)+sgn(a_3-b_2)+sgn(a_1-b_3)=1$吗？不见得。

实力为$a_2$与实力为$b_1$比赛，实力为$a_2$获胜的概率为$\displaystyle \frac{a_2}{a_2+b_1}$，实力为$b_1$获胜的概率为$\displaystyle \frac{b_1}{a_2+b_1}$

则获胜的期望值为$\displaystyle \frac{a_2-b_1}{a_2+b_1}+\frac{a_3-b_2}{a_3+b_2}+\frac{a_1-b_3}{a_1+b_3}$

设$a_1,b_1,a_2,b_2,a_3,b_3$有等差d，看看这是什么鬼东西！

$\displaystyle \frac{d}{a_2+b_1}+\frac{d}{a_3+b_2}+\frac{-5d}{a_1+b_3}$

realnumber

??回复 4# tommywong
不明白，题目假定没有概率，一般的马一定比更好的马慢．
１楼问题似乎很难，算了，直接放弃．

tommywong

之前我考虑了n=1,2,3,4的所有得分分布
n=1时只能输掉，记分布为{1}
n=2时可打平、可输掉，记分布为{1,1}
n=3时
(2,4,6)
(1,3,5)=-3
(1,5,3)=-1
(3,1,5)=-1
(3,5,1)=1
(5,1,3)=-1
(5,3,1)=-1
记分布为{1,4,1}
n=4时
穷举了24次，终于得到分布为{1,11,11,1}
但看不出规律，所以放弃了

现在却跟这个数列一样......http://kuing.orzweb.net/forumdisplay.php?fid=5

tommywong

设取胜次数f(x,y,z)=(x>1)+(y>2)+(z>3)
f(1,2,3)=0
f(1,3,2)=1
f(2,1,3)=1
f(2,3,1)=2
f(3,1,2)=1
f(3,2,1)=1
n匹马取胜m次的方法数a(n,m)
a(3,0)=1,a(3,1)=4,a(3,2)=1
考虑第n+1匹马
若前n匹马能取胜m次，第n+1匹马放在能取胜的m匹马上，或第n+1匹马放在原位：(m+1)a(n,m)
若前n匹马能取胜m-1次，第n+1匹马放在不能取胜的m-1匹马上：(n-m+1)a(n,m-1)
$a(n+1,m)=(m+1)a(n,m)+(n-m+1)a(n,m-1)$
$a(n,m)=\sum_{k=0}^m (-1)^k C_{n+1}^k (m+1-k)^n$
http://bbs.emath.ac.cn/thread-5548-1-1.html