IOI2009 冬令营论文 梅诗珂
证明:这个定理看上去很显然,因为先取 a 个球再取 b 个球应当是与直接取(a+b)个球
等价的,现在我们用代数方法证明。首先证明
)( nbaCCCC
a
ba
ba
n
b
an
a
n
。因为
)(
!!
)!(
)!()!(
!
)!(!)!(!
)!(!
nbaCC
ba
ba
banba
n
banbana
ann
CC
a
ba
ba
n
b
an
a
n
。
假设在先取 a 个球,再取 b 个球后,红球被取了 r 个。显然每次取球是互相独立的。所
以这种情况的概率是
)(
)1(
)1(
1
1
11
),(
01
b
abluered
arb
aablue
ar
ared
a
bluered
aa
blue
a
red
raMin
a
C
CC
C
CC
)(
11
),(
01
a
ba
aa
rba
a
r
ba
bluered
rba
blue
r
red
raMin
a
C
CC
C
CC
(应用上面的结论)
ba
bluered
rba
blue
r
red
C
CC
其中 a1 表示第一次取到的红球数,在第二个等式的右边,因为 a1≤a 和 a1≤r 总有一个成
立,所以等式恒成立。这个等式告诉我们从 red 个红球与 blue 个蓝球中先取 a 个球,再取
b 个求,与直接取(a+b)个球造成的剩余不同颜色的球数的概率分布是完全相同的。所以取
球的顺序与最终的结果没有关系。■
我们设 F(r,b)表示当前有 r 个红球,b 个蓝球的,被事先取走了 removed 个球(不知道
它们的颜色),面对这个局面的玩家所能得到的最大胜率。当玩家取走 m 个球时,根据定理
一,新的局面与玩家先取走 m 个球,再让 removed 个球被取走所得到的局面完全一样!但
是有一种边界情况要考虑:由于不能保证 removed≤r,可能在一些情况下,取走 m 个球后,
玩家已经输了,而不能进行下面的游戏。要解决这种特殊情况,只需对 F 的定义和动态规划
方程略加修改:让 F(r,b)表示当前有 r 个红球,b 个蓝球,被取走了 removed 个球但仍然至
少还有 1 个红球的情况下,当前玩家的最大胜率。
我们用 Pro(r,b,k)表示有 r 个红球,b 个蓝球,取走 k 个球而红球数仍大于 0 的概率,
那么 Pro(r,b,k)=
bakra
k
br
ak
b
a
r
C
CC
0,
。我们用递推式求解,显然
Pro(0,b,0) = 0;
Pro(r,b,0) = 1; (r>0)
)1,1,(Pr)1,,1(Pr),,(Pr
kbro
br
b
kbro
br
r
kbro
再考虑(1),因为 r 个红球,b 个蓝球取走 removed 个球仍有至少 1 个红球的情况,包含
了有(r-p)个红球,(b-q)个蓝球,取走 removed 个球后仍有至少 1 个红球的情况,因此在前